OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Characterizing Asynchronous Message-Passing Models Through Rounds

Shimi, Adam and Hurault, Aurélie and Quéinnec, Philippe Characterizing Asynchronous Message-Passing Models Through Rounds. (2018) In: 22nd International Conference On Principles Of Distributed Systems (OPODIS 2018), 17 December 2018 - 19 December 2018 (Hong Kong, Hong Kong).

(Document in English)

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

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


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, with predicates on the communication graph at each round. Characterizing a model by such a predicate then depends on how to implement rounds in the model. This is straightforward in synchronous models, thanks to the upper bound on communication delay. On the other hand, asynchronous models allow unbounded message delays, which makes the implementation of rounds dependent on the specific message-passing model. A formalization of rounds for asynchronous message-passing models is built through games: the environment captures the non-determinism of a scheduler while processes decide, in turn, whether to change round or wait for more messages. Strategies of processes for these games, capturing the decision of when to change rounds, are studied through a dominance relation: a dominant strategy for a game implements the communication predicate which characterize the corresponding message-passing model. The results of this study are dominant strategies for classical asynchronous models and the existence, for every waiting game, of a dominating strategy for large classes of strategies. On the whole, those results confirm the power of this formalization and demonstrate the characterization of asynchronous models through rounds as a worthwhile pursuit.

Item Type:Conference or Workshop Item (Paper)
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (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:
ANR : Agence nationale de la recherche (France)
Deposited On:03 Mar 2020 12:14

Repository Staff Only: item control page