Lamport Clocks And Vector Clocks
--
The concept of time is fundamental to our way of thinking about ordering of events in a system. Since physical clocks in a distributed system can drift among each other, it will be very difficult to enforce total ordering among all events in a distributed system across a set of processes.
As a first step, let’s try to move away from a physical clock for measuring order in a distributed system. Instead let’s try to create a logical clock that assigns an unique id to events in a distributed system, such that it captures the casual order among events in a distributed system. Let’s define the distributed system as set of processes. Each process execution is modeled as a sequence of events. The processes communicate with each other via messages.
The happens before relation (<) is defined as follows.
1. If a, b are events in the same process, if a occurs before b, then a < b
2. if a denotes sending of message in process-a and b denotes receipt of message in process-b then a < b
3. The relation is transitive, a < b and b < c => a < c
To capture the happens before relation, Lamport introduced a form of clock by name Lamport clocks.
Lamport clocks are defined as follows.
1. It’s a counter within a single process that increments from 1. Events within a process is assigned an unique id based on the counter value. Thus all compute and messaging events within a process are assigned an unique value
2. When sending a message from process-a, we set C(a) = C(a) + 1, then pass on C(a) as part of the message.
3. On recipient of message in process-b we set C(b) = max(C(b) + 1, C(a))
Lamport clocks can guarantee that if a < b then C(a) < C(b). However it can’t guarantee, that if C(a) < C(b) then event a happened before b.
A casuality relation states that if an event e1 possibly influences the generation of event e2, then e1 < e2. What’s better way to establish such a relation than relying on message passing among the processes. Message passing establishes a happens before order on events based on the communication pattern. For example if a process receives a message as event A, processes the message as B and sends out a new message to another process as event C then it’s assumed event A influenced the generation of event C and hence A & C are casually related, A < C.
Then comes the vector clocks into this picture.
In a system with N processes, each process keeps a vector timestamp TS[N]
1. In Process i,
a. TS[j] is logical time of process j as process i knows about it.
b. TS[i] is the lamport clock of process i.2. When a new event is generated, TS[i] = TS[i] + 1
3. When sending a message we copy the vector clock to the message
4. On recipient of message with vector timestamp MTS we set the TS of process i as,
TS[k] = max(TS[k], MTS[k]) for k = 1 to N
The happened before ordering in vector clocks is defined as follows.
e1 < e2 iff TS(e1)[k] <= TS(e2)[k] for k = 1 to N
* atleast one of the value of indices of e1 should be less than e2’s value
The timestamp of an event would tell us what all events among all processes would have influenced the generation of that particular event. So if e1 < e2, then e2 would have witnessed all the events that has been witnessed by e1. With vector clocks we can ascertain if TS(e1) < TS(e2) then e1 < e2.
Lamport Clock Image courtesy
http://www.cs.jhu.edu/~yairamir/cs437/week13/img006.gif
References