| Home | << 1 >> |
|
| Record | |||||
|---|---|---|---|---|---|
| Author | Becker, F.; Montealegre, P.; Rapaport, I.; Todinca, I. | ||||
| Title | The role of randomness in the broadcast congested clique model | Type | |||
| Year | 2021 | Publication | Information and Computation | Abbreviated Journal | Inf. Comput. |
| Volume | 281 | Issue | Pages | 104669 | |
| Keywords | Distributed computing; Broadcast congested clique; Message size complexity; Private and public coins; Simultaneous multi-party communication | ||||
| Abstract | We study the role of randomness in the broadcast congested clique model. This is a message-passing model of distributed computation where the nodes of a network know their local neighborhoods and they broadcast, in synchronous rounds, messages that are visible to every other node. This works aims to separate three different settings: deterministic protocols, randomized protocols with private coins, and randomized protocols with public coins. We obtain the following results: If more than one round is allowed, public randomness is as powerful as private ran-domness. One-round public-coin algorithms can be exponentially more powerful than determin-istic algorithms running in several rounds. One-round public-coin algorithms can be exponentially more powerful than one-round private-coin algorithms. One-round private-coin algorithms can be exponentially more powerful than one-round deterministic algorithms. |
||||
| Address | |||||
| Corporate Author | Thesis | ||||
| Publisher | Place of Publication | Editor | |||
| Language | Summary Language | Original Title | |||
| Series Editor | Series Title | Abbreviated Series Title | |||
| Series Volume | Series Issue | Edition | |||
| ISSN | 0890-5401 | ISBN | Medium | ||
| Area | Expedition | Conference | |||
| Notes | WOS:000721215200042 | Approved | |||
| Call Number | UAI @ alexi.delcanto @ | Serial | 1491 | ||
| Permanent link to this record | |||||