Document Open Access Logo

A Characterization of Consensus Solvability for Closed Message Adversaries

Authors Kyrill Winkler , Ulrich Schmid , Yoram Moses

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.17.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Author Details

Kyrill Winkler
  • TU Wien, Vienna, Austria
Ulrich Schmid
  • TU Wien, Vienna, Austria
Yoram Moses
  • Technion, Haifa, Israel

Funding

  • Winkler, Kyrill: Austrian Science Fund (FWF): ADynNet (P28182) and RiSE/SHiNE (S11405)

Cite As Get BibTex

Kyrill Winkler, Ulrich Schmid, and Yoram Moses. A Characterization of Consensus Solvability for Closed Message Adversaries. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.OPODIS.2019.17

Abstract

Distributed computations in a synchronous system prone to message loss can be modeled as a game between a (deterministic) distributed algorithm versus an omniscient message adversary. The latter determines, for each round, the directed communication graph that specifies which messages can reach their destination. Message adversary definitions range from oblivious ones, which pick the communication graphs arbitrarily from a given set of candidate graphs, to general message adversaries, which are specified by the set of sequences of communication graphs (called admissible communication patterns) that they may generate. This paper provides a complete characterization of consensus solvability for closed message adversaries, where every inadmissible communication pattern has a finite prefix that makes all (infinite) extensions of this prefix inadmissible. Whereas every oblivious message adversary is closed, there are also closed message adversaries that are not oblivious. We provide a tight non-topological, purely combinatorial characterization theorem, which reduces consensus solvability to a simple condition on prefixes of the communication patterns. Our result not only non-trivially generalizes the known combinatorial characterization of the consensus solvability for oblivious message adversaries by Coulouma, Godard, and Peters (Theor. Comput. Sci., 2015), but also provides the first combinatorial characterization for this important class of message adversaries that is formulated directly on the prefixes of the communication patterns.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Dynamic networks
  • Consensus
  • Message Adversary

Metrics

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

References

  1. Yehuda Afek and Eli Gafni. Asynchrony from Synchrony. In Davide Frey, Michel Raynal, Saswati Sarkar, RudrapatnaK. Shyamasundar, and Prasun Sinha, editors, Distributed Computing and Networking, volume 7730 of Lecture Notes in Computer Science, pages 225-239. Springer Berlin Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-35668-1_16.
  2. Bowen Alpern and Fred B. Schneider. Defining Liveness. Information Processing Letters, 21(4):181-185, 1985. Google Scholar
  3. 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: https://doi.org/10.1016/j.tcs.2018.02.019.
  4. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. IJPEDS, 27(5):387-408, 2012. Google Scholar
  5. Bernadette Charron-Bost and André Schiper. The Heard-Of model: computing in distributed systems with benign faults. Distributed Computing, 22(1):49-71, April 2009. URL: https://doi.org/10.1007/s00446-009-0084-6.
  6. Étienne Coulouma, Emmanuel Godard, and Joseph G. Peters. A characterization of oblivious message adversaries for which Consensus is solvable. Theoretical Computer Science, 584:80-90, 2015. URL: https://doi.org/10.1016/j.tcs.2015.01.024.
  7. Reinhard Diestel. Graph Theory (3rd ed.). Springer, 2006. Google Scholar
  8. Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77-97, January 1987. Google Scholar
  9. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the Presence of Partial Synchrony. Journal of the ACM, 35(2):288-323, April 1988. Google Scholar
  10. Cynthia Dwork and Yoram Moses. Knowledge and common knowledge in a Byzantine environment: Crash failures. Information and Computation, 88(2):156-186, 1990. URL: https://doi.org/10.1016/0890-5401(90)90014-9.
  11. Tristan Fevat and Emmanuel Godard. Minimal Obstructions for the Coordinated Attack Problem and Beyond. In 25th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2011 - Conference Proceedings, pages 1001-1011, 2011. URL: https://doi.org/10.1109/IPDPS.2011.96.
  12. Michael J. Fischer, Nancy A. Lynch, and M. S. Paterson. Impossibility of Distributed Consensus with one Faulty Process. Journal of the ACM, 32(2):374-382, April 1985. Google Scholar
  13. Joseph Y. Halpern and Yoram Moses. Knowledge and common knowledge in a distributed environment. J. ACM, 37(3):549-587, 1990. URL: https://doi.org/10.1145/79147.79161.
  14. Wolfgang Kiess and Martin Mauve. A Survey on Real-world Implementations of Mobile Ad-hoc Networks. Ad Hoc Networks, 5(3):324-339, April 2007. URL: https://doi.org/10.1016/j.adhoc.2005.12.003.
  15. F. Kuhn and R. Oshman. Dynamic networks: Models and algorithms. SIGACT News, 42(1):82-96, 2011. Google Scholar
  16. Fabian Kuhn, Nancy A. Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In STOC, pages 513-522, 2010. Google Scholar
  17. Fabian Kuhn, Rotem Oshman, and Yoram Moses. Coordinated consensus in dynamic networks. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, PODC '11. ACM, 2011. Google Scholar
  18. Franck Legendre, Theus Hossmann, Felix Sutton, and Bernhard Plattner. 30 Years of Wireless Ad Hoc Networking Research: What about Humanitarian and Disaster Relief Solutions? What are we still missing? In International Conference on Wireless Technologies for Humanitarian Relief (ACWR 11), Amrita, India, 2011. IEEE. Google Scholar
  19. Ronit Lubitch and Shlomo Moran. Closed Schedulers: A Novel Technique for Analyzing Asynchronous Protocols. Distributed Computing, 8(4):203-210, June 1995. URL: https://doi.org/10.1007/BF02242738.
  20. Yoram Moses and Sergio Rajsbaum. A Layered Analysis of Consensus. SIAM J. Comput., 31(4):989-1021, 2002. Google Scholar
  21. Thomas Nowak, Ulrich Schmid, and Kyrill Winkler. Topological Characterization of Consensus Under General Message Adversaries. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 218-227, New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3293611.3331624.
  22. Michel Raynal and Julien Stainer. Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors. In Proceedings ACM Symposium on Principles of Distributed Computing, PODC'13, pages 166-175, 2013. Google Scholar
  23. Nicola Santoro and Peter Widmayer. Time is not a healer. In Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS'89), LNCS 349, pages 304-313, Paderborn, Germany, February 1989. Springer-Verlag. Google Scholar
  24. Ulrich Schmid, Bettina Weiss, and Idit Keidar. Impossibility Results and Lower Bounds for Consensus under Link Failures. SIAM Journal on Computing, 38(5):1912-1951, 2009. Google Scholar
  25. Kyrill Winkler, Manfred Schwarz, and Ulrich Schmid. Consensus in rooted dynamic networks with short-lived stability. Distributed Computing, 32(5):443-458, October 2019. URL: https://doi.org/10.1007/s00446-019-00348-0.
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