In the field of distributed systems, a logical clock is a mechanism that tracks the number of events that have occurred and is designed to capture causal dependencies between those events.
Specifically, if event 'e1' happens before event 'e2', then the logical clock should reflect that relationship:
(e1 -> e2) -> (T (e1) < T (e2)) p>
The Lamport Clock Algorithm is a particular implementation of a logical clock that follows the following steps:
Step 1 : Upon initialization, set each node's local clock variable 't' to 0.
,center>
( t = 0) …. (1)
Step 2 : For every local event, increment the value of 't' by 1.
( t = t + 1) …. (2)
Step 3 : When a message 'm' is sent from a node, increment the value of 't' by 1 and attach the new value of 't' to the message.
The message is then sent over the network link.
(t = t + 1) … (3)
Send (t, m) ... (4)
Step 4 : When a node receives a message '(t', m)' over the network link, update its local clock variable 't' to the maximum value of 't' received so far and increment it by 1.
The node then delivers the message 'm' to the application.
Receive (t’, m) … (5)
Do t: max (t, t’) + 1 … (6) Were,
1. t’ = time stamp attached to the message.
2. t: max(t, t’) = greatest time stamp ( either local or server time stamp)end on.
In this algorithm, every node maintains a counter 't', which is incremented for every local event. The value of 't' after an event 'e' occurs is denoted by 'L(e)'. Every message sent over the network is attached with the current value of 't'.
When a recipient receives a message, it moves its clock forward to the timestamp in the message (if it is greater than the local counter) and increments it.
Properties :
- If event a occurs before event b, then,
a -> b then L(a) < L(b). - However,
L (a) < L (b)does not implya -> b. - It is possible that
L (a) = L (b)fora ≠ b.