CSE 124 Lecture Notes - Lecture 14: Total Order, Global Variable, Joule
5 May 2018
School
Department
Course
Professor
The Lamport Clock Algorithm
Before executing an event a, Ci ← Ci + 1
- SET event time C(a) ← Ci
1. Before executing an event b, Ci ← Ci + 1
- SET event time C(b) ← Ci
2. Send the local clock in the message m
3. On process Pj, receiving a message m:
- SET Cj and receive event time C(c) ← 1 + max{Cj, C(m)}
Why do we pick 3?
- The clock value that we assign to the event is defined by the equation
Note: C seems like a global variable, but it’s NOT!
- The only time C is ever shared is if it is in a message!
Ordering ALL Events
Break ties: append the process # to each event:
1. Process Pi timestamps event e w/ Ci (e).i
2. C(a).i < C(b).j when:
- C(a) < C(b), OR C(a) = C(b) and i < j
Now for ANY 2 events: C(a) < C(b), OR C(b) < C(a)
- Called total ordering
Totally-Ordered Multicast
Multicast - I want to send a message to a set of destinations
Idea: place events in a local queue
- Sorted by increasing C(x)
- Need a protocol that dequeue operations in the same order!
What do we NOT guarantee?
- Operations are applied the same moment
TOM (Almost correct)
1. On receiving an event from client, broadcast to others (including yourself!)
1. On receiving an event from replica:
a) Add to local queue
b) Broadcast an acknowledgment to every process (including yourself)
2. On receiving an acknowledgement:
- Mark event acknowledged
3. Remove and process events EVERYONE has “ack’d” from head of queue
TOM (Correct)
1. On receiving an event from client, broadcast to others (including yourself!)
1. On receiving or processing an event from replica:
c) Add to local queue
Document Summary
Before executing an event a , c i c i + 1: before executing an event b , c i c i + 1, send the local clock in the message m, on process p j , receiving a message m: Note: c seems like a global variable , but it"s not! Break ties: append the process # to each event: process p i timestamps event e w/ c i ( e ). i, c(a). i < c(b). j when: Set c j and receive event time c( c ) 1 + max {c j , c( m )} The clock value that we assign to the event is defined by the equation. The only time c is ever shared is if it is in a message! C(a) < c(b), or c(a) = c(b) and i < j. Now for any 2 events: c(a) < c(b), or c(b) < c(a) Multicast - i want to send a message to a set of destinations.
