Assignment handed out on Tuesday, March 13, 2001
Due in Recitation on 3/14/2001:
Read Chapters 10 and 11 from the text. There are many proofs.
You don't have to spend the time to understand them inside and out.
Instead, understand the implication of the proofs (e.g., under which
circumstances you can solve the byzantine generals problem).
Your writing/discussion assignment:
Distributed mutual exclusion can be accomplished using a variety of
algorithms. Several are described in the text. Those algorithms,
however, react differently to process failures.
Suppose that at most 1 process can fail. If you were able to reliably
detect the failure, which algorithm would you choose for distributed
mutual exclusion? Explain why. How does your algorithm react if you
cannot reliably detect the failure? What kind of approach would you
then use to achieve distributed mutual exclusion?
Hint 1: Use a case-based analysis. Consider the following cases:
- the failed process was in a critical section (e.g., was holding the
exclusivity)
- the failed process was waiting to enter the critical section
- the failed process was not waiting and was not in the critical section
Hint 2: Think about the consensus problem