The role of randomness in the broadcast congested clique model

Florent Becker; Pedro Montealegre; Ivan Rapaport; Ioan Todinca

doi:10.1016/j.ic.2020.104669

The role of randomness in the broadcast congested clique model

Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Research output: Contribution to journal › Article › peer-review

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 randomness. • One-round public-coin algorithms can be exponentially more powerful than deterministic 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.

Original language	English
Article number	104669
Journal	Information and Computation
Volume	281
DOIs	https://doi.org/10.1016/j.ic.2020.104669
State	Published - Dec 2021
Externally published	Yes

Keywords

Broadcast congested clique
Distributed computing
Message size complexity
Private and public coins
Simultaneous multi-party communication

Access to Document

10.1016/j.ic.2020.104669

Cite this

@article{f7a9bc5d2c90456099a7ed81852f9126,

title = "The role of randomness in the broadcast congested clique model",

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 randomness. • One-round public-coin algorithms can be exponentially more powerful than deterministic 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.",

keywords = "Broadcast congested clique, Distributed computing, Message size complexity, Private and public coins, Simultaneous multi-party communication",

author = "Florent Becker and Pedro Montealegre and Ivan Rapaport and Ioan Todinca",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Inc.",

year = "2021",

month = dec,

doi = "10.1016/j.ic.2020.104669",

language = "English",

volume = "281",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - The role of randomness in the broadcast congested clique model

AU - Becker, Florent

AU - Montealegre, Pedro

AU - Rapaport, Ivan

AU - Todinca, Ioan

PY - 2021/12

Y1 - 2021/12

N2 - 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 randomness. • One-round public-coin algorithms can be exponentially more powerful than deterministic 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.

AB - 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 randomness. • One-round public-coin algorithms can be exponentially more powerful than deterministic 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.

KW - Broadcast congested clique

KW - Distributed computing

KW - Message size complexity

KW - Private and public coins

KW - Simultaneous multi-party communication

UR - http://www.scopus.com/inward/record.url?scp=85106828923&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2020.104669

DO - 10.1016/j.ic.2020.104669

M3 - Article

AN - SCOPUS:85106828923

SN - 0890-5401

VL - 281

JO - Information and Computation

JF - Information and Computation

M1 - 104669

ER -

The role of randomness in the broadcast congested clique model

Abstract

Keywords

Access to Document

Fingerprint

Cite this