Document Open Access Logo

Effects of Topology Knowledge and Relay Depth on Asynchronous Appoximate Consensus

Authors Dimitris Sakavalas, Lewis Tseng, Nitin H. Vaidya

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.14.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Author Details

Dimitris Sakavalas
  • Boston College, USA
Lewis Tseng
  • Boston College, USA
Nitin H. Vaidya
  • Georgetown University, USA

Funding

  • Vaidya, Nitin H.: This research is supported in part by National Science Foundation awards 1421918. Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not necessarily reflect the views of the funding agencies or the U.S. government.

Cite As Get BibTex

Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya. Effects of Topology Knowledge and Relay Depth on Asynchronous Appoximate Consensus. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.OPODIS.2018.14

Abstract

Consider a point-to-point message-passing network. We are interested in the asynchronous crash-tolerant consensus problem in incomplete networks. We study the feasibility and efficiency of approximate consensus under different restrictions on topology knowledge and the relay depth, i.e., the maximum number of hops any message can be relayed. These two constraints are common in large-scale networks, and are used to avoid memory overload and network congestion respectively. Specifically, for positive integer values k and k', we consider that each node knows all its neighbors of at most k-hop distance (k-hop topology knowledge), and the relay depth is k'. We consider both directed and undirected graphs. More concretely, we answer the following question in asynchronous systems: "What is a tight condition on the underlying communication graphs for achieving approximate consensus if each node has only a k-hop topology knowledge and relay depth k'?" To prove that the necessary conditions presented in the paper are also sufficient, we have developed algorithms that achieve consensus in graphs satisfying those conditions:
- The first class of algorithms requires k-hop topology knowledge and relay depth k. Unlike prior algorithms, these algorithms do not flood the network, and each node does not need the full topology knowledge. We show how the convergence time and the message complexity of those algorithms is affected by k, providing the respective upper bounds. 
- The second set of algorithms requires only one-hop neighborhood knowledge, i.e., immediate incoming and outgoing neighbors, but needs to flood the network (i.e., relay depth is n, where n is the number of nodes). One result that may be of independent interest is a topology discovery mechanism to learn and "estimate" the topology in asynchronous directed networks with crash faults.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Fault-tolerant network topologies
Keywords
  • Asynchrony
  • crash
  • consensus
  • incomplete graphs
  • topology knowledge

Metrics

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

Related Versions

