Fall 2000

Homework

- The homework problems refer to the textbook.
- Please check the errata page
for the textbook.
- Write clearly and legibly. Grading will be based on correctness, clarity, and whether your solution is of the appropriate length.

**Homework 4, due 10:20 AM, Friday, Dec 1, 2000:**

(R) Exercise 8.8. Explain why or why not.

(S) Exercise 8.9

(T) Exercise 9.2

(U) Exercise 9.3

(V) Exercise 9.11

(W) Exercise 15.6

(X) Exercise 17.22

*** This is the entire assignment. ***

**Homework 3, due 10:20 AM, Monday, November 6, 2000:**

(N) Exercise 6.2.

(O) Exercise 6.5.

(P) Exercise 6.12.

(Q) Describe an algorithm to synchronize clocks (achieve epsilon- Clock Agreement and gamma-Clock Validity) in the following situation:

- n processors and no failures
- complete topology graph (clique)
- every message delay is d (no uncertainty)
- for each i, H_i(t) = r_i * t, for some r_i > 0. Each processor's hardware clock has a constant drift r_i which is unknown to the processors. Different processors may have different drift rates.

*** This is the entire assignment. ***

**Homework 2, due 10:20 AM, Wednesday, October 11, 2000 - postponed
to Monday, October 16, 2000:**

(F) Exercise 4.2. Your algorithm must ensure that a processor does not have to wait if only one processor is already in the critical section. Prove that your algorithm is correct.

(G) Exercise 4.5. Prove that your algorithm is correct.

(H) Exercise 4.7.

(I) Exercise 4.10.

(J) Exercise 5.2. Prove that your algorithm is correct.

(K) Exercise 5.6. Prove that your algorithm is correct.

(L) Exercise 5.17.

(L) Exercise 5.18. (Check the errata page.)

(M) Exercise 5.19. If you don't find the notation suggested in point 1 to be helpful, then just ignore it. (Check the errata page.)

**Homework 1, due 10:20 AM, Friday, September 15, 2000:**

(A) Exercise 2.8

(B) Exercise 2.11

(C) Exercise 3.3

(D) Exercise 3.5

(E) Exercise 14.3