Geometric and combinatorial views on asynchronous computability

Abstract : We show that the protocol complex formalization of fault-tolerant protocols can be directly derived from a suitable semantics of the underlying synchronization and communication primitives, based on a geometrization of the state space. By constructing a one-to-one relationship between sim-plices of the protocol complex and (di)homotopy classes of (di)paths in the latter semantics, we describe a connection between these two geometric approaches to distributed computing: protocol complexes and directed algebraic topology. This is exemplified on atomic snapshot, iterated snapshot and layered immediate snapshot protocols, where a well-known com-binatorial structure, interval orders, plays a key role. We believe that this correspondence between models will extend to proving impossibility results for much more intricate fault-tolerant distributed architectures.
Complete list of metadatas

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/hal-02155487
Contributor : Samuel Mimram <>
Submitted on : Thursday, June 13, 2019 - 4:03:40 PM
Last modification on : Saturday, June 15, 2019 - 1:17:57 AM

File

mimram_views.pdf
Files produced by the author(s)

Identifiers

Données associées

Citation

Eric Goubault, Samuel Mimram, Christine Tasson. Geometric and combinatorial views on asynchronous computability. Distributed Computing, Springer Verlag, 2018, 31 (4), pp.289-316. ⟨10.1007/s00446-018-0328-4⟩. ⟨hal-02155487⟩

Share

Metrics

Record views

48

Files downloads

248