The mutual exclusion problem for unreliable processes: Preliminary report
Ronald L. Rivest, Vaughan Pratt · 1976
Cons,ider;, proces.ses operating asynchronously in parallel, each of whiCh maintains I single "special " variable whichc"n be read (but not written). by the other proce$ses ~ All coordination between processes is to.be accomplished by means of the execution. 6.f. "the primitive operations of a process (ll reading another process's spedalvariable, and.(2)' seUing.its own spedal variable to ·some. value. A process may "die " at any time,. when its spedal variable is (automatically) set to a special "dead " value. A dead process may revive.. Reading a special variable which is being simultaneously written returns either the old or the new value. Each process may be in a certain "critical " state (which it leaves if it dies). We present a coordination ' scheme with the following proper,jies. a time. (1) At most one process is ever in its critical state at (2) If a process wants to enter its critical state, it may do so before any other process enters itscrttical state more than once. (3) The special variables are bounded in value. (4) Some process wanting to (!nter its critical state can always make progress to that g.oal. By the definition of the problem, no process can prevent another from entering its critical state by repeatedly failing and restarting. I n the case of two processes, what makes our solution of particular interest is its remarkable simpli~ity when compared with the extant solutions to this problem. Our n-process solution uses the two-process solution as a subroutine. and is not quite as. elegant as the two-process solution.