A Fundamental Theorem of Asynchronous Parallel Computation

Authors

Robert M. Keller, Harvey Mudd CollegeFollow

Document Type

Conference Proceeding

Department

Computer Science (HMC)

Publication Date

1975

Abstract

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.

Recommended Citation

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.