1 Search Results for "Feinerman, Ofer"

Document

DOI: 10.4230/LIPIcs.ITCS.2018.49

Limits for Rumor Spreading in Stochastic Populations

Authors: Lucas Boczkowski, Ofer Feinerman, Amos Korman, and Emanuele Natale

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

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. In order to study the effect of communication noise on the ability of groups that lack stable structures to efficiently solve this task, we consider a noisy version of the uniform PULL model. We prove a lower bound which implies 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. Our results thus show an exponential separation between the uniform PUSH and PULL communication models in the presence of noise. Such separation may be interpreted as suggesting that, in order to achieve efficient rumor spreading, a system must exhibit either some degree of structural stability or, alternatively, some facet of the communication which is immune to noise. We corroborate our theoretical findings with a new analysis of experimental data regarding recruitment in Cataglyphis Niger desert ants.

Cite as

Lucas Boczkowski, Ofer Feinerman, Amos Korman, and Emanuele Natale. Limits for Rumor Spreading in Stochastic Populations. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boczkowski_et_al:LIPIcs.ITCS.2018.49,
  author =	{Boczkowski, Lucas and Feinerman, Ofer and Korman, Amos and Natale, Emanuele},
  title =	{{Limits for Rumor Spreading in Stochastic Populations}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{49:1--49:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.49},
  URN =		{urn:nbn:de:0030-drops-83207},
  doi =		{10.4230/LIPIcs.ITCS.2018.49},
  annote =	{Keywords: Noisy communication, Passive communication, Ant recruitment, Hypothesis testing}
}

Refine by Author
1 Boczkowski, Lucas
1 Feinerman, Ofer
1 Korman, Amos
1 Natale, Emanuele

Refine by Classification

Refine by Keyword
1 Ant recruitment
1 Hypothesis testing
1 Noisy communication
1 Passive communication

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Feinerman, Ofer"

Limits for Rumor Spreading in Stochastic Populations

Abstract

Cite as

Thanks for your feedback!

Could not send message