1. Mutual exclusion in a message-passing system

Give an efficient algorithm for solving mutual exclusion in an asynchronous bidirectional message-passing network. You may assume processes have unique identities. Your algorithm should be starvation-free; that is, if every process that enters a critical section eventually exits it, then every process that is trying to enter a critical section eventually does so.

1.1. Solution

Elect a leader and build a spanning tree with the leader at the root, then pass a token around around a DFS traversal of the tree. The token is initially possessed by the root of the tree. To enter its critical section, a process first waits to receive the token; it sends the token on when it leaves its critical section. If it is not trying, it resends the token immediately. Mutual exclusion follows from the existence of only one token. Starvation-freedom follows because the token eventually reaches every node in the tree.

2. Mutual exclusion with multiple resources

Suppose that instead of having 1 critical shared resource, we have k. We wish to build a protocol similar to mutual exclusion for assigning processes exclusively to one of these resources. The protocol should provide two procedures: an acquire procedure that returns the identity of one of the resources, and a release procedure that releases the previously-acquired resource.

Design a protocol for this k-mutual-exclusion problem that satisfies the following two conditions:

Mutual exclusion

A protocol provides mutual exclusion if whenever some process P's acquire operation returns i, no other process's acquire operation returns i until P calls release(i).

Starvation-freedom

A process seizes resource i if it obtains i through an acquire operation but never calls release(i). A protocol is starvation-free if, in any execution where k-1 or fewer resources are seized, every call to acquire eventually returns.

You may find it helpful to use a known mutual exclusion algorithm as a subroutine.

2.1. Solution

There are many ways to solve this problem. Here is one:

We maintain a queue of waiting processes together with an array of assignments, where a[i] is the process assigned to resource i, or ⊥ if there is not process assigned to resource i. We use a single lock (mutual exclusion algorithm) to protect the shared variables from concurrent updates.

Acquire procedure:

• Acquire the lock.
• Add myself to the end of the queue.
• Release the lock.
• acquired ← ⊥
• while acquired = ⊥:
  • Acquire the lock.
  • If there are any empty entries in a[], fill them in with process id's dequeued from the queue.
  • If my id appears in a[i] for some i, set acquired to i.
  • Release the lock.
• Return acquired.

Release procedure:

• Acquire the lock.
• Find i such that a[i] = my pid and set a[i] to ⊥
• Release the lock.

Proof of mutual exclusion: If p has acquired i, then a[i] = p; when a[i] is set to p (not necessarily by p), no other process has a pending write on a[i] (because of the lock), and no process but p can write any value to a[i] without checking that it is empty first.

Proof of starvation-freedom: Let i be a resource that is never seized. Each time i is released, a[i] is set to ⊥; so the next time some process goes through the loop, at least one process will be dequeued and stored in a[i]. It follows that any process that enters the queue eventually leaves it.

3. Consensus with crash failures

A user complains that Algorithm 15 from AttiyaWelch transmits too much data, and suggests the following modified algorithm:

• Initially v = x.
• round k, 1≤k≤f+1:
  • send v to all processors (including myself).

  • receive v_i from p_i, for all i.

  • v ← min_i v_i.

  • if k = f+1, then decide on v.

Another user suggests a democratic approach:

• Initially v = x
• round k, 1≤k≤f+1:
  • send v to all processors (including myself)

  • receive v_i from p_i, for all i

  • set v to the most frequent value among the v_i, breaking ties in favor of smaller values.

  • if k = f+1, then decide on v.

Do either of these protocols work? If so, prove it. If not, give a counterexample.

3.1. Solution

Both protocols work, with t+1 rounds, where t is the number of failures. Indeed, any function f of the received messages that is used by all processes and never picks a value that isn't among its inputs works, with f+1 rounds. The proof:

• Validity::Use induction to show that every value f(...) computed at each round is an original input to some process.
Agreement
With t+1 rounds, some round is failure-free. In this round all processes receive the same message and compute the same value using f. Since this is the only surviving value, further applications of f in subsequent rounds can't cause any process to decide anything else.

Note that f+1 rounds is optimal (by the lower bound in IndistinguishabilityProofs for f < n-1), so it doesn't particularly matter which f we choose.