The mutual exclusion problem: part I—a theory of interprocess communication

ABSTRACT

A novel formal theory of concurrent systems that does not assume any atomic operations is introduced. The execution of a concurrent program is modeled as an abstract set of operation executions with two temporal ordering relations: “precedence” and “can causally affect”. A primitive interprocess communication mechanism is then defined. In Part II, the mutual exclusion is expressed precisely in terms of this model, and solutions using the communication mechanism are given.

REFERENCES

• 1: Per Brinch Hansen, Concurrent Programming Concepts, ACM Computing Surveys (CSUR), v.5 n.4, p.223-245, Dec. 1973 [doi>10.1145/356622.356624]
• 2: CHANEY, T. J., AND MOLNAR, C. E. Anomalous behavior of synchronizer and arbiter circuits. IEEE Trans. Comput. C-22 (Apr. 1973), 421-422.
• 3: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 4: EINSTEIN, A. Zur electrodynamik bewegter korper. Ann. Physik, 17 (1905). Translated as: On the electrodynamics of moving bodies. In The Principle of Relativity, Dover, New York, pp. 35-65.
• 5: Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
• 6: Leslie Lamport, A New Approach to Proving the Correctness of Multiprocess Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.84-97, July 1979 [doi>10.1145/357062.357068]
• 7: LAMPORT, L. On interprocess communication---Part I: Basic formalism. Dist. Comput. (to appear).
• 8: LAMPORT, L. On interprocess communication---Part II: Algorithms. Dist. Comput. (to appear).
• 9: Leslie Lamport, The mutual exclusion problem: partII—statement and solutions, Journal of the ACM (JACM), v.33 n.2, p.327-348, April 1986 [doi>10.1145/5383.5385]
• 10: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 11: MINKOWSKI, H. Space and Time. In The Principle of Relativity. Dover, New York, pp. 73-8 i.
• 12: PALAIS, R., AND LAMPORT, L. On the glitch phenomenon. Tech. Rep. CA-7611-081 l, Massachusetts Computer Associates, Wakefield, Mass., Nov. 1976.
• 13: Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]
• 14: RIVEST, R. L., AND PRATT, V. R. The mutual exclusion problem for unreliable processes: Preliminary report. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1976, pp. 1-80.
• 15: SCHWARTZ, J.T. Relativity in Illustrations. New York University Press, New York, 1962.
• 16: TAYLOR, E. F., AND WHEELER, J.A. Space-Time Physics. W. H. Freeman, San Francisco, 1966.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Mutual exclusion

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

General Terms:
Design, Performance, Theory