A Fundamental Theorem of Asynchronous Parallel Computation
Computer Science (HMC)
A recurrent phenomenon in models of asynchronous parallel computation is expressed in an abstract model. Many previous models, or special cases thereof, possess three local properties: determinism, commutativity, and persistence, as they are defined here. We show that the possession of these local properties by a system is a sufficient condition for the possession of the global confluence or "Church-Rosser" property. The relation of this property to the "determinacy" of asynchronous systems was suggested in recent work by Rosen. We show that determinacy proofs for many models, and proofs of some other properties of interest, are really corollaries of the main theorem of this paper.
Keller, RM. A fundamental theorem of asynchronous parallel computation. In: Feng TY. Parallel Processing Proceedings of the Sagamore Computer Conference, August 20–23, 1974. Lect Notes Comp Sci. 1975;24: 102-112.