Document Open Access Logo

Limits for Rumor Spreading in Stochastic Populations

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

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.49.pdf
  • Filesize: 1.17 MB
  • 21 pages

Document Identifiers

Author Details

Lucas Boczkowski
Ofer Feinerman
Amos Korman
Emanuele Natale

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ITCS.2018.49

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.

Subject Classification

Keywords
  • Noisy communication
  • Passive communication
  • Ant recruitment
  • Hypothesis testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. El Gamal a. Young-Han Kim. Network Information Theory. Cambridge University Press, 2011. Google Scholar
  2. M. Abeles. Corticonics: Neural circuits of the cerebral cortex. Cambridge University Press, 1991. Google Scholar
  3. N. Alon, M. Braverman, K. Efremenko, R. Gelles, and B. Haeupler. Reliable communication over highly connected noisy networks. In PODC, pages 165-173, 2016. Google Scholar
  4. F. Amor, P. Ortega, X. Cerdá, and R. Boulay. Cooperative prey-retrieving in the ant cataglyphis floricola: An unusual short-distance recruitment. Insectes Sociaux, 57(1), 2010. URL: https://link.springer.com/article/10.1007/s00040-009-0053-x.
  5. D. Angluin, J. Aspnes, and D. Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87-102, 2008. Google Scholar
  6. D. Angluin, J. Aspnes, M. J. Fischer, and H. Jiang. Self-stabilizing population protocols. TAAS, 3(4), 2008. Google Scholar
  7. J. Aspnes and E. Ruppert. An introduction to population protocols. Bulletin of the EATCS, 93:98-117, 2007. Google Scholar
  8. W. Bialek. Physical limits to sensation and perception. Annual review of biophysics and biophysical chemistry, 16(1):455-478, 1987. Google Scholar
  9. S. Bikhchandani, D. Hirshleifer, and I. Welch. Learning from the behavior of others: Conformity, fads, and informational cascades. J. Economic Perspectives, 12(3):151-170, 1998. Google Scholar
  10. Lucas Boczkowski, Amos Korman, and Emanuele Natale. Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2540-2559. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.168.
  11. A. Cavagna, A. Cimarelli, I. Giardina, G. Parisi, R. Santagati, F. Stefanini, and M. Viale. Scale-free correlations in starling flocks. PNAS, 107(26):11865-11870, 2010. Google Scholar
  12. Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, and Petar Maymounkov. Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 961-970. ACM, 2012. URL: http://dx.doi.org/10.1145/2213977.2214064.
  13. E. Chastain, A. Livnat, C. Papadimitriou, and U. Vazirani. Algorithms, games, and evolution. PNAS, 111(29):10620-10623, 2014. URL: http://dx.doi.org/10.1073/pnas.1406556111.
  14. Bernard Chazelle. Natural algorithms. In SODA, pages 422-431, 2009. Google Scholar
  15. Thomas M Cover and B Gopinath. Open problems in communication and computation. Springer Science &Business Media, 2012. Google Scholar
  16. A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In PODC, 1987. Google Scholar
  17. Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing consensus with the power of two choices. In Rajmohan Rajaraman and Friedhelm Meyer auf der Heide, editors, SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4-6, 2011 (Co-located with FCRC 2011), pages 149-158. ACM, 2011. URL: http://dx.doi.org/10.1145/1989493.1989516.
  18. A. Dornhaus and L. Chittka. Food alert in bumblebees (bombus terrestris): Possible mechanisms and evolutionary implications. Behavioral Ecology and Sociobiology, 50(6):570-576, 2001. Google Scholar
  19. Robert Elsässer and Thomas Sauerwald. On the runtime and robustness of randomized broadcasting. Theor. Comput. Sci., 410(36):3414-3427, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2008.04.017.
  20. O. Feinerman and A. Korman. Theoretical distributed computing meets biology: A review. In ICDCIT, pages 1-18. Springer, 2013. Google Scholar
  21. O. Feinerman, A. Rotem, and E. Moses. Reliable neuronal logic devices from patterned hippocampal cultures. Nature physics, 4(12):967-973, 2008. Google Scholar
  22. Ofer Feinerman, Bernhard Haeupler, and Amos Korman. Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 114-123. ACM, 2014. URL: http://dx.doi.org/10.1145/2611462.2611469.
  23. P. Fraigniaud and E. Natale. Noisy rumor spreading and plurality consensus. In PODC, pages 127-136, 2016. Google Scholar
  24. R. G. Gallager. Finding parity in a simple broadcast network. IEEE Trans. Inf. Theor., 34(2):176-180, 2006. Google Scholar
  25. L. A. Giraldeau, T. J. Valone, and J.J. Templeton. Potential disadvantages of using socially acquired information. Philosophical Transactions of the Royal Society of London B: Biological Sciences, 357(1427):1559-1566, 2002. Google Scholar
  26. Navin Goyal, Guy Kindler, and Michael E. Saks. Lower bounds for the noisy broadcast problem. SIAM J. Comput., 37(6):1806-1841, 2008. URL: http://dx.doi.org/10.1137/060654864.
  27. B. Hölldobler. Recruitment behavior in camponotus socius (hym. formicidae). J. of Comparative Physiology A, 75(2):123-142, 6 1971. Google Scholar
  28. R. M. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking. Randomized rumor spreading. In FOCS, pages 565-574, 2000. Google Scholar
  29. D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In FOCS, pages 482-491. IEEE, 2003. Google Scholar
  30. Amos Korman, Efrat Greenwald, and Ofer Feinerman. Confidence sharing: An economic strategy for efficient information flows in animal groups. PLoS Computational Biology, 10(10), 2014. URL: http://dx.doi.org/10.1371/journal.pcbi.1003862.
  31. S. Marras, R. Batty, and P. Domenici. Information transfer and antipredator maneuvers in schooling herring. Adaptive Behavior, 20(1):44-56, 2012. Google Scholar
  32. Cameron Musco, Hsin-Hao Su, and Nancy A. Lynch. Ant-inspired density estimation via random walks: Extended abstract. In George Giakkoupis, editor, Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 469-478. ACM, 2016. URL: http://dx.doi.org/10.1145/2933057.2933106.
  33. B. Pittel. On spreading a rumor. SIAM J. Appl. Math., 47(1):213-223, 1987. Google Scholar
  34. N. Razin, J.P. Eckmann, and O. Feinerman. Desert ants achieve reliable recruitment across noisy interactions. Journal of the Royal Society Interface; 10(20170079)., 2013. Google Scholar
  35. G. Rieucau and L. A. Giraldeau. Persuasive companions can be wrong: the use of misleading social information in nutmeg mannikins. Behavioral Ecology, pages 1217-1222, 2009. Google Scholar
  36. P. Rigollet. High dimensional statistics. Lecture notes for course 18S997., 2015. Google Scholar
  37. S. B. Rosenthal, C. R. Twomey, A. T. Hartnett, H. S. Wu, and I. D. Couzin. Revealing the hidden networks of interaction in mobile animal groups allows prediction of complex behavioral contagion. PNAS, 112(15):4690-4695, 2015. Google Scholar
  38. J. J. Templeton and Giraldeau L. A. Patch assessment in foraging flocks of european starlings: evidence for the use of public information. Behavioral Ecology, 6(1):65-72, 1995. Google Scholar
  39. J. von Neumann. Probabilistic logics and the synthesis of reliable organisms from unreliable components. Automata Studies, pages 43-98, 1956. Google Scholar
  40. A. Xu and M. Raginsky. Information-theoretic lower bounds for distributed function computation. IEEE Trans. Information Theory, 63(4):2314-2337, 2017. Google Scholar
  41. Y.Afek, N. Alon, O. Barad, E. Hornstein, N. Barkai, and Z. Bar-joseph. A biological solution to a fundamental distributed computing problem. Science, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact