Description
1.(5 points) Prove the claim on page 20 of the slide deck on Synchronization. “If every Ci(·), Cj (·) satisfy κ1 and κ2,
then C(·) satisfies κ0.”
2.(5 points) Prove the claim on page 29 of the slide deck on Synchronization. “a → b if and only if VC(a) <
VC(b).”
3.(5 points) Suppose we use the protocol on page 22 of the slide deck on Synchronization for totally ordered multicast
with logical (but not vector) clocks. Does the protocol achieve causally ordered multicast? If your answer is ‘yes,’
provide a proof. If your answer is ‘no,’ provide a counterexample.
4.(5 points) Consider page 40 of the slide deck on Synchronization. Devise a protocol by which n processes that can
communicate with one another can organize themselves into a ring as shown to the right of the slide. What are the
time- and space-efficiencies of your protocol?
5.(5 points) Page 41 of the slide deck on Synchronization (and your textbook) asserts that the number of messages
between request and fulfilment for the Decentralized algorithm is unbounded. Propose a way to bound this, and give
the corresponding tight lower- and upper-bounds for the number of messages.
6.(5 points) Page 41 of the slide deck on Synchronization (and your textbook) asserts that the number of messages
between request and fulfilment for the Token Ring algorithm is unbounded. Propose a way to bound this, and give the
corresponding tight lower- and upper-bounds for the number of messages.
7.(5 points) Consider the example we discussed at the start in the context of consistency — it is on pages 1–2 of the
slide deck on Consistency and Figure 7-7 in the textbook. Is 001110 a legal output? Justify briefly. In particular, if
you say ‘yes,’ you should identify the notion of “legal” that you adopt.
