Skip to Main content Skip to Navigation
Journal articles

Limits on reliable information flows through stochastic populations

Abstract : Biological systems can share and collectively process information to yield emergent effects, despite inherent noise in communication. While man-made systems often employ intricate structural solutions to overcome noise, the structure of many biological systems is more amorphous. It is not well understood how communication noise may affect the computational repertoire of such groups. To approach this question we consider the basic collective task of rumor spreading, in which information from few knowledgeable sources must reliably flow into the rest of the population. We study the effect of communication noise on the ability of groups that lack stable structures to efficiently solve this task. We present an impossibility result which strongly restricts reliable rumor spreading in such groups. Namely, we prove that, in the presence of even moderate levels of noise that affect all facets of the communication , no scheme can significantly outperform the trivial one in which agents have to wait until directly interacting with the sources-a process which requires linear time in the population size. Our results imply that in order to achieve efficient rumor spread a system must exhibit either some degree of structural stability or, alternatively, some facet of the communication which is immune to noise. We then corroborate this claim by providing new analyses of experimental data regarding recruitment in Cataglyphis niger desert ants. Finally, in light of our theoretical results, we discuss strategies to overcome noise in other biological systems. Author summary Biological systems must function despite inherent noise in their communication. Systems that enjoy structural stability, such as biological neural networks, could potentially overcome noise using simple redundancy-based procedures. However, when individuals have little control over who they interact with, it is unclear what conditions would prevent runaway error accumulation. This paper takes a general stance to investigate this problem, concentrating on the basic information-dissemination task of rumor spreading. Drawing on a theoretical model, we prove that fast rumor spreading can only be achieved if some part of the communication setting is either stable or reliable. We then provide empirical PLOS Computational Biology | https://doi.org/10.1371/journal.pcbi.
Complete list of metadatas

Cited literature [48 references]  Display  Hide  Download

https://hal.inria.fr/hal-01953778
Contributor : Amos Korman <>
Submitted on : Friday, December 14, 2018 - 5:23:35 PM
Last modification on : Thursday, October 15, 2020 - 2:42:03 PM
Long-term archiving on: : Friday, March 15, 2019 - 5:34:43 PM

File

journal.pcbi.1006195 (1).pdf
Publisher files allowed on an open archive

Identifiers

Citation

Lucas Boczkowski, Emanuele Natale, Ofer Feinerman, Amos Korman. Limits on reliable information flows through stochastic populations. PLoS Computational Biology, Public Library of Science, 2018, 14 (6), ⟨10.1371/journal.pcbi.1006195⟩. ⟨hal-01953778⟩

Share

Metrics

Record views

339

Files downloads

1092