Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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.

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.

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 vi from pi, for all i.

• v ← mini vi.

• 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 vi from pi, for all i

• set v to the most frequent value among the vi, 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.

2014-06-17 11:58