Lamport timestamp

The Lamport timestamp is a simple logical clock algorithm used to determine the order of events in a distributed computer system. Because the nodes or processes of such a system are never perfectly synchronized, wall-clock readings cannot be trusted to say which event came first. The algorithm instead gives each process a numerical software counter, increments it before each event, attaches its value to every message it sends, and on receiving a message sets its own counter past the larger of the two values. In this way the happened-before ordering, in which one event precedes another if it can be reached by moving forward within a process or by following a message from sender to receiver, is captured numerically with very little overhead. The resulting timestamps give a partial ordering of events: if one event happened before another its timestamp is smaller, while events in processes that never exchange messages, directly or indirectly, are concurrent and nothing can be said about their order. The method is named after its creator Leslie Lamport and is the conceptual starting point for the more advanced vector clock.