1. Bulletin Board Dilemma

Reading material:

• Section 5.2 Logical Clocks, T&vS 1st Ed.
• Section 6.2 Logical Clocks, T&vS 2nd Ed.

An interesting dilemma regarding Vector Clocks concerns year 2009's Exercise 4, task 3, section b). Please familiarize yourself with the task description before reading its model answer. Now,

1. Describe the full state of the given Bulletin Board System: processes, channels, and messages
2. Argue for or against the model answer. Is it correct? Under what circumstances should local events increment the vector clock, if any?

2. Vector Clocks

Reading material:

• Section 5.2.2 Vector Timestamps, T&vS 1st Ed.
• Section 6.2.2 Vector Clocks, T&vS 2nd Ed.

Three processes communicate exchanging messages. Each process P_i maintains its own vector clock V_i. All messages have a timestamp t based on the sender's clock; using t the receiver updates its own clock.

Assume that when P₂'s clock was (5,4,2) it received a message from P₁. The timestamp of the message was (7,3,5).

1. What did P₂ learn about the history of its colleagues?
2. Show that the relation V_j[i] <= V_i[i] always holds.
3. Show that e->e' => V(e) < V(e').

For #3, we do not expect a full formal proof; it is sufficient to sketch the idea of the proof.

3. Decentralized Total Ordering

Background reading:

• Section 5.2.1 Lamport timestamps, T&vS 1st Ed.
• Section 6.2.1 Lamport's logical clocks, T&vS 2nd Ed.

Describe in detail the decentralized implementation of total ordering. Show that it performs correctly:

1. in all hold-back queues the messages are in the same order
2. after having received all ack's the message at the head of the hold-back queue can be sure that nobody will ever appear in front of it.

Is it strictly necessary that each message is acknowledged?

Total ordering is easy to implement as a centralized service. How?

Give some examples where total ordering is needed.