13 Lamport Clocks

(Ci, id)

• Ci - highest known logical time
• id - id of the process/server

1. Internal Event a
   • Ci := Ci + 1
2. Event “send m”
   • Ci ​:= Ci​+1
   • ts(m)=Ci​
3. Event Receive m with ts(m)
   • Ci = max(Ci , ts) + 1

(C1, id1) > (C2, id2) iff C1 > C2 or (C1 = C2 and id1 > id2).
(C1, id1) = (C2, id2) iff C1 = C2 and id1= id2.

Totally Ordered Multicast

ensures every server applies operations in exactly the same order

An example execution:

1. Roughly simultaneously, +1000 arrives at S1, and %1 arrives at S2. Both are added to
   respective queues with timestamps (1,1) for S1 and (1,2) for S2.
2. S1 sends a request for ACK +1000 to S2.
3. S2 sends a request for ACK 1% to S1.
4. S2 receives ACK, +1000 (1,1) is at the front of the queue.
   a. marks locally that 2 have acknowledged +1000, applies +1000
   b. Increments Lamport ts to (2,2)
   c. (Note that any new messages received at this point would be timestamped as (3,2) for example)
5. S1 receives ACK %1(1,2), enqueues behind +1000 (1,1). Thus, does not apply anything.
6. S2 receives ACK %1, applies %1.
7. S1 receives ACK +1000, thus has ACKS=2, and can apply +1000, and then apply %1.