Skip to Main content Skip to Navigation
Theses

On the Power of Rounds: Explorations of the Heard-Of Model

Abstract : Distributed computing differs from sequential computing mainly through its abundance of incomparable models. Whereas everything goes back to Turing machines in sequential computing, distributed computing models the inherent uncertainties of communication and synchronization, in many equally meaningful ways that don't fall under the umbrella of one true model. The need to study them all then leads to the complex landscape of distributed computing models. A recent approach for dealing with this difficulty proposes to unify models through communication-closed rounds: sequences of steps where everyone sends a message tagged with the current round number, waits for messages with this same round number, and then uses them to compute its next state and change round. The most promising take on this approach, in my opinion, is the Heard-Of model of Charron-Bost and Schiper. One significant advantage of this model over alternatives lies in its lack of operational assumptions: no synchrony, no adversary, not even failures. Everything follows from which message is received on time -- before the end of the corresponding round at the receiver. Collections capture these possible patterns of messages received on time, and predicates over these collections capture models of communication. Yet this model lacks the attention that it deserves from the research community. I believe the reason lies on the following three unsolved problems: how to find the heard-of predicate corresponding to a given model; is anything lost in this translation; and how to prove general results on heard-of predicates. This thesis addresses all three, and provides elements of answers: a formalization of how to derive the most meaningful heard-of predicate for a given model, along with a methodology for simplifying this derivation by decomposing the original model into a combination of simpler ones; an equivalence between new heard-of predicates and asynchronous message-passing with failure detectors, along with an analysis of the underlying assumptions of such and previous equivalences; and general impossibility results for k-set agreement using combinatorial topology, and focusing on a class of heard-of predicates capturing many safety properties.
Complete list of metadata

https://hal.archives-ouvertes.fr/tel-03123969
Contributor : Philippe Queinnec <>
Submitted on : Thursday, January 28, 2021 - 12:06:38 PM
Last modification on : Thursday, June 10, 2021 - 3:48:32 AM
Long-term archiving on: : Thursday, April 29, 2021 - 6:42:31 PM

File

these.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-03123969, version 1

Citation

Adam Shimi. On the Power of Rounds: Explorations of the Heard-Of Model. Distributed, Parallel, and Cluster Computing [cs.DC]. Université de Toulouse, 2020. English. ⟨tel-03123969⟩

Share

Metrics

Record views

74

Files downloads

84