A logical clock is a mechanism to capture the chronological relationships in a distributed system. To implement a logical clock, every node in the distributed system should agree on the order in which events occur rather than the time at which they occurred
To implement Lamport's logical clocks, each process Pi maintains a local counter G. These counters are updated as follows steps:
a) Before executing an event Pi executes Gf- G+1.
b) When process Pi sends a message m to Pj it sets m's timestamp ts (m) equal to G after having executed the previous step.
c) Upon the receipt of a message m, process Pj adjusts its own local counter as 0f- max{0,ts(m)}, after which it then executes the first step and delivers the message to the application.
Before delving into how logical clocks can be used to order causally related events, it is essential to understand the "happens before" relation and causal relation.
"happens-before"
—\> denotes the "happens before" relation and it is identified as follows:
occurred before B
process
Causal Relation
Two events A and B are said to be causally related if there exists a "happens before" relationship i.e A—\>B
Ordering Causally Related Events
A logical clock assigns a clock value Ci(event) to each event in a process i in the following ways such that causality is preserved (timestamps reflect the order of events)
Partial Ordering
If event A "happens before" event B ie A—\>B then clock values are assigned such that clock(A)\<clock(B) according to the following rules
• Each event A in i is time-stamped Ci(A)- the value of clock of process i when A occurred
• Ci is incremented by 1 for each event in i
• In addition, if A is a send of message m from process i to j, then on receive of m, Cj = max (Cj, Ci(A)+1) These events are considered causal.