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.
Work reported herein was performed while the author was visiting Stanford University, and was sponsored by NSF grant GJ-30126
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Adams, "A Computation Model with Data Flow Sequencing", Tech. Report CS 117 (Ph.D. dissertation), Computer Science Dept., Stanford Univ. (Dec. 1968).
F. Commoner, A.W. Holt, S. Even, and A. Pnueli, "Marked Directed Graphs", J. Computer and System Sciences, 5, 5 (Oct. 1971) pp. 511–523
M. Hack, "Decision Problems for Petri Nets and Vector Addition Systems", MIT Project MAC, Computation Structures Group Memo 95 (Mar. 1974).
G. Kahn, "A Preliminary Theory for Parallel Programs", IRIA Research Report No. 6, (Jan. 1973).
R.M. Karp, and R.E. Miller, "Parallel Program Schemata," J. Computer and System Sciences, 3, 2, (May 1969), pp. 147–195.
R.M. Karp, and R.E. Miller, "Properties of a Model for Parallel Computations: Determinacy, Termination, and Queuing," SIAM J. Applied Math., 14, 6. (Nov. 1966), pp. 1390–1411.
R.M. Keller, "Parallel Program Schemata and Maximal Parallelism," J. ACM, 20, 3, (July 1973) pp. 514–537 and 20, 4, (Oct. 1973) pp. 696–710.
R.M. Keller, "Vector Replacement Systems: A Formalism for Modeling Asynchronous Systems," Tech. Rept. 117, Computer Science Laboratory, Princeton University (Jan. 1974).
F.L. Luconi, "Asynchronous Computational Structures," MIT Project MAC Rept. MAC-TR-49 (1968).
D.E. Muller and W.S. Bartky, "A Theory of Asynchronous Circuits," Annals of the Computation Laboratory of Harvard University, 29, Pt. 1, (1959) pp. 204–243.
M.H.A. Newman, "On Theories with a Combinatorial Definition of ‘Equivalence'" Annals of Math., 43, 2, (April 1942), pp. 223–243.
S. Patil, "Closure Properties of Interconnections of Determinate Systems," Proc. Project MAC Conference on Concurrent Systems and Parallel Computations, (June 1970), pp. 107–116.
B. Rosen, "Tree Manipulating Systems and Church-Rosser Theorems", J. ACM 20, 1, (Jan. 1973), pp. 160–187.
R. Sethi, "Theorems of Confluence for Unions of Replacement Systems with Equivalences," Tech. Rept. 131, Computer Science Dept., Pennsylvania State University (Oct. 1972).
R.C. Holt, "On Deadlock in Computer Systems," Univ. of Toronto Computer Science Research Group Rept. CSRG-6, (April 1971).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1975 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Keller, R.M. (1975). A fundamental theorem of asynchronous parallel computation. In: Feng, Ty. (eds) Parallel Processing. SCC 1974. Lecture Notes in Computer Science, vol 24. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-07135-0_113
Download citation
DOI: https://doi.org/10.1007/3-540-07135-0_113
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-07135-8
Online ISBN: 978-3-540-37408-4
eBook Packages: Springer Book Archive