Algebraic topology and concurrency

@article{citeulike:1550280, abstract = {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.}, author = {Fajstrup, Lisbeth and Rau[ss]en, Martin and Goubault, Eric }, booktitle = {Clifford Lectures and the Mathematical Foundations of Programming Semantics}, citeulike-article-id = {1550280}, doi = {http://dx.doi.org/10.1016/j.tcs.2006.03.022}, journal = {Theoretical Computer Science}, keywords = {algebra, algorithms, geometry, multithreading, topology}, month = {July}, number = {1-3}, pages = {241--278}, posted-at = {2007-08-12 10:55:56}, priority = {2}, title = {Algebraic topology and concurrency}, url = {http://dx.doi.org/10.1016/j.tcs.2006.03.022}, volume = {357}, year = {2006} }

TY - JOUR ID - citeulike:1550280 L3 - citeulike-article-id:1550280 N2 - 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. IS - 1-3 JF - Theoretical Computer Science EP - 278 TI - Algebraic topology and concurrency VL - 357 T2 - Clifford Lectures and the Mathematical Foundations of Programming Semantics SP - 241 KW - algebra KW - algorithms KW - geometry KW - multithreading KW - topology AU - Fajstrup, Lisbeth AU - Rau[ss]en, Martin AU - Goubault, Eric PY - 2006/07/25/ UR - http://dx.doi.org/10.1016/j.tcs.2006.03.022 ER -