/Solutions

1. Group mutual exclusion

In group mutual exclusion, each process that wants to enter the critical section specifies a session id, and it is permitted for two or more processes with the same session id to be in the critical section at the same time. Slightly more formally, we can define a group mutual exclusion protocol as one that satisfies: (a) group mutual exclusion: no two processes with the different session ids are in the critical section simultaneously; (b) progress: if no process is in the critical section, eventually some process enters the critical section; and (c) concurrent entering: if a process p with a given session id attempts to enter the critical session, and no process with a different session id is executing the protocol, then p enters the critical section after a bounded number of steps.

1. Give an implementation of a group mutual exclusion protocol as defined above using a single RMW register.

2. Suppose that session ids are either 0 or 1, and we have each process run Peterson's two-process tournament algorithm (as describe in MutualExclusion) using its session id in place of its process id. Is the resulting protocol a group mutual exclusion protocol?

2. Two agreement protocols

Suppose you have an asynchronous system in which any one process may crash, and that you want an agreement protocol satisfying the usual requirements of agreement, validity, and termination. From the FischerLynchPaterson impossibility result, we know that this is impossible for deterministic processes.

1. Consider the following protocol: each process sends its input (0 or 1) to all processes (including itself). It then waits to receive n messages and decides on the OR of their values. Show that this protocol satisfies agreement and validity, but not termination.

2. Consider this protocol, for n even and at least 4: Each process executes a loop implementing a sequence of phases. Initially, process p sets v_p to input_p. In phase i, process p sends (i, v_p) to all processes (including itself). It then waits to receive n-1 phase-i messages and sets v_p to the majority of the values its sees (we assume messages from later phases are buffered so p can pretend it received them during the appropriate phase). If all the messages p receives have the same value for three phases in a row, p decides on that value. Show that this protocol satisfies agreement and validity, but not termination.

3. Synchronous agreement with intermittent faults

Suppose we have a system where one process in each round suffers a transmitter failure, causing some subset of its outgoing messages for that round to be lost. These faults are intermittent; a process p that is faulty in round r is not necessarily faulty in round r+1, and indeed if some other process q is faulty in round r+1, then p must not be faulty in round r+1, because at most one process is faulty in each round.

Is it possible to solve synchronous agreement (see SynchronousAgreement) in this model? Give a protocol and prove that it works, or give an impossibility result.