Lamport timestamps
Encyclopedia
The algorithm of Lamport timestamps is a simple algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering
of events with minimal overhead, and conceptually provide a starting point for the more advanced Vector clock method.
Distributed algorithms such as resource synchronization often depend on some method of ordering events to function. For example, consider a system with two processes and a disk. The processes send messages to each other, and also send messages to the disk requesting access. The disk grants access in the order the messages were sent. Now, imagine process 1 sends a message to the disk asking for access to write, and then sends a message to process 2 asking it to read. Process 2 receives the message, and as a result sends its own message to the disk. Now, due to some timing delay, the disk receives both messages at the same time: how does it determine which message happened-before
the other? (
happens-before 
if one can get from 
to 
by a sequence of moves of two types: moving forward while remaining in the same process, and following a message from its sending to its reception.) A logical clock algorithm provides a mechanism to determine facts about the order of such events.
Leslie Lamport
invented a simple mechanism by which the happened-before
ordering can be captured numerically. A Lamport logical clock is a monotonically incrementing software counter maintained in each process.
It follows some simple rules:
Conceptually, this logical clock can be thought of as a clock that only has meaning in relation to messages moving between processes. When a process receives a message, it resynchronizes its logical clock with that sender.
and 
occurring in the same process, and 
being the timestamp for a certain event 
, it is necessary that 
never equals 
.
Therefore it is necessary that:
then 
, where 
means happened-before
.
This relation only goes one way, and is called clock consistency condition: if one event comes before another, then that event's logical clock comes before the other's. The strong clock consistency condition, which is two way (if
then 
), can be obtained by other techniques such as vector clocks. Using only a simple Lamport clock, only a partial causal ordering can be inferred from the clock.
However, via the contrapositive, it's true that
implies 
. So, for example, if 
then 
cannot have happened-before 
.
Another way of putting this is that
means that 
may have happened-before 
, or be incomparable with 
in the happened-before ordering, but 
did not happen after 
.
Nevertheless, Lamport timestamps can be used to create a total ordering of events in a distributed system by using some arbitrary mechanism to break ties (e.g. the ID of the process). The caveat is that this ordering is artifactual and cannot be depended on to imply a causal relationship.
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
of events with minimal overhead, and conceptually provide a starting point for the more advanced Vector clock method.
Distributed algorithms such as resource synchronization often depend on some method of ordering events to function. For example, consider a system with two processes and a disk. The processes send messages to each other, and also send messages to the disk requesting access. The disk grants access in the order the messages were sent. Now, imagine process 1 sends a message to the disk asking for access to write, and then sends a message to process 2 asking it to read. Process 2 receives the message, and as a result sends its own message to the disk. Now, due to some timing delay, the disk receives both messages at the same time: how does it determine which message happened-before
Happened-before
In computer science, the happened-before relation is a means of ordering events based on the potential causal relationship of pairs of events in a concurrent system, especially asynchronous distributed systems...
the other? (
happens-before if one can get from to by a sequence of moves of two types: moving forward while remaining in the same process, and following a message from its sending to its reception.) A logical clock algorithm provides a mechanism to determine facts about the order of such events.Leslie Lamport
Leslie Lamport
Leslie Lamport is an American computer scientist. A graduate of the Bronx High School of Science, he received a B.S. in mathematics from the Massachusetts Institute of Technology in 1960, and M.A. and Ph.D. degrees in mathematics from Brandeis University, respectively in 1963 and 1972...
invented a simple mechanism by which the happened-before
Happened-before
In computer science, the happened-before relation is a means of ordering events based on the potential causal relationship of pairs of events in a concurrent system, especially asynchronous distributed systems...
ordering can be captured numerically. A Lamport logical clock is a monotonically incrementing software counter maintained in each process.
It follows some simple rules:
- A process increments its counter before each event in that process;
- When a process sends a message, it includes its counter value with the message;
- On receiving a message, the receiver process sets its counter to be greater than the maximum of its own value and the received value before it considers the message received.
Conceptually, this logical clock can be thought of as a clock that only has meaning in relation to messages moving between processes. When a process receives a message, it resynchronizes its logical clock with that sender.
Considerations
For every two events and occurring in the same process, and being the timestamp for a certain event , it is necessary that never equals .Therefore it is necessary that:
- The logical clock be set so that there is minimum of one clock "tick" (increment of the counter) between events
and 
; - In a multiprocess or multithreaded environment, it might be necessary to attach the process ID (PID) or any other unique ID to the timestamp so that it is possible to differentiate between events
and 
which may occur simultaneously in different processes.
Implications
A Lamport clock may be used to create a partial causal ordering of events between processes. Given a logical clock following these rules, the following relation is true: if then , where means happened-beforeHappened-before
In computer science, the happened-before relation is a means of ordering events based on the potential causal relationship of pairs of events in a concurrent system, especially asynchronous distributed systems...
.
This relation only goes one way, and is called clock consistency condition: if one event comes before another, then that event's logical clock comes before the other's. The strong clock consistency condition, which is two way (if
then ), can be obtained by other techniques such as vector clocks. Using only a simple Lamport clock, only a partial causal ordering can be inferred from the clock.However, via the contrapositive, it's true that
implies . So, for example, if then cannot have happened-before .Another way of putting this is that
means that may have happened-before , or be incomparable with in the happened-before ordering, but did not happen after .Nevertheless, Lamport timestamps can be used to create a total ordering of events in a distributed system by using some arbitrary mechanism to break ties (e.g. the ID of the process). The caveat is that this ordering is artifactual and cannot be depended on to imply a causal relationship.
Lamport's logical clock in distributed systems
- In a distributed system, it is not possible in practice to synchronize timeClock synchronizationClock synchronization is a problem from computer science and engineering which deals with the idea that internal clocks of several computers may differ. Even when initially set accurately, real clocks will differ after some amount of time due to clock drift, caused by clocks counting time at...
across entities (typically thought of as processes) within the system; hence, the entities can use the concept of a logical clock based on the events through which they communicate. - If two entities do not exchange any messages, then they probably do not need to share a common clock; events occurring on those entities are termed as concurrent events.
- Among the processes on the same local machine we can order the events based on the local clock of the system.
- When two entities communicate by message passing, then the send event is said to 'happen before' the receive event, and the logical order can be established among the events.
- A distributed system is said to have partial order if we can have a partial order relationship among the events in the system. If 'totality', i.e., causal relationship among all events in the system can be established, then the system is said to have total order.