English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Consensus and Broadcast are two fundamental problems in distributedcomputing, whose solutions have several applications. Intuitively, Consensusshould be no harder than Broadcast, and this can be rigorously established inseveral models. Can Consensus be easier than Broadcast?  In models that allow noiseless communication, we prove a reduction of (asuitable variant of) Broadcast to binary Consensus, that preserves thecommunication model and all complexity parameters such as randomness, number ofrounds, communication per round, etc., while there is a loss in the successprobability of the protocol. Using this reduction, we get, among otherapplications, the first logarithmic lower bound on the number of rounds neededto achieve Consensus in the uniform GOSSIP model on the complete graph. Thelower bound is tight and, in this model, Consensus and Broadcast areequivalent.  We then turn to distributed models with noisy communication channels thathave been studied in the context of some bio-inspired systems. In such models,only one noisy bit is exchanged when a communication channel is establishedbetween two nodes, and so one cannot easily simulate a noiseless protocol byusing error-correcting codes. An $\Omega(\epsilon^{-2} n)$ lower bound on thenumber of rounds needed for Broadcast is proved by Boczkowski et al. [PLOSComp. Bio. 2018] in one such model (noisy uniform PULL, where $\epsilon$ is aparameter 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 anexponential gap between the number of rounds necessary for Consensus versusBroadcast.

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