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. They are named after their creator, Leslie Lamport.
Contents
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. For example process A sends a message to the disk requesting write access, and then sends a read instruction message to process B. Process B receives the message, and as a result sends its own read request message to the disk. If there is a timing delay causing the disk to receive both messages at the same time, it can determine which message happened-before the other: (
Lamport invented a simple mechanism by which the happened-before ordering can be captured numerically. A Lamport logical clock is an incrementing software counter maintained in each process.
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. The above mentioned vector clock is a generalization of the idea into the context of an arbitrary number of parallel, independent processes.
Algorithm
The algorithm 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 counter of the recipient is updated, if necessary, to the greater of its current counter and the timestamp in the received message. The counter is then incremented by 1 before the message is considered received.
In a Pseudocode format, the algorithm for sending:
time = time+1; time_stamp = time; send(message, time_stamp);The algorithm for receiving a message:
(message, time_stamp) = receive(); time = max(time_stamp, time)+1;Considerations
For every two different events
Therefore it is necessary that:
- The logical clock be set so that there is a minimum of one clock "tick" (increment of the counter) between events
a andb ; - 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
a andb 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
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
However, via the contrapositive, it's true that
Another way of putting this is that
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.