On interprocess communication. I: Basic formalism. (English) Zbl 0598.68022

Summary: A formalism for specifying and reasoning about concurrent systems is described. Unlike more conventional formalisms, it is not based upon atomic actions. A definition of what it means for one system to implement a higher-level system is given and justified.


68N25 Theory of operating systems
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI


[1] Bernstein PA, Goodman N (1981) Concurrency control in distributed database systems. ACM Comput Surv 13:185–222 · doi:10.1145/356842.356846
[2] Brauer W (ed) (1980) Net Theory and Applications. Lect Notes Comput Sci 84, Springer-Verlag, Berlin Heidelberg New York · Zbl 0484.57024
[3] Lamport L (in press) The mutual exclusion problem. J ACM
[4] Lamport L (1979) A new approach to proving the correctness of multiprocess programs. ACM Trans Program Lang Syst 1:84–97 · Zbl 0463.68022 · doi:10.1145/357062.357068
[5] Lamport L: On interprocess communication. Part II: Algorithms. Distributed Computing 1:85-101 · Zbl 0598.68023
[6] Lamport L (1978) Time, clocks and the ordering of events in a distributed system. Commun ACM 21:558–565 · Zbl 0378.68027 · doi:10.1145/359545.359563
[7] Lamport L (1985) What it means for a concurrent program to satisfy a specification: why no one has specified priority. In: Proceedings of the Twelfth ACM Symposium on Principles of Programming Languages, ACM SIGACT-SIGPLAN, New Orleans
[8] Lamport L (1985) Interprocess Communication. SRI Technical Report, March 1985 · Zbl 0598.68023
[9] Lauer PE, Shields MW. Best E (1979) Formal Theory of the Basic COSY Notation. Technical Report TR143. Computing Laboratory. University of Newcastle upon Tyne
[10] Mazurkiewicz A (1984) Semantics of Concurrent Systems: A Modular Fixed Point Trace Approach. Technical Report 84-19. Institute of Applied Mathematics and Computer Science, University of Leiden · Zbl 0576.68044
[11] Milner R (1980) A Calculus of Communicating Systems. Lect Notes Comput Sci 92. Springer-Verlag, Berlin Heidelberg New York · Zbl 0452.68027
[12] Pnueli A (1977) The temporal logic of programs. In: Proc. of the 18th Symposium on the Foundations of Computer Science, ACM, November 1977
[13] Winskel G (1980) Events in Computation. PhD thesis, Edinburgh University
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.