Document Open Access Logo

Asynchronous Message Orderings Beyond Causality

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.OPODIS.2017.29.pdf
  • Filesize: 0.5 MB
  • 20 pages

Document Identifiers

Subject Classification

Keywords
  • Asynchronous computations
  • Point-to-point message orderings
  • Causality
  • Topology
  • Interior
  • Closure

Metrics

Abstract

In the asynchronous setting, distributed behavior is traditionally studied through computa- tions, the Happened-Before posets of events generated by the system. An equivalent perspective considers the linear extensions of the generated computations: each linear extension defines a sequence of events, called an execution. Both perspective were leveraged in the study of asyn- chronous point-to-point message orderings over computations; yet neither allows us to interpret message orderings defined over executions. Can we nevertheless make sense of such an ordering, maybe even use it to understand asynchronicity better?
We provide a general answer by defining a topology on the set of executions which captures the fundamental assumptions of asynchronicity. This topology links each message ordering over executions with two sets of computations: its closure, the computations for which at least one linear extension satisfies the predicate; and its interior, the computations for which all linear ex- tensions satisfy it. These sets of computations represent respectively the uncertainty brought by asynchronicity – the computations where the predicate is satisfiable – and the certainty available despite asynchronicity – the computations where the predicate must hold. The paper demon- strates the use of this topological approach by examining closures and interiors of interesting orderings over executions.

Cite As Get BibTex

Adam Shimi, Aurélie Hurault, and Philippe Quéinnec. Asynchronous Message Orderings Beyond Causality. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.OPODIS.2017.29

Author Details

Adam Shimi
Aurélie Hurault
Philippe Quéinnec

