TY - GEN
T1 - From geometric semantics to asynchronous computability
AU - Goubault, Éric
AU - Mimram, Samuel
AU - Tasson, Christine
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
PY - 2015/1/1
Y1 - 2015/1/1
N2 - 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 dihomotopy classes of dipaths in the latter semantics, we describe a connection between these two geometric approaches: 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.
AB - 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 dihomotopy classes of dipaths in the latter semantics, we describe a connection between these two geometric approaches: 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.
U2 - 10.1007/978-3-662-48653-5_29
DO - 10.1007/978-3-662-48653-5_29
M3 - Conference contribution
AN - SCOPUS:84946090253
SN - 9783662486528
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 436
EP - 451
BT - Distributed Computing - 29th International Symposium, DISC 2015, Proceedings
A2 - Moses, Yoram
PB - Springer Verlag
T2 - 29th International Symposium on Distributed Computing, DISC 2015
Y2 - 7 October 2015 through 9 October 2015
ER -