# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1807.05626.pdf

(Preprint), 441KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Clementi, A., Gualà, L., Natale, E., Pasquale, F., Scornavacca, G., & Trevisan, L. (2018). Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise. Retrieved from http://arxiv.org/abs/1807.05626.

Cite as: https://hdl.handle.net/21.11116/0000-0002-B985-7

##### Abstract

Consensus and Broadcast are two fundamental problems in distributed

computing, whose solutions have several applications. Intuitively, Consensus

should be no harder than Broadcast, and this can be rigorously established in

several models. Can Consensus be easier than Broadcast?

In models that allow noiseless communication, we prove a reduction of (a

suitable variant of) Broadcast to binary Consensus, that preserves the

communication model and all complexity parameters such as randomness, number of

rounds, communication per round, etc., while there is a loss in the success

probability of the protocol. Using this reduction, we get, among other

applications, the first logarithmic lower bound on the number of rounds needed

to achieve Consensus in the uniform GOSSIP model on the complete graph. The

lower bound is tight and, in this model, Consensus and Broadcast are

equivalent.

We then turn to distributed models with noisy communication channels that

have been studied in the context of some bio-inspired systems. In such models,

only one noisy bit is exchanged when a communication channel is established

between two nodes, and so one cannot easily simulate a noiseless protocol by

using error-correcting codes. An $\Omega(\epsilon^{-2} n)$ lower bound on the

number of rounds needed for Broadcast is proved by Boczkowski et al. [PLOS

Comp. Bio. 2018] in one such model (noisy uniform PULL, where $\epsilon$ is a

parameter that measures the amount of noise). In such model, we prove a new

$\Theta(\epsilon^{-2} n \log n)$ bound for Broadcast and a

$\Theta(\epsilon^{-2} \log n)$ bound for binary Consensus, thus establishing an

exponential gap between the number of rounds necessary for Consensus versus

Broadcast.

computing, whose solutions have several applications. Intuitively, Consensus

should be no harder than Broadcast, and this can be rigorously established in

several models. Can Consensus be easier than Broadcast?

In models that allow noiseless communication, we prove a reduction of (a

suitable variant of) Broadcast to binary Consensus, that preserves the

communication model and all complexity parameters such as randomness, number of

rounds, communication per round, etc., while there is a loss in the success

probability of the protocol. Using this reduction, we get, among other

applications, the first logarithmic lower bound on the number of rounds needed

to achieve Consensus in the uniform GOSSIP model on the complete graph. The

lower bound is tight and, in this model, Consensus and Broadcast are

equivalent.

We then turn to distributed models with noisy communication channels that

have been studied in the context of some bio-inspired systems. In such models,

only one noisy bit is exchanged when a communication channel is established

between two nodes, and so one cannot easily simulate a noiseless protocol by

using error-correcting codes. An $\Omega(\epsilon^{-2} n)$ lower bound on the

number of rounds needed for Broadcast is proved by Boczkowski et al. [PLOS

Comp. Bio. 2018] in one such model (noisy uniform PULL, where $\epsilon$ is a

parameter that measures the amount of noise). In such model, we prove a new

$\Theta(\epsilon^{-2} n \log n)$ bound for Broadcast and a

$\Theta(\epsilon^{-2} \log n)$ bound for binary Consensus, thus establishing an

exponential gap between the number of rounds necessary for Consensus versus

Broadcast.