Algebraic topology and concurrency (Q2500494)

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.