CPSC 668: Distributed Algorithms and Systems
Fall 2006
Homework 5
Due: beginning of class on Fri, Nov 3. **postponed to Mon, Nov 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.
- Problem 4 on the midterm.
- Problem 5 on the midterm. Work out the bounds in detail (don't
just refer to a theorem in a paper).
- Exercise 7.1
- Exercise 8.1
- Exercise 8.7
- Exercise 8.9
- Exercise 9.2. Correct typo: prove that linearizability is *composable*
(not local).
- Exercise 9.3
- Exercise 9.7
Paper Reviews:
- G. Chockler, I. Keidar, and R. Vitenberg,
"Group Communication Specifications: A Comprehensive Study",
CACM Computing Surveys, vol. 33, no. 4, Dec. 2001, pp. 427--469.
- Cristian Tapus, Aleksey Nogin, Jason Hickey, and Jerome White,
"A Mechanism for Sequential Consistency in a Distributed Objects System,"
17th International Conference on Parallel and Distributed Computing Systems
(PDCS), 2004.
Available at http://mojave.caltech.edu/crt/applications.shtml.