
This article outlines a way in which algebraic topology can be applied to concurrency theory. The state of a concurrent computation can be represented by a configuration space in which each point stands for the locations of the participating processes in their tasks. Thus a computation involving just two processes could have as its ``state'' the pair of program counters representing the state of each component process. In a quite natural way this space is ``locally partially ordered''. The `locally' being necessitated by the fact that a process may have a built in loop structure. When mutual exclusions between processes need to be taken into account, as will be the case in access to shared memory, there will be forbidden regions in the configuration space, corresponding to violations of the mutual exclusion, indeed there are also deadlock regions from which the processes cannot escape to complete their tasks. The computer scientist is interested in restricting the processes to those paths that allow them to run to completion. The algebraic topologist is interested in determining how many different paths there are in the configuration space. This paper constructs a directed homotopy theory of these configuration spaces based on a notion of cubical set, not unlike cubical homology except that the cubes have a partial ordering on them. The results are applied to prove the safeness of a two-phase protocol. The paper concludes with a list of interesting problems in the area. The paper has an extensive bibliography which will be of great use to persons interested in pursuing work in this area.
Higher-dimensional automata, local partial order, Theory of computing, directed homotopy, higher-dimensional automata, Cubical set, deadlock, Theoretical Computer Science, Partially ordered space, Homotopy theory, Concurrency, Partial order, Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.), concurrency, cubical set, Homotopy, Computer Science(all)
Higher-dimensional automata, local partial order, Theory of computing, directed homotopy, higher-dimensional automata, Cubical set, deadlock, Theoretical Computer Science, Partially ordered space, Homotopy theory, Concurrency, Partial order, Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.), concurrency, cubical set, Homotopy, Computer Science(all)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 79 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
