Document Open Access Logo

Fast, Robust, Quantizable Approximate Consensus

Authors Bernadette Charron-Bost, Matthias Függer, Thomas Nowak

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.137.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Bernadette Charron-Bost
Matthias Függer
Thomas Nowak

Cite As Get BibTex

Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Fast, Robust, Quantizable Approximate Consensus. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 137:1-137:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.137

Abstract

We introduce a new class of distributed algorithms for the approximate consensus problem in dynamic rooted networks, which we call amortized averaging algorithms. They are deduced from ordinary averaging algorithms by adding a value-gathering phase before each value update. This results in a drastic drop in decision times, from being exponential in the number n of processes to being polynomial under the assumption that each process knows n. In particular, the amortized midpoint algorithm is the first algorithm that achieves a linear decision time in dynamic rooted networks with an optimal contraction rate of 1/2 at each update step.

We then show robustness of the amortized midpoint algorithm under violation of network assumptions: it gracefully degrades if communication graphs from time to time are non rooted, or under a wrong estimate of the number of processes. Finally, we prove that the amortized midpoint algorithm behaves well if processes can store and send only quantized values, rendering it well-suited for the design of dynamic networked systems. As a corollary we obtain that the 2-set consensus problem is solvable in linear time in any dynamic rooted network model.

Subject Classification

Keywords
  • approximate consensus
  • dynamic networks
  • averaging algorithms

Metrics

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

References

  1. David Angeli and Pierre-Alexandre Bliman. Stability of leaderless discrete-time multi-agent systems. Mathematics of Control, Signals, and Systems, 18(4):293-322, 2006. Google Scholar
  2. Pierre-Alexandre Bliman, Angelia Nedic, and Asuman E. Ozdaglar. Rate of convergence for consensus with delays. In Proceedings of the 47th IEEE Conference on Decision and Control, and the European Control Conference (CDC-ECC), pages 2226-2231. IEEE, New York City, 2008. Google Scholar
  3. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proceedings of the 25th ACM Symposium on Theory of Computing (STOC), pages 91-100. ACM, New York City, 1993. Google Scholar
  4. Ming Cao, A. Stephen Morse, and Brian D. O. Anderson. Reaching a consensus in a dynamically changing environment: a graphical approach. SIAM Journal on Control and Optimization, 47(2):575-600, 2008. Google Scholar
  5. Ming Cao, A. Stephen Morse, and Brian D. O. Anderson. Reaching a consensus in a dynamically changing environment: convergence rates, measurement delays, and asynchronous events. SIAM Journal on Control and Optimization, 47(2):601-623, 2008. Google Scholar
  6. Ming Cao, Daniel A. Spielman, and A. Stephen Morse. A lower bound on convergence of a distributed network consensus algorithm. In Hannes Frey, Xu Li, and Stefan Rührup, editors, Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference (CDC-ECC), pages 2356-2361. IEEE, New York City, 2005. Google Scholar
  7. Bernadette Charron-Bost. Orientation and connectivity based criteria for asymptotic consensus. arXiv:1303.2043v1 [cs.DC], 2013. Google Scholar
  8. Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Approximate consensus in highly dynamic networks: The role of averaging algorithms. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 528-539. Springer, Heidelberg, 2015. Google Scholar
  9. Bernadette Charron-Bost and André Schiper. The Heard-Of model: computing in distributed systems with benign faults. Distributed Computing, 22(1):49-71, 2009. Google Scholar
  10. Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132-158, 1993. Google Scholar
  11. Bernard Chazelle. The convergence of bird flocking. arXiv:0905.4241 [cs.CG], 2009. Google Scholar
  12. Bernard Chazelle. The total s-energy of a multiagent system. SIAM Journal on Control and Optimization, 49(4):1680-1706, 2011. Google Scholar
  13. Roberto De Prisco, Dahlia Malkhi, and Michael K. Reiter. On k-set consensus problems in asynchronous systems. In Proceedings of the 18th ACM Symposium on Principles of Distributed Computing (PODC), pages 257-265. ACM, New York City, 1999. Google Scholar
  14. Roland L. Dobrushin. Central limit theorem for non-stationary Markov chains I. Theory of Probability &Its Applications, 1(1):65-80, 1956. Google Scholar
  15. Paolo Frasca, Ruggero Carli, Fabio Fagnani, and Sandro Zampieri. Average consensus on networks with quantized communication. International Journal of Robust and Nonlinear Control, 19(16):1787-1816, 2009. Google Scholar
  16. R. Hegselmann and U. Krause. Opinion dynamics and bounded confidence models, analysis, and simulation. Journal of artificial societies and social simulation, 5(3):1-33, 2002. Google Scholar
  17. Maurice Herlihy and Nir Shavit. The asynchronous computability theorem for t-resilient tasks. In Proceedings of the 25th ACM Symposium on Theory of Computing (STOC), pages 111-120. ACM, New York City, 1993. Google Scholar
  18. Akshay Kashyap, Tamer Basar, and R. Srikant. Quantized consensus. Automatica, 43(7):1192-1203, 2007. Google Scholar
  19. Renato E. Mirollo and Steven H. Strogatz. Synchronization of pulse-coupled biological oscillators. SIAM Journal on Applied Mathematics, 50(6):1645-1662, December 1990. Google Scholar
  20. Luc Moreau. Stability of multiagent systems with time-dependent communication links. IEEE Transactions on Automatic Control, 50(2):169-182, 2005. Google Scholar
  21. S. Muthukrishnan, Bhaskar Ghosh, and Martin H. Schultz. First- and second-order diffusive methods for rapid, coarse, distributed load balancing. Theory of Computing Systems, 31(4):331-354, 1998. Google Scholar
  22. Angelia Nedic, Alexander Olshevsky, Asuman E. Ozdaglar, and John N. Tsitsiklis. On distributed averaging algorithms and quantization effects. IEEE Transactions on Automatic Control, 54(11):2506-2517, 2009. Google Scholar
  23. Alex Olshevsky. Linear time average consensus on fixed graphs. IFAC-PapersOnLine, 48(22):94-99, 2015. Google Scholar
  24. Alex Olshevsky and John N. Tsitsiklis. Convergence speed in distributed consensus and averaging. SIAM Review, 53(4):747-772, 2011. Google Scholar
  25. Michael E. Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: the topology of public knowledge. In Proceedings of the 25th ACM Symposium on Theory of Computing (STOC), pages 101-110. ACM, New York City, 1993. Google Scholar
  26. Nicola Santoro and Peter Widmayer. Time is not a healer. In B. Monien and R. Cori, editors, Proceedings of the 6th Symposium on Theoretical Aspects of Computer Science (STACS), volume 349 of LNCS, pages 304-313. Springer, Heidelberg, 1989. Google Scholar
  27. Steven H. Strogatz. From Kuramoto to Crawford: Exploring the onset of synchronization in populations of coupled oscillators. Physica D: Nonlinear Phenomena, 143(1-4):1-20, 2000. Google Scholar
  28. Y. Yuan, G.-B. Stan, L. Shi, M. Barahona, and J. Goncalves. Decentralized minimum-time consensus. Automatica, 49(5):1227-1235, 2013. 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