Skip to Main content Skip to Navigation
Journal articles

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 : Friday, March 27, 2020 - 3:49:13 AM

File

mimram_views.pdf
Files produced by the author(s)

Identifiers

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

188

Files downloads

662