Lamport timestamps

From Wikipedia, the free encyclopedia

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.

It follows some simple rules:

1. The counter is incremented before each event is issued at the process;
2. When a process sends a message, it includes the counter value with the message;
3. On receiving a message a process computes the counter as the maximum between their own value and the received value and then applies rule 1 before timestamping the event as received.

Considerations: For every two events, a and b occurring in the same process, and being C(x) the timestamp for a certain event x, it is necessary that C(a)!=C(b) is always true.

Therefore it is necessary that:

1. The internal physical clock be set so that there is minimum of one clock "tick" between events a and b;
2. 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 and b which may occur simultaneously in different processes.

[edit] Lamport's logical clock in distributed systems

• In distributed systems it is not practically possible to synchronize time across two systems. Hence the systems can use concept of logical clock based on the events through which they communicate.
• If two systems do not exchange any messages then probably they don't need to share common clock. And events occuring on those systems are termed as concurrent events.
• Among the processes on same local machine we can order the events based on the local clock of the system.
• When two systems 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 partial order relationship among the events in the system. If 'totality' i.e. causal relationship among all events in system can be established then the system is said to have total order.

[edit] References

Leslie Lamport (1978). "Time, clocks, and the ordering of events in a distributed system". Communications of the ACM 21 (7): 558-565. DOI:10.1145/359545.359563.