OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Asynchronous Message Orderings Beyond Causality

Shimi, Adam and Hurault, Aurélie and Quéinnec, Philippe Asynchronous Message Orderings Beyond Causality. (2018) In: The 21st International Conference on Principles of Distributed Systems (OPODIS 2017), 18 December 2017 - 20 December 2017 (Lisboa, Portugal).

(Document in English)

PDF (Publisher's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.4230/LIPIcs.OPODIS.2017.29


In the asynchronous setting, distributed behavior is traditionally studied through computations, 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 asynchronous 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 extensions 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 demonstrates the use of this topological approach by examining closures and interiors of interesting orderings over executions.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Droits : Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
HAL Id:hal-02617506
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Agence Nationale de la Recherche (ANR)
Deposited On:25 May 2020 07:35

Repository Staff Only: item control page