The Lamport timestamp algorithm is a simple logical clock 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.
The algorithm is named after its creator, Leslie Lamport.
Distributed algorithms such as resource synchronization often depend on some method of ordering events to function.
The disk grants access in the order the messages were received.
A logical clock algorithm provides a mechanism to determine facts about the order of such events.
[1] 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.
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.
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.
A Lamport clock may be used to create a partial ordering of events between processes.
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 artificial and cannot be depended on to imply a causal relationship.
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.
"[2] 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.
Note that with Lamport’s clocks, nothing can be said about the actual time of
Lamport clocks show non-causality, but do not capture all causality.
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.
In 2011-12, Munindar Singh proposed a declarative, multiagent approach based on true causality called information protocols.
An information protocol specifies the constraints on communications between the agents that constitute a distributed system.
For example, an information protocol for an e-commerce application may specify that to send a Quote with parameters ID (a uniquifier), item, and price, Seller must already know the ID and item from its state but can generate whatever price it wants.
A remarkable thing about information protocols is that although emissions are constrained, receptions are not.
Specifically, agents may receive communications in any order whatsoever -- receptions simply bring information and there is no point delaying them.
This means that information protocols can be enacted over unordered communication services such as UDP.
Current approaches largely ignore semantics and focus on providing application-agnostic ("syntactic") message delivery and ordering guarantees in communication services, which is where ideas like potential causality help.
But if we had a suitable way of doing application semantics, then we wouldn't need such communication services.