Mutual exclusion with linear waiting using binary shared variables
James E. Burns · ACM SIGACT News · 1978
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.