Lamport timestamp: Difference between revisions
Content deleted Content added
No edit summary |
Add reference to another article |
||
| Line 16: | Line 16: | ||
==Lamport's logical clock in distributed systems== |
==Lamport's logical clock in distributed systems== |
||
* In a distributed system, it is not possible in practice to synchronize time 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. |
* In a distributed system, it is not possible in practice to [[Clock synchronization|synchronize time ]] 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. |
* 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. |
* Among the processes on the same local machine we can order the events based on the local clock of the system. |
||
Revision as of 21:11, 20 April 2008
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:
- The counter is incremented before each event is issued at the process;
- When a process sends a message, it includes the counter value with the message;
- 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:
- The logical clock be set so that there is minimum of one clock "tick" (increment of the counter) between events a and b;
- 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.
Lamport's logical clock in distributed systems
- In a distributed system, it is not possible in practice to synchronize time 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.
See also
References
- Leslie Lamport (1978). "Time, clocks, and the ordering of events in a distributed system" (PDF). Communications of the ACM. 21 (7): 558–565. doi:10.1145/359545.359563.