Distributed Algorithms (236357) Winter 2000

Home assignment # 2

Consider the following mutual exclusion algorithm for n processors (Algorithm 4.7), suggested by Lamport.
(In POSTSCRIPT.)


 

Question 1.

Prove that the algorithm provides mutual exclusion .

Hint. Suppose in contradiction that there is a configuration when two processors, pi and pj, are in the critical section simultaneously.
Observe all the possible cases, e.g.: pi enters through the fast path whereas pj enters through the slow path, etc.

Question 2.

Prove the no deadlock property of the algorithm.

Hint. Assume that there is a deadlock, i.e., some processors are trying to enter the critical section, and none of them succeeds (although the execution is infinite).

  1. Show that there is no processor that continually executes goto in Line 6 or Line 13.
  2. Show that all the processors cannot be forever stuck waiting in Line 5/Line 10/Line 12.

Question 3.

Does the algorithm satisfy the no lockout property?

Submission date: 18/12/2000