CPSC 668: Distributed Algorithms and Systems
Fall 2006
Homework 3
Due: beginning of class on Fri, Oct 6.
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 5.4
- Exercise 5.9
- Exercise 5.12. (For some background, read the statements
of Exercises 5.1 and 5.7.)
- Exercise 5.14
- Exercise 5.20. (You don't have to follow the suggested outline
if it is not helpful to you.)
- Exercise 5.21
- Exercise 6.1
Paper Reviews:
- T. Mizrahi and Y. Moses, "Continuous Consensus via Common
Knowledge," Proceedings of the 10th Conference on Theoretical
Aspects of Rationality and Knowledge (TARK), pp. 236-252, 2005.
Available from the ACM Digital Library.
- A. Arora, S. Kulkarni, and M. Demirbas, "Resettable Vector Clocks,"
Proceedings of the 19th ACM Symposium on Principles of Distributed
Computing (PODC), pp. 269-278, 2000.
Available from the ACM Digital Library.