CSCE 668: Distributed Algorithms and Systems
Spring 2014
Homework

General Instructions:
• Check course web page homework section for more information, especially regarding use of LaTeX, paper reviews and cover sheet.

• The numbered exercises are from the textbook.

• Do your best to give rigorous proofs of all the results.

• Be sure to explicitly list any assumptions that you make (in case a question seems ambiguous and you are unable to get clarification).

[Homework 1] [Homework 2] [Homework 3] [Homework 4] [Homework 5] [Homework 6] [Homework 7]

Problems:

• Exercise 2.2.
• Exercise 2.3.
• Exercise 3.3.
• Exercise 3.5.

Paper Review: (If you are behind the TAMU firewall, following the links should give you access to the full text of the papers.)

Problems:

• Exercise 14.3.
• Prove that these three statements are invariants of Algorithm 9 (true in every configuration):
1. At most one element in the Flags array is set to has-lock.
2. If no element in the Flags array is set to has-lock, then exactly one processor, say p_i, is in the critical section, and exactly (Last - k) mod n processors are in the entry section, each of them spinning on a different entry in the Flags array: Flags[k], Flags[k+1 mod n], ..., Flags[Last-1 mod n], where k = my-place_i + 1 mod n.
3. If Flags[k] is set to has-lock, then no processor is in the critical section, and exactly (Last - k) mod n processors are in the entry section, each of them spinning on a different entry of Flags: Flags[k], Flags[k+1 mod n], ..., Flags[Last-1 mod n].
Then use these invariants to prove that Algorithm 9 provides mutual exclusion and FIFO entry to the critical section.
• Exercise 4.8.
• Exercise 4.11. Do not simply appeal to Theorem 4.19. Instead, write a proof from scratch. Model it after the proof of Theorem 4.19, but it should be much simpler because there are only 2 processors, instead of n. The point is make sure you understand the proof of Theorem 4.19 sufficiently to write your own simplified version.

Paper Review: (If you are behind the TAMU firewall, following the links should give you access to the full text of the papers.)

Homework 3: Due Mon, Mar 3, 10:20 AM

Problems:

• Exercise 5.5
• For the case when f = 2 and n = 8, describe an execution of the Phase King algorithm (Algorithm 16) that fails to solve the consensus problem.
• Exercise 5.14
• Exercise 5.15
• Exercise 5.17
• Exercise 14.10

Paper Review: (If you are behind the TAMU firewall, following the link should give you access to the full text of the paper.)

Homework 4: Due Mon, Mar 24, 10:20 AM

Problems:

• Exercise 6.5
• Suppose we have a distributed system whose topology is an n-element r ing instead of a clique. Assume the message delay on every link is in the range [d-u,d]. What is the tight bound on the skew obtainable in this case? Answering this requires two things: an algorithm for the upper bound (together with a proof of its skew) and a matching lower bound on the skew.
• Exercise 13.2
• Exercise 13.5
• Using the model presented in Chapter 7, specify the binary consensus problem (as in Section 5.1.2) for n processes, up to f of which may crash.
• Prove that, in the failure-free case, if a broadcast service provides both single-source FIFO ordering and total ordering, then it also provides causal ordering.
• Exercise 8.9

Paper Reviews: (If you are behind the TAMU firewall, following the links should give you access to the full text of the papers.)

Homework 5: Due Wed, Apr 2, 10:20 AM

Problems:

• Exercise 8.10
• Exercise 9.5
• Exercise 9.6
• Exercise 9.7

(No paper review)

Homework 6: Due Mon, Apr 21, 10:20 AM

This assignment has fewer problems and more paper reviews (3) than the others. It is now complete.

Problems:

• Exercise 10.5. Justify your answers by either providing an algorithm or proving an impossibility result.
• Exercise 10.11
• Exercise 15.5
• Exercise 15.7

Paper Reviews: (If you are behind the TAMU firewall, following the links should give you access to the full text of the papers.)

Homework 7: Due Tue, Apr 29, 10:20 AM

Problems:

• Exercise 16.16
• Exercise 16.17
• Exercise 16.22

Paper Review: (If you are behind the TAMU firewall, following the link should give you access to the full text of the paper.)