Bounds on Shared Memory for Mutual Exclusion

The shared memory requirements of Dijkstra′s mutual exclusion problem are examined. It is shown that n binary shared variables are necessary and sufficient to solve the problem of mutual exclusion with guaranteed global progress for n processes using only atomic reads and writes of shared variables for communication.

Authors

• J.E. Burns
• N.A. Lynch

Keywords

No keywords are indexed for this paper.