References

  1. Bowen Alpern and Fred B. Schneider. Defining liveness. Inf. Process. Lett., 21(4):181-185, 1985. URL: http://dx.doi.org/10.1016/0020-0190(85)90056-0.
  2. Samik Basu, Tevfik Bultan, and Meriem Ouederni. Synchronizability for verification of asynchronously communicating systems. In Viktor Kuncak and Andrey Rybalchenko, editors, Verification, Model Checking, and Abstract Interpretation - 13th International Conference, VMCAI 2012, Philadelphia, PA, USA, January 22-24, 2012. Proceedings, volume 7148 of Lecture Notes in Computer Science, pages 56-71. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-27940-9_5.
  3. Ido Ben-Zvi and Yoram Moses. Beyond lamport’s Happened-before: On time bounds and the ordering of events in distributed systems. J. ACM, 61(2):13:1-13:26, 2014. URL: http://dx.doi.org/10.1145/2542181.
  4. Kenneth P. Birman and Thomas A. Joseph. Reliable communication in the presence of failures. ACM Trans. Comput. Syst., 5(1):47-76, 1987. URL: http://dx.doi.org/10.1145/7351.7478.
  5. K. Mani Chandy and Leslie Lamport. Distributed snapshots: Determining global states of distributed systems. ACM Trans. Comput. Syst., 3(1):63-75, 1985. URL: http://dx.doi.org/10.1145/214451.214456.
  6. K. Mani Chandy and Jayadev Misra. How processes learn. Distributed Computing, 1(1):40-52, 1986. URL: http://dx.doi.org/10.1007/BF01843569.
  7. Bernadette Charron-Bost, Carole Delporte-Gallet, and Hugues Fauconnier. Local and temporal predicates in distributed systems. ACM Trans. Program. Lang. Syst., 17(1):157-179, 1995. URL: http://dx.doi.org/10.1145/200994.201005.
  8. Bernadette Charron-Bost, Friedemann Mattern, and Gerard Tel. Synchronous, asynchronous, and causally ordered communication. Distributed Computing, 9(4):173-191, 1996. URL: http://dx.doi.org/10.1007/s004460050018.
  9. Bernadette Charron-Bost, Sam Toueg, and Anindya Basu. Revisiting safety and liveness in the context of failures. In Catuscia Palamidessi, editor, CONCUR 2000 - Concurrency Theory, 11th International Conference, University Park, PA, USA, August 22-25, 2000, Proceedings, volume 1877 of Lecture Notes in Computer Science, pages 552-565. Springer, 2000. URL: http://dx.doi.org/10.1007/3-540-44618-4_39.
  10. David R. Cheriton and Dale Skeen. Understanding the limitations of causally and totally ordered communication. SIGOPS Oper. Syst. Rev., 27(5):44-57, 1993. URL: http://dx.doi.org/10.1145/173668.168623.
  11. Florent Chevrou, Aurélie Hurault, and Philippe Quéinnec. On the diversity of asynchronous communication. Formal Asp. Comput., 28(5):847-879, 2016. URL: http://dx.doi.org/10.1007/s00165-016-0379-x.
  12. Robert Cooper and Keith Marzullo. Consistent detection of global predicates. SIGPLAN Not., 26(12):167-174, dec 1991. URL: http://dx.doi.org/10.1145/127695.122774.
  13. Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi, and Yoram Moses. Reasoning About Knowledge. MIT Press, Cambridge, MA, USA, 1995. Google Scholar
  14. Colin J. Fidge. Timestamps in message-passing systems that preserve the partial ordering. Proceedings of the 11th Australian Computer Science Conference, 10(1):56–66, 1988. Google Scholar
  15. Joseph Y. Halpern and Yoram Moses. Knowledge and common knowledge in a distributed environment. J. ACM, 37(3):549-587, 1990. URL: http://dx.doi.org/10.1145/79147.79161.
  16. Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, 1991. URL: http://dx.doi.org/10.1145/114005.102808.
  17. Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann Publishers Inc., 1st edition, 2013. Google Scholar
  18. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858-923, 1999. URL: http://dx.doi.org/10.1145/331524.331529.
  19. Ajay D. Kshemkalyani and Mukesh Singhal. Necessary and sufficient conditions on information for causal message ordering and their optimal implementation. Distributed Computing, 11(2):91-111, 1998. URL: http://dx.doi.org/10.1007/s004460050044.
  20. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558-565, 1978. URL: http://dx.doi.org/10.1145/359545.359563.
  21. Friedemann Mattern. Virtual time and global states of distributed systems. In Parallel and Distributed Algorithms, pages 215-226. North-Holland, 1989. Google Scholar
  22. Venkatesh V. Murty and Vijay K. Garg. Characterization of message ordering specifications and protocols. In Proceedings of the 17th International Conference on Distributed Computing Systems, Baltimore, MD, USA, May 27-30, 1997, pages 492-499. IEEE Computer Society, 1997. URL: http://dx.doi.org/10.1109/ICDCS.1997.603392.
  23. Michel Raynal, André Schiper, and Sam Toueg. The causal ordering abstraction and a simple way to implement it. Inf. Process. Lett., 39(6):343-350, 1991. URL: http://dx.doi.org/10.1016/0020-0190(91)90008-6.
  24. André Schiper, Jorge Eggli, and Alain Sandoz. A new algorithm to implement causal ordering. In Jean-Claude Bermond and Michel Raynal, editors, Distributed Algorithms, 3rd International Workshop, Nice, France, September 26-28, 1989, Proceedings, volume 392 of Lecture Notes in Computer Science, pages 219-232. Springer, 1989. URL: http://dx.doi.org/10.1007/3-540-51687-5_45.
  25. Reinhard Schwarz and Friedemann Mattern. Detecting causal relationships in distributed computations: In search of the holy grail. Distributed Computing, 7(3):149-174, 1994. URL: http://dx.doi.org/10.1007/BF02277859.
  26. Terunao Soneoka and Toshihide Ibaraki. Logically instantaneous message passing in asynchronous distributed systems. IEEE Trans. Computers, 43(5):513-527, 1994. URL: http://dx.doi.org/10.1109/12.280800.
  27. Ashis Tarafdar and Vijay K. Garg. Addressing false causality while detecting predicates in distributed programs. In Proceedings of the 18th International Conference on Distributed Computing Systems, Amsterdam, The Netherlands, May 26-29, 1998, pages 94-101. IEEE Computer Society, 1998. URL: http://dx.doi.org/10.1109/ICDCS.1998.679491.
  28. William T. Trotter. Combinatorics and Partially Ordered Sets. The Johns Hopkins University Press, 1992. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact