• CS425
• Assignments
• HW2

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 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.