HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 metadata

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/hal-02155487
Contributor : Samuel Mimram Connect in order to contact the contributor
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

60

Files downloads

95