Document Open Access Logo

Fast Multidimensional Asymptotic and Approximate Consensus

Authors Matthias Függer, Thomas Nowak

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.27.pdf
  • Filesize: 466 kB
  • 16 pages

Document Identifiers

Author Details

Matthias Függer
  • CNRS, LSV, ENS Paris-Saclay, Université Paris-Saclay, and Inria, France
Thomas Nowak
  • Université Paris-Sud, France

Funding

This research was partially supported by the CNRS project PEPS DEMO and the Institut Farman.

Cite AsGet BibTex

Matthias Függer and Thomas Nowak. Fast Multidimensional Asymptotic and Approximate Consensus. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.27

Abstract

We study the problems of asymptotic and approximate consensus in which agents have to get their values arbitrarily close to each others' inside the convex hull of initial values, either without or with an explicit decision by the agents. In particular, we are concerned with the case of multidimensional data, i.e., the agents' values are d-dimensional vectors. We introduce two new algorithms for dynamic networks, subsuming classical failure models like asynchronous message passing systems with Byzantine agents. The algorithms are the first to have a contraction rate and time complexity independent of the dimension d. In particular, we improve the time complexity from the previously fastest approximate consensus algorithm in asynchronous message passing systems with Byzantine faults by Mendes et al. [Distrib. Comput. 28] from Omega(d log (d Delta)/epsilon) to O(log Delta/epsilon), where Delta is the initial and epsilon is the terminal diameter of the set of vectors of correct agents.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • asymptotic consensus
  • approximate consensus
  • multidimensional data
  • dynamic networks
  • Byzantine processes

Metrics

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

References

  1. Ittai Abraham, Yonatan Amit, and Danny Dolev. Optimal resilience asynchronous approximate agreement. In Teruo Higashino, editor, 8th International Conference on Principles of Distributed Systems (OPODIS 2004), volume 3544 of Lecture Notes in Computer Science, pages 229-239. Springer, Heidelberg, 2005. Google Scholar
  2. David Angeli and Pierre-Alexandre Bliman. Stability of leaderless discrete-time multi-agent systems. MCSS, 18(4):293-322, 2006. Google Scholar
  3. Zohir Bouzid, Maria Gradinariu Potop-Butucaru, and Sébastien Tixeuil. Optimal Byzantine-resilient convergence in uni-dimensional robot networks. Theoretical Computer Science, 411(34-36):3154-3168, 2010. Google Scholar
  4. Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004. 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 J. Control Optim., 47(2):601-623, 2008. Google Scholar
  6. 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, ICALP15, pages 528-539, 2015. Google Scholar
  7. Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Fast, robust, quantizable approximate consensus. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP16, pages 137:1-137:14, 2016. Google Scholar
  8. Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Multidimensional asymptotic consensus in dynamic networks. CoRR, abs/1611.02496, 2016. URL: http://arxiv.org/abs/1611.02496.
  9. Bernadette Charron-Bost and André Schiper. The Heard-Of model: computing in distributed systems with benign faults. Distrib. Comput., 22(1):49-71, 2009. Google Scholar
  10. Bernard Chazelle. The total s-energy of a multiagent system. SIAM Journal on Control and Optimization, 49(4):1680-1706, 2011. Google Scholar
  11. Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Solving the robots gathering problem. In International Colloquium on Automata, Languages, and Programming, pages 1181-1196. Springer, 2003. Google Scholar
  12. Ludwig Danzer, Branko Grünbaum, and Victor Klee. Helly’s theorem and its relatives. In Victor Klee, editor, Convexity, volume 7 of Proceedings of Symposia in Pure Mathematics, pages 101-180. AMS, Providence, 1963. Google Scholar
  13. Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. jacm, 33(2):499-516, 1986. Google Scholar
  14. Alan D. Fekete. Asymptotically optimal algorithms for approximate agreement. Distrib. Comput., 4(1):9-29, 1990. Google Scholar
  15. Matthias Függer, Thomas Nowak, and Manfred Schwarz. Tight bounds for asymptotic and approximate consensus. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, pages 325-334, 2018. Google Scholar
  16. Qun Li and Daniela Rus. Global clock synchronization in sensor networks. IEEE Transactions on Computers, 55(2):214-226, 2006. Google Scholar
  17. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, San Francisco, CA, 1996. Google Scholar
  18. Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K. Garg. Multidimensional agreement in Byzantine systems. Distributed Computing, 28:423-441, 2015. Google Scholar
  19. Luc Moreau. Stability of multiagent systems with time-dependent communication links. IEEE Transactions on Automatic Control, 50(2):169-182, 2005. Google Scholar
  20. Reza Olfati-Saber and Richard M Murray. Consensus problems in networks of agents with switching topology and time-delays. IEEE Transactions on automatic control, 49(9):1520-1533, 2004. Google Scholar
  21. Luis A. Rademacher. Approximating the centroid is hard. In Proceedings of the Twenty-third Annual Symposium on Computational Geometry, pages 302-305. ACM, 2007. Google Scholar
  22. Nicola Santoro and Peter Widmayer. Time is not a healer. In B. Monien and R. Cori, editors, 6th Symposium on Theoretical Aspects of Computer Science, volume 349 of LNCS, pages 304-313. Springer, Heidelberg, 1989. Google Scholar
  23. Fred B Schneider. Understanding protocols for Byzantine clock synchronization. Technical report, Cornell University, 1987. Google Scholar
  24. Jennifer Lundelius Welch and Nancy Lynch. A new fault-tolerant algorithm for clock synchronization. Information and computation, 77(1):1-36, 1988. 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