Logical Clock

Measure the passage of time in an asynchronous distributed system:
• Each process p keeps an integer called logical clock lp, initially 0.
• Any time an event occurs at process p, the logical clock lp is incremented by one unit.
• When a process sends a message, it timestamps the message with the value of its logical clock at the moment the message is sent and tags the message with that timestamp. The timestamp of event e is denoted by t(e).
• When a process p receives a message m with timestamp lm, p incrementsits timestamp in the following way: lp = max(lp, lm) + 1.

happened-before relation (e1 → e2):
We say that an event e1 may potentially have caused another event e2, denoted as e1 → e2, if the following relation applies:
• e1 and e2 occurred at the same process p and e1 occurred before e2.
• e1 corresponds to the transmission of a message m at a process p and e2 to the reception of the same message at some other process q.
• there exists some event e such that e1 → e' and e' → e2.

If the events are timestamped with logical clocks, then e1 → e2 ⇒ t(e1) < t(e2). The opposite implication is not true.