Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Matthieu Roy Connect in order to contact the contributor
Submitted on : Wednesday, September 30, 2015 - 11:32:12 AM
Last modification on : Friday, March 27, 2020 - 3:47:18 AM
Long-term archiving on: : Thursday, December 31, 2015 - 10:23:30 AM


Files produced by the author(s)



É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⟩



Record views


Files downloads