2026-07-24T01:44:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8638 2024-03-06T10:42:14Z ddc:004 open_access

Asynchronous Message Orderings Beyond Causality Shimi, Adam Hurault, Aurélie Quéinnec, Philippe Asynchronous computations Point-to-point message orderings Causality Topology Interior Closure 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Shimi and Aurélie Hurault and Philippe Quéinnec 2018 Is Part Of LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2017.29 urn:nbn:de:0030-drops-86387 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.29 eng https://creativecommons.org/licenses/by/3.0/legalcode