From Geometric Semantics to 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 simplices 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 combinatorial 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 [31 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01207146
Contributor : Matthieu Roy <>
Submitted on : Wednesday, September 30, 2015 - 11:32:12 AM
Last modification on : Sunday, March 31, 2019 - 1:33:16 AM
Long-term archiving on : Thursday, December 31, 2015 - 10:23:30 AM

File

35.pdf
Files produced by the author(s)

Identifiers

Citation

Éric Goubault, Samuel Mimram, Christine Tasson. From Geometric Semantics to Asynchronous Computability. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_29⟩. ⟨hal-01207146⟩

Share

Metrics

Record views

217

Files downloads

132