Document Open Access Logo

Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol

Authors Frederik Mallmann-Trenn, Yannic Maus, Dominik Pajak

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.148.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Author Details

Frederik Mallmann-Trenn
  • MIT, CSAIL, Cambridge, MA, US
Yannic Maus
  • Department of Computer Science, Technion, Haifa, Israel,
Dominik Pajak
  • Faculty of Fundamental Problems of Technology, Wroclaw University of Science and Technology, Poland
  • Tooploox, Wroclaw, Poland

Funding

  • Mallmann-Trenn, Frederik: NSF CCF-1461559, CCF-0939370, CCF-18107.
  • Maus, Yannic: ERC Grant No. 336495 (ACDC).

Cite AsGet BibTex

Frederik Mallmann-Trenn, Yannic Maus, and Dominik Pajak. Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 148:1-148:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.148

Abstract

We study a process of averaging in a distributed system with noisy communication. Each of the agents in the system starts with some value and the goal of each agent is to compute the average of all the initial values. In each round, one pair of agents is drawn uniformly at random from the whole population, communicates with each other and each of these two agents updates their local value based on their own value and the received message. The communication is noisy and whenever an agent sends any value v, the receiving agent receives v+N, where N is a zero-mean Gaussian random variable. The two quality measures of interest are (i) the total sum of squares TSS(t), which measures the sum of square distances from the average load to the initial average and (ii) bar{phi}(t), which measures the sum of square distances from the average load to the running average (average at time t). It is known that the simple averaging protocol - in which an agent sends its current value and sets its new value to the average of the received value and its current value - converges eventually to a state where bar{phi}(t) is small. It has been observed that TSS(t), due to the noise, eventually diverges and previous research - mostly in control theory - has focused on showing eventual convergence w.r.t. the running average. We obtain the first probabilistic bounds on the convergence time of bar{phi}(t) and precise bounds on the drift of TSS(t) that show that although TSS(t) eventually diverges, for a wide and interesting range of parameters, TSS(t) stays small for a number of rounds that is polynomial in the number of agents. Our results extend to the synchronous setting and settings where the agents are restricted to discrete values and perform rounding.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • population protocols
  • noisy communication
  • distributed averaging

Metrics

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

Related Versions

