OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Derivation of Heard-Of Predicates From Elementary Behavioral Patterns

Shimi, Adam and Hurault, Aurélie and Quéinnec, Philippe Derivation of Heard-Of Predicates From Elementary Behavioral Patterns. (2020) In: International Conference on Formal Techniques for Networked and Distributed Systems (FORTE 2020), 15 June 2020 - 19 June 2020 (Online, France).

(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.1007/978-3-030-50086-3_8


There are many models of distributed computing, and no unifying mathematical framework for considering them all. One way to sidestep this issue is to start with simple communication and fault models, and use them as building blocks to derive the complex models studied in the field. We thus define operations like union, succession or repetition, which makes it easier to build complex models from simple ones while retaining expressivity. To formalize this approach, we abstract away the complex models and operations in the Heard-Of model. This model relies on (possibly asynchronous) rounds; sequence of digraphs, one for each round, capture which messages sent at a given round are received before the receiver goes to the next round. A set of sequences, called a heard-of predicate, defines the legal communication behaviors – that is to say, a model of communication. Because the proposed operations behave well with this transformation of operational models into heard-of predicates, we can derive bounds, characterizations, and implementations of the heard-of predicates for the constructions.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer Nature Switzerland editor. This papers appears in volume 12136 of Lecture Notes in Computer Science, ISSN: 0302-9743, ISBN: 978-3-030-50085-6 The original PDF is available at: https://link.springer.com/chapter/10.1007/978-3-030-50086-3_8
HAL Id:hal-02947787
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:
Agence Nationale de la Recherche - ANR (FRANCE)
Deposited On:11 Sep 2020 13:47

Repository Staff Only: item control page