CPSC 668: Distributed Algorithms and Systems
Fall 2006
Homework 2
Due: beginning of class on Fri, Sep 22.
Check course
web page homework section
for more information, especially regarding paper reviews and cover sheet.
Problems:
The numbered exercises are from the textbook.
Do your best to give rigorous proofs of all the results.
- Exercise 4.2. Why is your algorithm correct?
- Exercise 4.3. This exercise is now extra credit.
Find, state, and prove
correct invariants that allow you to prove the correctness
of this algorithm.
- Exercise 4.7
- Exercise 4.9
- Exercise 4.11. Don't just copy the proof for the case of general n.
The point is to come up with a simpler proof (for the special case
of n = 2).
- Extra credit: Exercise 4.14
Paper Reviews:
- Y.-J. Kim and J. H. Anderson, "Adaptive Mutual Exclusion
with Local Spinning", available on-line
here.
(revised version of DISC 2000 paper).
Just skim the voluminous proofs to get an idea of the techniques
used. Focus on the architectural model, the related work, and
the general idea of the algorithms.
- R. Fan and N. Lynch, "An Omega(n log n) Lower Bound on the Cost
of Mutual Exclusion", PODC 2006.