Properties5
| Type | Article |
| Author | Giridhar Manepalli |
| Date | Nov 16, 2022 |
| URL | https://www.exhypothesi.com/clocks-and-causality/?ref=refind |
| Note created | Nov 16, 2022 |
because of clock drifts and/or assumptions around network time delays, timestamps from conventional clocks are not always mutually comparable, and therefore events cannot be reliably ordered using timestamps from conventional clocks
If multiple nodes in a distributed system can rely on a centralized logical clock, then most issues discussed in this article become irrelevant.
For a distributed logical clock to function, we expect each of the participating nodes to have its own clock that cooperates with clocks on other nodes in order to produce the next timestamp
because events may occur faster than the notification of such events between nodes, events may be unaware of some past events. Events that occur without the knowledge of each other are called concurrent events.
Each timestamp produced by a logical clock consists of two components:
- an id for the current event, and
- the ids of some or all events the node is aware of thus far (aka history).
Richness in the timestamp therefore needs to be purchased with space or time complexity. And different designs make different choices in this area. However, a common compaction scheme used by different clock designs is to track history with the use of numbers for event ids. Under this compaction scheme, an event with timestamp [ 5 ] not only represents that the event id is the number 5, but that the node generating that event has knowledge of the existence of (some) event [ 4 ] (because there could be multiple [ 4 ] events) and possibly all events prior to and equal to [ 4 ], depending on the clock.
If the knowledge from event A is used to produce event B, then A caused B. If B merely happened before C, but event C did not use the knowledge from event B, then B and C are not causally related, just temporally so.
Most applications, for simplicity, use temporal relationship as a proxy for causality.
Timestamps produced by a Lamport clock take the least amount of space, O(1) in terms of the number of nodes in the system, compared to other clock designs. A Lamport timestamp captures the event id and some history of events the node is aware of at the time the event is generated, all using a single unique number. When a node generated event id [ 5 ], the node claims to have knowledge of some event that is numbered [ 4 ] and no knowledge of any other event that is numbered [ 5 ] or above.
Lamport timestamps do not capture which node generated the event.
A Lamport clock can be implemented as follows:
- Timestamps are sequential numbers associated with events.
- Each node maintains its own sequence starting with number 0.
- When an event is generated, the node increments its number by one and associates that number with the event.
- When a node learns an event from another node, the node ensures its number to the highest of its own number and the event number it learned from the other node.
Lamport timestamps can be used to arrange events in a historical (i.e., happened-before) order after the fact.