From Geometric Semantics to Asynchronous Computability
From Geometric Semantics to Asynchronous Computability
复制标题
从几何语义到异步可计算性
DOI：
10.1007/978-3-662-48653-5_29
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
C. Tasson
中科院分区：
文献类型：
--
作者：
É. Goubault;S. Mimram;C. Tasson
我们表明，协议复杂的形式化的容错协议可以直接从一个合适的语义的基础同步和通信原语，基于几何化的状态空间。通过构建一个一对一的关系简单的协议复杂的（二）同伦类的（二）路径在后者的语义，我们描述了这两个几何方法之间的连接分布式计算：协议复杂和有向代数拓扑。原子快照，迭代快照和分层立即快照协议，其中一个众所周知的组合结构，间隔顺序，起着关键作用。我们相信，模型之间的这种对应关系将扩展到证明更复杂的容错分布式体系结构的不可能结果。
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.