Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1 handwiki -- 1481 2022-10-24 01:34:50

Video Upload Options

Do you have a full video?

Confirm

Are you sure to Delete?
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
HandWiki. Lamport Timestamps. Encyclopedia. Available online: https://encyclopedia.pub/entry/30834 (accessed on 09 October 2024).
HandWiki. Lamport Timestamps. Encyclopedia. Available at: https://encyclopedia.pub/entry/30834. Accessed October 09, 2024.
HandWiki. "Lamport Timestamps" Encyclopedia, https://encyclopedia.pub/entry/30834 (accessed October 09, 2024).
HandWiki. (2022, October 24). Lamport Timestamps. In Encyclopedia. https://encyclopedia.pub/entry/30834
HandWiki. "Lamport Timestamps." Encyclopedia. Web. 24 October, 2022.
Lamport Timestamps
Edit

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. 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 [math]\displaystyle{ A }[/math] sends a message to the disk requesting write access, and then sends a read instruction message to process [math]\displaystyle{ B }[/math]. Process [math]\displaystyle{ B }[/math] 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: [math]\displaystyle{ A }[/math] happens-before [math]\displaystyle{ B }[/math] if one can get from [math]\displaystyle{ A }[/math] to [math]\displaystyle{ B }[/math] 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. Lamport invented a simple mechanism by which the happened-before ordering can be captured numerically. A Lamport logical clock is a numerical software counter value 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 re-synchronizes 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.

clock algorithm simple algorithm generalization

1. Algorithm

The algorithm follows some simple rules:

  1. A process increments its counter before each event in that process;
  2. When a process sends a message, it includes its counter value with the message;
  3. 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.[1]

In pseudocode, the algorithm for sending is:

# event is known time = time + 1; # event happens send(message, time); 

The algorithm for receiving a message is:

(message, time_stamp) = receive(); time = max(time_stamp, time) + 1; 

2. Considerations

For every two different events [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] occurring in the same process, and [math]\displaystyle{ C(x) }[/math] being the timestamp for a certain event [math]\displaystyle{ x }[/math], it is necessary that [math]\displaystyle{ C(a) }[/math] never equals [math]\displaystyle{ C(b) }[/math].

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 [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math];
  • In a multi-process or multi-threaded 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 [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] which may occur simultaneously in different processes.

3. Causal Ordering

For any two events, [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math], if there’s any way that [math]\displaystyle{ a }[/math] could have influenced [math]\displaystyle{ b }[/math], then the Lamport timestamp of [math]\displaystyle{ a }[/math] will be less than the Lamport timestamp of [math]\displaystyle{ b }[/math]. It’s also possible to have two events where we can’t say which came first; when that happens, it means that they couldn’t have affected each other. If [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] can’t have any effect on each other, then it doesn’t matter which one came first.

4. 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 [math]\displaystyle{ a \rightarrow b }[/math] then [math]\displaystyle{ C(a) \lt C(b) }[/math], where [math]\displaystyle{ \rightarrow\, }[/math] means happened-before.

This relation only goes one way, and is called the 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 [math]\displaystyle{ C(a) \lt C(b) }[/math] then [math]\displaystyle{ a \rightarrow b }[/math]), 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 [math]\displaystyle{ C(a) \nless C(b) }[/math] implies [math]\displaystyle{ a \nrightarrow b }[/math]. So, for example, if [math]\displaystyle{ C(a) \geq C(b) }[/math] then [math]\displaystyle{ a }[/math] cannot have happened-before [math]\displaystyle{ b }[/math].

Another way of putting this is that [math]\displaystyle{ C(a) \lt C(b) }[/math] means that [math]\displaystyle{ a }[/math] may have happened-before [math]\displaystyle{ b }[/math], or be incomparable with [math]\displaystyle{ b }[/math] in the happened-before ordering, but [math]\displaystyle{ a }[/math] did not happen after [math]\displaystyle{ b }[/math].

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.

5. 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.

A single entity cannot have two events occur simultaneously. If the system has total order we can determine the order among all events in the system. If the system has partial order between processes, which is the type of order Lamport's logical clock provides, then we can only tell the ordering between entities that interact. Lamport addressed ordering two events with the same timestamp (or counter): "To break ties, we use any arbitrary total ordering [math]\displaystyle{ \lt }[/math] of the processes."[1] Thus two timestamps or counters may be the same within a distributed system, but in applying the logical clocks algorithm events that occur will always maintain at least a strict partial ordering.

Lamport clocks lead to a situation where all events in a distributed system are totally ordered. That is, if [math]\displaystyle{ a \rightarrow b }[/math], then we can say [math]\displaystyle{ a }[/math] actually happened before [math]\displaystyle{ b }[/math].

Note that with Lamport’s clocks, nothing can be said about the actual time of [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math]. If the logical clock says [math]\displaystyle{ a \rightarrow b }[/math], that does not mean in reality that [math]\displaystyle{ a }[/math] actually happened before [math]\displaystyle{ b }[/math] in terms of real time.

Lamport clocks show non-causality, but do not capture all causality. Knowing [math]\displaystyle{ a \rightarrow c }[/math] and [math]\displaystyle{ b \rightarrow c }[/math] shows [math]\displaystyle{ c }[/math] did not cause [math]\displaystyle{ a }[/math] or [math]\displaystyle{ b }[/math] but we cannot say which initiated [math]\displaystyle{ c }[/math].

This kind of information can be important when trying to replay events in a distributed system (such as when trying to recover after a crash). If one node goes down, and we know the causal relationships between messages, then we can replay those messages and respect the causal relationship to get that node back up to the state it needs to be in.[2]

References

  1. Lamport, L. (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. http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf. 
  2. "Clocks and Synchronization — Distributed Systems alpha documentation". http://books.cs.luc.edu/distributedsystems/clocks.html. 
More
Information
Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
View Times: 733
Entry Collection: HandWiki
Revision: 1 time (View History)
Update Date: 24 Oct 2022
1000/1000
ScholarVision Creations