References

  1. EduardoA.P. Alchieri, AlyssonNeves Bessani, Joni Silva Fraga, and Fabíola Greve. Byzantine Consensus with Unknown Participants. In Principles of Distributed Systems, volume 5401 of Lecture Notes in Computer Science, pages 22-40. Springer Berlin Heidelberg, 2008. URL: http://dx.doi.org/10.1007/978-3-540-92221-6_4.
  2. John Augustine, Gopal Pandurangan, and Peter Robinson. Fast Byzantine Agreement in Dynamic Networks. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC '13, pages 74-83, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2484239.2484275.
  3. Piyush Bansal, Prasant Gopal, Anuj Gupta, Kannan Srinathan, and Pranav Kumar Vasishta. Byzantine agreement using partial authentication. In Proceedings of the 25th international conference on Distributed computing, DISC'11, pages 389-403, Berlin, Heidelberg, 2011. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=2075029.2075079.
  4. Martin Biely, Peter Robinson, and Ulrich Schmid. Agreement in Directed Dynamic Networks. In Guy Even and Magnús M. Halldórsson, editors, Structural Information and Communication Complexity, pages 73-84, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  5. Martin Biely, Peter Robinson, Ulrich Schmid, Manfred Schwarz, and Kyrill Winkler. Gracefully Degrading Consensus and k-Set Agreement in Directed Dynamic Networks. In Ahmed Bouajjani and Hugues Fauconnier, editors, Networked Systems, pages 109-124, Cham, 2015. Springer International Publishing. Google Scholar
  6. Martin Biely, Peter Robinson, Ulrich Schmid, Manfred Schwarz, and Kyrill Winkler. Gracefully degrading consensus and k-set agreement in directed dynamic networks. Theoretical Computer Science, 726:41-77, 2018. URL: http://dx.doi.org/10.1016/j.tcs.2018.02.019.
  7. Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Approximate Consensus in Highly Dynamic Networks. CoRR, abs/1408.0620, 2014. URL: http://arxiv.org/abs/1408.0620,
  8. Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak. Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms. In Proceedings, Part II, of the 42Nd International Colloquium on Automata, Languages, and Programming - Volume 9135, ICALP 2015, pages 528-539, New York, NY, USA, 2015. Springer-Verlag New York, Inc. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_42.
  9. Étienne Coulouma and Emmanuel Godard. A Characterization of Dynamic Networks Where Consensus Is Solvable. In Thomas Moscibroda and Adele A. Rescigno, editors, Structural Information and Communication Complexity, pages 24-35, Cham, 2013. Springer International Publishing. Google Scholar
  10. S. M. Dibaji, H. Ishii, and R. Tempo. Resilient Randomized Quantized Consensus. IEEE Transactions on Automatic Control, PP(99):1-1, 2017. URL: http://dx.doi.org/10.1109/TAC.2017.2771363.
  11. Danny Dolev. The Byzantine Generals Strike Again. Journal of Algorithms, 3(1), March 1982. Google Scholar
  12. Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. J. ACM, 33:499-516, May 1986. URL: http://dx.doi.org/10.1145/5925.5931.
  13. Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. In Proceedings of the fourth annual ACM symposium on Principles of distributed computing, PODC '85, pages 59-70, New York, NY, USA, 1985. ACM. URL: http://dx.doi.org/10.1145/323596.323602.
  14. Heath LeBlanc, Haotian Zhang, Xenofon D. Koutsoukos, and Shreyas Sundaram. Resilient Asymptotic Consensus in Robust Networks. IEEE Journal on Selected Areas in Communications, 31(4), 2013. URL: http://dx.doi.org/10.1109/JSAC.2013.130413.
  15. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996. Google Scholar
  16. Alexandre Maurer, Sébastien Tixeuil, and Xavier Défago. Reliable Communication in a Dynamic Network in the Presence of Byzantine Faults. CoRR, abs/1402.0121, 2014. URL: http://arxiv.org/abs/1402.0121,
  17. Mikhail Nesterenko and Sébastien Tixeuil. Discovering Network Topology in the Presence of Byzantine Faults. In Structural Information and Communication Complexity, pages 212-226, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  18. Aris Pagourtzis, Giorgos Panagiotakos, and Dimitris Sakavalas. Reliable broadcast with respect to topology knowledge. Distributed Computing, 30(2):87-102, 2017. URL: http://dx.doi.org/10.1007/s00446-016-0279-6.
  19. Aris Pagourtzis, Giorgos Panagiotakos, and Dimitris Sakavalas. Reliable Communication via Semilattice Properties of Partial Knowledge. In Ralf Klasing and Marc Zeitoun, editors, Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings, volume 10472 of Lecture Notes in Computer Science, pages 367-380. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-662-55751-8_29.
  20. M. Pease, R. Shostak, and L. Lamport. Reaching Agreement in the Presence of Faults. J. ACM, 27(2):228-234, April 1980. URL: http://dx.doi.org/10.1145/322186.322188.
  21. Dimitris Sakavalas, Lewis Tseng, and Nitin H. Vaidya. Asynchronous Crash-Tolerant Approximate Consensus in Directed Graphs: Topology Knowledge. CoRR, abs/1803.04513, 2018. URL: http://arxiv.org/abs/1803.04513.
  22. Lili Su and Nitin Vaidya. Reaching Approximate Byzantine Consensus with Multi-hop Communication. In Andrzej Pelc and Alexander A. Schwarzmann, editors, Stabilization, Safety, and Security of Distributed Systems, volume 9212 of Lecture Notes in Computer Science, pages 21-35. Springer International Publishing, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21741-3_2.
  23. Lewis Tseng and Nitin H. Vaidya. Fault-Tolerant Consensus in Directed Graphs. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC '15, pages 451-460, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2767386.2767399.
  24. Lewis Tseng and Nitin H. Vaidya. Iterative approximate Byzantine consensus under a generalized fault model. In In International Conference on Distributed Computing and Networking (ICDCN), January 2013. Google Scholar
  25. Nitin H. Vaidya, Lewis Tseng, and Guanfeng Liang. Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs. In Proceedings of the thirty-first annual ACM symposium on Principles of distributed computing, PODC '12. ACM, 2012. Google Scholar
  26. H. Zhang and S. Sundaram. Robustness of distributed algorithms to locally bounded adversaries. In Proceedings of ACC 2012, the 31st American Control Conference, 2012. 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