Noisy rumor spreading and plurality consensus

Abstract : Error-correcting codes are efficient methods for handling noisy communication channels in the context of technological networks. However, such elaborate methods differ a lot from the unsophisticated way biological entities are supposed to communicate. Yet, it has been recently shown by Feinerman, Haeupler, and Korman [PODC 2014] that complex coordination tasks such as rumor spreading and majority consensus can plausibly be achieved in biological systems subject to noisy communication channels, where every message transferred through a channel remains intact with small probability 1 2 + , without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has nevertheless been established only in the case of 2-valued opinions: rumor spreading aims at broadcasting a single-bit opinion to all nodes, and majority consensus aims at leading all nodes to adopt the single-bit opinion that was initially present in the system with (relative) majority. In this paper, we extend this previous work to k-valued opinions, for any constant k ≥ 2. Our extension requires to address a series of important issues, some conceptual, others technical. We had to entirely revisit the notion of noise, for handling channels carrying k-valued messages. In fact, we precisely characterize the type of noise patterns for which plurality consensus is solvable. Also, a key result employed in the bivalued case by Feinerman et al. is an estimate of the probability of observing the most frequent opinion from observing the mode of a small sample. We generalize this result to the multivalued case by providing a new analytical proof for the bivalued case that is amenable to be extended, by induction, and that is of independent interest.
Complete list of metadatas

Cited literature [44 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02001830
Contributor : Emanuele Natale <>
Submitted on : Thursday, July 11, 2019 - 5:59:01 PM
Last modification on : Saturday, July 20, 2019 - 3:58:01 PM

File

Noisy_Plurality_Consensus.pdf
Files produced by the author(s)

Identifiers

Citation

Pierre Fraigniaud, Emanuele Natale. Noisy rumor spreading and plurality consensus. Distributed Computing, Springer Verlag, 2018, ⟨10.1007/s00446-018-0335-5⟩. ⟨hal-02001830⟩

Share

Metrics

Record views

180

Files downloads

31