References

  1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-Space Trade-offs in Population Protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2560-2579, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.169.
  2. Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-Optimal Majority in Population Protocols. CoRR, abs/1704.04947, 2017. URL: http://arxiv.org/abs/1704.04947.
  3. Dan Alistarh, Rati Gelashvili, and Milan Vojnović. Fast and Exact Majority in Population Protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC '15, pages 47-56, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2767386.2767429.
  4. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, 2006. URL: http://dx.doi.org/10.1007/s00446-005-0138-3.
  5. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. Distributed Computing, 30(4):293-306, 2017. URL: http://dx.doi.org/10.1007/s00446-016-0289-4.
  6. Petra Berenbrink, Andrea E. F. Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, and Emanuele Natale. Ignore or Comply?: On Breaking Symmetry in Consensus. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 335-344, 2017. URL: http://dx.doi.org/10.1145/3087801.3087817.
  7. Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, pages 10:1-10:18, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.DISC.2018.10.
  8. 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, January 11-14, 2018, Cambridge, MA, USA, pages 49:1-49:21, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2018.49.
  9. J. E. Boillat. Load Balancing and Poisson Equation in a Graph. Concurrency: Pract. Exper., 2(4):289-313, November 1990. URL: http://dx.doi.org/10.1002/cpe.4330020403.
  10. Henrik Brumm. Animal communication and noise, volume 2. Springer, 2013. Google Scholar
  11. Jingjing Bu, Maryam Fazel, and Mehran Mesbahi. Accelerated Consensus with Linear Rate of Convergence. In 2018 Annual American Control Conference (ACC), pages 4931-4936. IEEE, 2018. Google Scholar
  12. Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, and Goran Zuzic. Broadcasting in Noisy Radio Networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 33-42, 2017. URL: http://dx.doi.org/10.1145/3087801.3087808.
  13. Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, and Goran Zuzic. Erasure Correction for Noisy Radio Networks. CoRR, abs/1805.04165, 2018. URL: http://arxiv.org/abs/1805.04165.
  14. Biao Chen, Ruixiang Jiang, Teerasit Kasetkasem, and Pramod K Varshney. Channel aware decision fusion in wireless sensor networks. IEEE Transactions on Signal Processing, 52(12):3454-3458, 2004. Google Scholar
  15. Ge Chen, Le Yi Wang, Chen Chen, and George Yin. Critical connectivity and fastest convergence rates of distributed consensus with switching topologies and additive noises. IEEE Transactions on Automatic Control, 62(12):6152-6167, 2017. Google Scholar
  16. John Cook. Upper and lower bounds for the normal distribution function. https://www.johndcook.com/blog/norm-dist-bounds/, 2018. [Online; accessed 6-September-2018].
  17. G. Cybenko. Dynamic Load Balancing for Distributed Memory Multiprocessors. J. Parallel Distrib. Comput., 7(2):279-301, October 1989. URL: http://dx.doi.org/10.1016/0743-7315(89)90021-X.
  18. Morris H DeGroot. Reaching a consensus. Journal of the American Statistical Association, 69(345):118-121, 1974. Google Scholar
  19. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. Distributed Computing, 31(4):257-271, August 2018. URL: http://dx.doi.org/10.1007/s00446-016-0281-z.
  20. Julia T. Ebert, Melvin Gauci, and Radhika Nagpal. Multi-Feature Collective Decision Making in Robot Swarms. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pages 1711-1719, 2018. URL: http://dl.acm.org/citation.cfm?id=3237953.
  21. Julia T. Ebert, Melvin Gauci, and Radhika Nagpal. Multi-Feature Collective Decision Making in Robot Swarms. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pages 1711-1719, 2018. URL: http://dl.acm.org/citation.cfm?id=3237953.
  22. Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Frederik Mallmann-Trenn, and Horst Trinker. Efficient k-Party Voting with Two Choices. CoRR, abs/1602.04667, 2016. URL: http://arxiv.org/abs/1602.04667.
  23. J Alexander Fax and Richard M Murray. Information flow and cooperative control of vehicle formations. IEEE transactions on automatic control, 49(9):1465-1476, 2004. Google Scholar
  24. Ofer Feinerman, Bernhard Haeupler, and Amos Korman. Breathe Before Speaking: Efficient Information Dissemination Despite Noisy, Limited and Anonymous Communication. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, pages 114-123, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2611462.2611469.
  25. Pierre Fraigniaud and Emanuele Natale. Noisy Rumor Spreading and Plurality Consensus. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 127-136, 2016. URL: http://dx.doi.org/10.1145/2933057.2933089.
  26. Simon French. Group consensus probability distributions: A critical survey. University of Manchester. Department of Decision Theory, 1983. Google Scholar
  27. Federica Garin and Luca Schenato. A Survey on Distributed Estimation and Control Applications Using Linear Consensus Algorithms, pages 75-107. Springer London, London, 2010. URL: http://dx.doi.org/10.1007/978-0-85729-033-5_3.
  28. Leszek Gasieniec and Grzegorz Stachowiak. Fast Space Optimal Leader Election in Population Protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2653-2667, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.169.
  29. Leszek Gasieniec, Grzegorz Stachowiak, and Przemyslaw Uznanski. Almost logarithmic-time space optimal leader election in population protocols. CoRR, abs/1802.06867, 2018. URL: http://arxiv.org/abs/1802.06867.
  30. Melvin Gauci, Monica E. Ortiz, Michael Rubenstein, and Radhika Nagpal. Error Cascades in Collective Behavior: A Case Study of the Gradient Algorithm on 1000 Physical Agents. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, São Paulo, Brazil, May 8-12, 2017, pages 1404-1412, 2017. URL: http://dl.acm.org/citation.cfm?id=3091319.
  31. Gustavo L Gilardoni and Murray K Clayton. On reaching a consensus using DeGroot’s iterative pooling. The Annals of Statistics, pages 391-401, 1993. Google Scholar
  32. Seth Gilbert and Calvin Newport. Symmetry Breaking with Noisy Processes. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 273-282, 2017. URL: http://dx.doi.org/10.1145/3087801.3087814.
  33. B. Hajek. Hitting-Time and Occupation-Time Bounds Implied by Drift Analysis with Applications. Advances in Applied Probability, 14(3):502-525, 1982. Google Scholar
  34. Ali Jadbabaie, Jie Lin, and A Stephen Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on automatic control, 48(6):988-1001, 2003. Google Scholar
  35. Varun Kanade, Frederik Mallmann-Trenn, and Thomas Sauerwald. On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 956-965, 2019. URL: http://dx.doi.org/10.1137/1.9781611975482.59.
  36. Soummya Kar and José MF Moura. Distributed Consensus Algorithms in Sensor Networks With Imperfect Communication: Link Failures and Channel Noise. IEEE Transactions on Signal Processing, 57(1):355-369, 2009. Google Scholar
  37. D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 482-491, October 2003. URL: http://dx.doi.org/10.1109/SFCS.2003.1238221.
  38. Adrian Kosowski and Przemyslaw Uznanski. Brief Announcement: Population Protocols Are Fast. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 475-477, 2018. URL: https://dl.acm.org/citation.cfm?id=3212788.
  39. Sara Diana Leonhardt, Florian Menzel, Volker Nehring, and Thomas Schmitt. Ecology and evolution of communication in social insects. Cell, 164(6):1277-1287, 2016. Google Scholar
  40. Zhongkui Li and Jie Chen. Robust consensus of linear feedback protocols over uncertain network graphs. IEEE Transactions on Automatic Control, 62(8):4251-4258, 2017. Google Scholar
  41. Romain Libbrecht, Miguel Corona, Franziska Wende, Dihego O Azevedo, Jose E Serrão, and Laurent Keller. Interplay between insulin signaling, juvenile hormone, and vitellogenin regulates maternal effects on polyphenism in ants. Proceedings of the National Academy of Sciences, 110(27):11050-11055, 2013. Google Scholar
  42. Frederik Mallmann-Trenn, Yannic Maus, and Dominik Pajak. Code of the experiments. URL: https://bitbucket.org/frederikmallmann/noisy-communication-code/.
  43. Frederik Mallmann-Trenn, Yannic Maus, and Dominik Pajak. Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol. arXiv e-prints, page arXiv:1904.10984, April 2019. URL: http://arxiv.org/abs/1904.10984.
  44. Luc Moreau. Stability of multiagent systems with time-dependent communication links. IEEE Transactions on automatic control, 50(2):169-182, 2005. Google Scholar
  45. Angelia Nedić and Ji Liu. On convergence rate of weighted-averaging dynamics for consensus problems. IEEE Transactions on Automatic Control, 62(2):766-781, 2017. Google Scholar
  46. Theodore S Rappaport et al. Wireless communications: principles and practice, volume 2. prentice hall PTR New Jersey, 1996. Google Scholar
  47. Wei Ren and Randal W Beard. Distributed consensus in multi-vehicle cooperative control. Springer, 2008. Google Scholar
  48. Wei Ren, Randal W Beard, and Ella M Atkins. A survey of consensus problems in multi-agent coordination. In American Control Conference, 2005. Proceedings of the 2005, pages 1859-1864. IEEE, 2005. Google Scholar
  49. David Saldana, Amanda Prorok, Shreyas Sundaram, Mario FM Campos, and Vijay Kumar. Resilient consensus for time-varying networks of dynamic agents. In American Control Conference (ACC), 2017, pages 252-258. IEEE, 2017. Google Scholar
  50. Ioannis D Schizas, Alejandro Ribeiro, and Georgios B Giannakis. Consensus-based distributed parameter estimation in ad hoc wireless sensor networks with noisy links. In Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, volume 2, pages II-849. IEEE, 2007. Google Scholar
  51. Slobodan N Simić and Shankar Sastry. Distributed environmental monitoring using random sensor networks. In Information Processing in Sensor Networks, pages 582-592. Springer, 2003. Google Scholar
  52. Behrouz Touri and Angelia Nedic. Distributed consensus over network with noisy links. In Information Fusion, 2009. FUSION'09. 12th International Conference on, pages 146-154. IEEE, 2009. Google Scholar
  53. Lin Xiao and S. Boyd. Fast linear iterations for distributed averaging. In 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475), volume 5, pages 4997-5002 Vol.5, December 2003. URL: http://dx.doi.org/10.1109/CDC.2003.1272421.
  54. Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems &Control Letters, 53(1):65-78, 2004. Google Scholar
  55. Lin Xiao, Stephen Boyd, and Seung-Jean Kim. Distributed Average Consensus with Least-mean-square Deviation. J. Parallel Distrib. Comput., 67(1):33-46, January 2007. URL: http://dx.doi.org/10.1016/j.jpdc.2006.08.010.
  56. Lin Xiao, Stephen Boyd, and Sanjay Lall. A scheme for robust distributed sensor fusion based on average consensus. In Information Processing in Sensor Networks, 2005. IPSN 2005. Fourth International Symposium on, pages 63-70. IEEE, 2005. 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 Imprint Privacy Contact