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. Your algorithm should satisfy no-lockout. Argue the correctness of your algorithm.
• Exercise 4.6.
• Exercise 4.7.
• Exercise 5.5.
• Exercise 5.12. (For some background, read the statements of Exercises 5.1 and 5.7.)
• Exercise 5.16.
• Exercise 5.17. Either give an algorithm or give an impossibility proof.
• Exercise 5.19. (2/18: I removed the irrelevant "hint".)

Paper Reviews:

1. Y.-J. Kim and J. H. Anderson, "Adaptive Mutual Exclusion with Local Spinning", Distributed Computing, vol. 19, no. 3, 2007. Available on line (if you are behind the TAMU firewall) at: http://www.springerlink.com/content/k51766836k425203/. Just skim the proofs in the appendix to get an idea of the techniques used. Focus on the architectural model, the related work, and the general idea of the algorithms.
2. B. Charron-Bost and A. Schiper, "Uniform Consensus is Harder than Consensus," Journal of Algorithms, vol. 51, pp. 15-37, 2004. Available on line (if you are behind the TAMU firewall) at: http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-4BKN0MM-1&_user=952835&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000049198&_version=1&_urlVersion=0&_userid=952835&md5=44027502e4ab80899881c5320dab6c53 . Focus on concepts of uniform consensus (different use of the word uniform), early stopping, omission failure model, as well as the complexity results.