Document Open Access Logo

Computing Outside the Box: Average Consensus over Dynamic Networks

Authors Bernadette Charron-Bost, Patrick Lambein-Monette

PDF
Thumbnail PDF

File

LIPIcs.SAND.2022.10.pdf
  • Filesize: 0.83 MB
  • 16 pages

Document Identifiers

Author Details

Bernadette Charron-Bost
  • Département d'informatique de l'ENS, ENS, CNRS, PSL University, Paris, France
Patrick Lambein-Monette
  • Université Paris Cité, CNRS, IRIF, F-75013, Paris, France

Acknowledgements

Patrick Lambein-Monette would like to thank his doctoral jury for stimulating discussions and remarks regarding previous versions of this material.

Cite As Get BibTex

Bernadette Charron-Bost and Patrick Lambein-Monette. Computing Outside the Box: Average Consensus over Dynamic Networks. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SAND.2022.10

Abstract

Networked systems of autonomous agents, and applications thereof, often rely on the control primitive of average consensus, where the agents are to compute the average of private initial values. To provide reliable services that are easy to deploy, average consensus should continue to operate when the network is subject to frequent and unpredictable change, and should mobilize few computational resources, so that deterministic, low powered, and anonymous agents can partake in the network.
In this stringent adversarial context, we investigate the implementation of average consensus by distributed algorithms over networks with bidirectional, but potentially short-lived, communication links. Inspired by convex recurrence rules for multi-agent systems, and the Metropolis average consensus rule in particular, we design a deterministic distributed algorithm that achieves asymptotic average consensus, which we show to operate in polynomial time in a synchronous temporal model.
The algorithm is easy to implement, has low space and computational complexity, and is fully distributed, requiring neither symmetry-breaking devices like unique identifiers, nor global control or knowledge of the network. In the fully decentralized model that we adopt, to our knowledge, no other distributed average consensus algorithm has a better temporal complexity.
Our approach distinguishes itself from classical convex recurrence rules in that the agent’s values may sometimes leave their previous convex hull. As a consequence, our convergence bound requires a subtle analysis, despite the syntactic simplicity of our algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Computing methodologies → Distributed artificial intelligence
  • Networks → Sensor networks
  • Networks → Mobile networks
  • Networks → Network dynamics
Keywords
  • average consensus
  • dynamic networks
  • distributed algorithms
  • iterated averaging
  • Metropolis

Metrics

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

Related Versions

