Characterizing Asynchronous Message-Passing Models Through Rounds

Authors Adam Shimi, Aurélie Hurault, Philippe Quéinnec



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.18.pdf
  • Filesize: 475 kB
  • 17 pages

Document Identifiers

Author Details

Adam Shimi
  • IRIT - Université de Toulouse, 2 rue Camichel, F-31000 Toulouse, France, http://www.irit.fr
Aurélie Hurault
  • IRIT - Université de Toulouse, 2 rue Camichel, F-31000 Toulouse, France, http://www.irit.fr
Philippe Quéinnec
  • IRIT - Université de Toulouse, 2 rue Camichel, F-31000 Toulouse, France, http://www.irit.fr

Cite AsGet BibTex

Adam Shimi, Aurélie Hurault, and Philippe Quéinnec. Characterizing Asynchronous Message-Passing Models Through Rounds. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.OPODIS.2018.18

Abstract

Message-passing models of distributed computing vary along numerous dimensions: degree of synchrony, kind of faults, number of faults... Unfortunately, the sheer number of models and their subtle distinctions hinder our ability to design a general theory of message-passing models. One way out of this conundrum restricts communication to proceed by round. A great variety of message-passing models can then be captured in the Heard-Of model, through predicates on the messages sent in a round and received during or before this round. Then, the issue is to find the most accurate Heard-Of predicate to capture a given model. This is straightforward in synchronous models, because waiting for the upper bound on communication delay ensures that all available messages are received, while not waiting forever. On the other hand, asynchrony allows unbounded message delays. Is there nonetheless a meaningful characterization of asynchronous models by a Heard-Of predicate? We formalize this characterization by introducing Delivered collections: the collections of all messages delivered at each round, whether late or not. Predicates on Delivered collections capture message-passing models. The question is to determine which Heard-Of predicates can be generated by a given Delivered predicate. We answer this by formalizing strategies for when to change round. Thanks to a partial order on these strategies, we also find the "best" strategy for multiple models, where "best" intuitively means it waits for as many messages as possible while not waiting forever. Finally, a strategy for changing round that never blocks a process forever implements a Heard-Of predicate. This allows us to translate the order on strategies into an order on Heard-Of predicates. The characterizing predicate for a model is then the greatest element for that order, if it exists.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • Message-passing
  • Asynchronous Rounds
  • Dominant Strategies
  • Failures

Metrics

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

References

  1. Eshrat Arjomandi, Michael J. Fischer, and Nancy A. Lynch. A Difference in Efficiency Between Synchronous and Asynchronous Systems. In Thirteenth Annual ACM Symposium on Theory of Computing, STOC '81, pages 128-132, 1981. URL: http://dx.doi.org/10.1145/800076.802466.
  2. Elizabeth Borowsky and Eli Gafni. Generalized FLP Impossibility Result for T-resilient Asynchronous Computations. In Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC '93, pages 91-100. ACM, 1993. URL: http://dx.doi.org/10.1145/167088.167119.
  3. Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The Weakest Failure Detector for Solving Consensus. J. ACM, 43(4):685-722, July 1996. URL: http://dx.doi.org/10.1145/234533.234549.
  4. 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: http://dx.doi.org/10.1007/s00446-009-0084-6.
  5. Cezara Drăgoi, Thomas A. Henzinger, and Damien Zufferey. PSync: A Partially Synchronous Language for Fault-tolerant Distributed Algorithms. In 43rd Symposium on Principles of Programming Languages, pages 400-415, 2016. URL: http://dx.doi.org/10.1145/2837614.2837650.
  6. Michael J. Fischer and Nancy A. Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, 14(4):183-186, 1982. URL: http://dx.doi.org/10.1016/0020-0190(82)90033-3.
  7. Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a Complexity Theory for Local Distributed Computing. J. ACM, 60(5):35:1-35:26, October 2013. URL: http://dx.doi.org/10.1145/2499228.
  8. Eli Gafni. Round-by-round Fault Detectors (Extended Abstract): Unifying Synchrony and Asynchrony. In Seventeenth ACM Symposium on Principles of Distributed Computing, PODC '98, pages 143-152. ACM, 1998. URL: http://dx.doi.org/10.1145/277697.277724.
  9. Maurice Herlihy and Nir Shavit. The Topological Structure of Asynchronous Computability. J. ACM, 46(6):858-923, November 1999. URL: http://dx.doi.org/10.1145/331524.331529.
  10. M. Hutle and A. Schiper. Communication Predicates: A High-Level Abstraction for Coping with Transient and Dynamic Faults. In 37th International Conference on Dependable Systems and Networks (DSN'07), pages 92-101, June 2007. URL: http://dx.doi.org/10.1109/DSN.2007.25.
  11. Fabian Kuhn and Rotem Oshman. Dynamic Networks: Models and Algorithms. SIGACT News, 42(1):82-96, March 2011. URL: http://dx.doi.org/10.1145/1959045.1959064.
  12. Ognjen Marić, Christoph Sprenger, and David Basin. Cutoff Bounds for Consensus Algorithms. In Rupak Majumdar and Viktor Kunčak, editors, Computer Aided Verification, pages 217-237. Springer International Publishing, 2017. Google Scholar
  13. Michael Saks and Fotios Zaharoglou. Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge. SIAM J. Comput., 29(5):1449-1483, March 2000. URL: http://dx.doi.org/10.1137/S0097539796307698.
  14. Adam Shimi, Aurélie Hurault, and Philippe Quéinnec. Characterizing Asynchronous Message-Passing Models Through Rounds. CoRR, 2018. URL: http://arxiv.org/abs/1805.01657.
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