A Fundamental Theorem of Asynchronous Parallel Computation

Document Type

Conference Proceeding


Computer Science (HMC)

Publication Date



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.

Rights Information

©1975 SpringerLink

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.