Mutual exclusion with linear waiting using binary shared variables

ABSTRACT

The problem of mutual exclusion among N asynchronous, parallel processes using only shared binary variables for communication is considered. Upper and lower bounds of N+1 and N shared binary variables, respectively, are shown for the problem of mutual exclusion with linear waiting. Lockout-free mutual exclusion is shown to require at least N shared binary variables when the primitive operations are suitably restricted. This latter bound is tight for N=2.

REFERENCES

• 1: 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]
• 2: Donald E. Knuth, Additional comments on a problem in concurrent programming control, Communications of the ACM, v.9 n.5, p.321-322, May 1966 [doi>10.1145/355592.365595]
• 3: Murray A. Eisenberg , Michael R. McGuire, Further comments on Dijkstra's concurrent programming control problem, Communications of the ACM, v.15 n.11, p.999, Nov. 1972 [doi>10.1145/355606.361895]
• 4: Cremers, A. and T. Hibbard, "An Algebraic Approach to Concurrent Programming Control and Related Complexity Problems", University of Southern California Technical Report (Nov 1975).
• 5: Burns, J., M. Fischer, P. Jackson, N. Lynch and G. Peterson, "Shared Data Requirements for Implementation of Mutual Exclusion Using a Test-and-set Primitive", <u>Proc. of the 1978 International Conf. on Parallel Processing</u> (to appear).
• 6: Miller, R. and C. Yap, "Formal Specification and Analysis of Loosely Connected Processes", IBM Research Report RC 6717 (Sep 1977).