Algebraic topology and concurrency
Algebraic topology and concurrency
复制标题
代数拓扑和并发
DOI：
10.1016/j.tcs.2006.03.022
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
É. Goubault
中科院分区：
文献类型：
--
作者：
L. Fajstrup;M. Raussen;É. Goubault
在这篇文章中，我们表明，同伦理论的一些概念，在代数拓扑，是相关的研究并发程序。我们表现出一个自然的语义的信号量程序，半序拓扑空间的基础上，研究了“弹性变形”或同伦，提供有关的重要属性的程序，如死锁，不可达，serializability，基本的时间表等，事实上，它不是很普通的同伦，必须使用，而是一个“定向同伦”，不扭转的时间流。我们通过例子展示了普通同伦和有向同伦之间的一些本质区别。我们还涉及到拓扑视图的并发程序更接近过渡系统的组合视图，通过一个立方集的概念。最后，我们应用这些概念的安全性证明的两个阶段的协议，众所周知，并在并发数据库理论中使用。我们最终从数学和计算机科学的角度列出了一系列问题。
We show in this article that some concepts from homotopy theory, in algebraic topology, are relevant for studying concurrent programs. We exhibit a natural semantics of semaphore programs, based on partially ordered topological spaces, which are studied up to “elastic deformation” or homotopy, giving information about important properties of the program, such as deadlocks, unreachables, serializability, essential schedules, etc. In fact, it is not quite ordinary homotopy that has to be used, but rather a “directed homotopy” that does not reverse the flow of time. We show some of the essential differences between ordinary and directed homotopy through examples. We also relate the topological view to a combinatorial view of concurrent programs closer to transition systems, through the notion of a cubical set. Finally we apply some of these concepts to the proof of the safeness of a two-phase protocol, well-known and used in concurrent database theory. We end up with a list of problems from both a mathematical and a computer-scientific point of view.