References

  1. Dana Angluin. Local and global properties in networks of processors (extended abstract). In R. E. Miller, S Ginsburg, W. A. Burkhard, and R. J. Lipton, editors, Proceedings of the twelfth annual ACM symposium on Theory of computing - STOC '80, pages 82-93. ACM Press, 1980. URL: https://doi.org/10.1145/800141.804655.
  2. Paolo Boldi and Sebastiano Vigna. An effective characterization of computability in anonymous networks. In Jennifer Welch, editor, DISC 2001: Distributed Computing, volume 2180 of Lecture Notes in Computer Science, pages 33-47. Springer Berlin Heidelberg, 2001. URL: https://doi.org/10.1007/3-540-45414-4_3.
  3. Florence Bénézit, Vincent D. Blondel, Patrick Thiran, John N. Tsitsiklis, and Martin Vetterli. Weighted gossip: Distributed averaging using non-doubly stochastic matrices. In 2010 IEEE International Symposium on Information Theory, pages 1753-1757, June 2010. URL: https://doi.org/10.1109/ISIT.2010.5513273.
  4. Themistoklis Charalambous, Michael G. Rabbat, Mikael Johansson, and Christoforos N. Hadjicostis. Distributed Finite-Time Computation of Digraph Parameters: Left-Eigenvector, Out-Degree and Spectrum. IEEE Transactions on Control of Network Systems, 3(2):137-148, 2016. URL: https://doi.org/10.1109/TCNS.2015.2428411.
  5. Bernadette Charron-Bost. Geometric Bounds for Convergence Rates of Averaging Algorithms. Information and Computation, 2022. (To appear). URL: http://arxiv.org/abs/2007.04837.
  6. Bernadette Charron-Bost and Patrick Lambein-Monette. Randomization and quantization for average consensus. In 2018 IEEE Conference on Decision and Control (CDC), pages 3716-3721. IEEE, December 2018. URL: https://doi.org/10.1109/CDC.2018.8619817.
  7. Samprit Chatterjee and Eugene Seneta. Towards Consensus: Some Convergence Theorems on Repeated Averaging. Journal of Applied Probability, 14(1):89-97, 1977. URL: https://doi.org/10.2307/3213262.
  8. George Cybenko. Dynamic load balancing for distributed memory multiprocessors. Journal of Parallel and Distributed Computing, 7(2):279-301, 1989. URL: https://doi.org/10.1016/0743-7315(89)90021-X.
  9. Louis Penet de Monterno, Bernadette Charron-Bost, and Stephan Merz. Synchronization modulo k in dynamic networks. In Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, SSS 2021, Virtual Event, November 17-20, 2021, Proceedings, volume 13046 of Lecture Notes in Computer Science, pages 425-439. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-91081-5_28.
  10. Morris H. DeGroot. Reaching a Consensus. Journal of the American Statistical Association, 69(345):118-121, 1974. URL: https://doi.org/10.2307/2285509.
  11. Persi Diaconis and Daniel Stroock. Geometric bounds for eigenvalues of markov chains. The Annals of Applied Probability, 1(1):36-61, February 1991. URL: https://doi.org/10.1214/aoap/1177005980.
  12. Michael Dinitz, Jeremy Fineman, Seth Gilbert, and Calvin Newport. Load balancing with bounded convergence in dynamic networks. In IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, pages 1-9, Atlanta, GA, USA, 2017. IEEE. URL: https://doi.org/10.1109/INFOCOM.2017.8057000.
  13. Alejandro D. Dominguez-Garcia, Stanton T. Cady, and Christoforos N. Hadjicostis. Decentralized optimal dispatch of distributed energy resources. In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pages 3688-3693. IEEE, December 2012. ZSCC: 0000166. URL: https://doi.org/10/ggd8nx.
  14. Balazs Gerencser and Julien M. Hendrickx. Push-sum with transmission failures. IEEE Transactions on Automatic Control, 64(3):1019-1033, March 2019. URL: https://doi.org/10.1109/TAC.2018.2836861.
  15. Wilfred Keith Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1):97-109, April 1970. URL: https://doi.org/10.1093/biomet/57.1.97.
  16. Julien M. Hendrickx, Alex Olshevsky, and John N. Tsitsiklis. Distributed anonymous discrete function computation. IEEE Transactions on Automatic Control, 56(10):2276-2289, October 2011. URL: https://doi.org/10.1109/TAC.2011.2163874.
  17. Julien M. Hendrickx and John N. Tsitsiklis. Fundamental limitations for anonymous distributed systems with broadcast communications. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 9-16. IEEE, September 2015. URL: https://doi.org/10.1109/ALLERTON.2015.7446980.
  18. 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. URL: https://doi.org/10.1109/TAC.2003.812781.
  19. David Kempe, Alin Dobra, and Johannes 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: https://doi.org/10/fcmmkg.
  20. Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the 42nd ACM symposium on Theory of computing - STOC '10, page 513. ACM Press, 2010. URL: https://doi.org/10.1145/1806689.1806760.
  21. Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6):1087-1092, March 1953. URL: https://doi.org/10.2172/4390578.
  22. Luc Moreau. Stability of multiagent systems with time-dependent communication links. IEEE Transactions on Automatic Control, 50(2):169-182, 2005. URL: https://doi.org/10.1109/TAC.2004.841888.
  23. Damon Mosk-Aoyama and Devavrat Shah. Computing separable functions via gossip. In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, PODC '06, pages 113-122. ACM Press, July 2006. URL: https://doi.org/10.1145/1146381.1146401.
  24. Angelia Nedić and Alex Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60(3):601-615, 2014. URL: https://doi.org/10/f63582.
  25. Angelia Nedić, Alex Olshevsky, Asuman Ozdaglar, and John N. Tsitsiklis. On Distributed Averaging Algorithms and Quantization Effects. IEEE Transactions on Automatic Control, 54(11):2506-2517, 2009. URL: https://doi.org/10.1109/TAC.2009.2031203.
  26. Angelia Nedić, Alex Olshevsky, and Michael G. Rabbat. Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization. Proceedings of the IEEE, 106(5):953-976, 2018. URL: https://doi.org/10.1109/JPROC.2018.2817461.
  27. Reza Olfati-Saber and Jeff S. Shamma. Consensus filters for sensor networks and distributed sensor fusion. In Proceedings of the 44th IEEE Conference on Decision and Control, pages 6698-6703, December 2005. URL: https://doi.org/10/c338d4.
  28. Alex Olshevsky. Linear Time Average Consensus and Distributed Optimization on Fixed Graphs. SIAM Journal on Control and Optimization, 55(6):3990-4014, 2017. URL: https://doi.org/10.1137/16M1076629.
  29. Alex Olshevsky and John N. Tsitsiklis. Convergence Speed in Distributed Consensus and Averaging. SIAM Review, 53(4):747-772, 2011. URL: https://doi.org/10.1137/110837462.
  30. W. Ren. Consensus strategies for cooperative control of vehicle formations. IET Control Theory & Applications, 1(2):505-512, 2007. URL: https://doi.org/10.1049/iet-cta:20050401.
  31. Shreyas Sundaram and Christoforos N. Hadjicostis. Finite-Time Distributed Consensus in Graphs with Time-Invariant Topologies. In 2007 American Control Conference, pages 711-716, 2007. URL: https://doi.org/10.1109/ACC.2007.4282726.
  32. Ichiro Suzuki and Masafumi Yamashita. Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. SIAM Journal on Computing, 28(4):1347-1363, 1999. URL: https://doi.org/10.1137/S009753979628292X.
  33. John N. Tsitsiklis. Problems in Decentralized Decision Making and Computation. PhD thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, 1984. URL: https://www.mit.edu/~jnt/Papers/PhD-84-jnt.pdf.
  34. John N. Tsitsiklis, Dimitri P. Bertsekas, and Michael Athans. Distributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms. IEEE Transactions on Automatic Control, 31(9):803-812, 1986. URL: https://doi.org/10.1109/TAC.1986.1104412.
  35. Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004. URL: https://doi.org/10.1016/j.sysconle.2004.02.022.
  36. Lin Xiao, Stephen Boyd, and Seung-Jean Kim. Distributed average consensus with least-mean-square deviation. Journal of Parallel and Distributed Computing, 67(1):33-46, 2007. URL: https://doi.org/10/bmq2t4.
  37. Lin Xiao, Stephen Boyd, and Sanjay Lall. A Scheme for Robust Distributed Sensor Fusion Based on Average Consensus. In Fourth International Symposium on Information Processing in Sensor Networks, 2005., pages 63-70, Los Angeles, CA, USA, 2005. IEEE. URL: https://doi.org/10.1109/IPSN.2005.1440896.
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