{"history":[],"article":{"id":"c9cb0832-7e95-44a4-91b2-815edbdf66b0","title":"Lamport timestamp","slug":"lamport-timestamp","content":":::summary\n:::\n\n# \nThe **Lamport timestamp** algorithm is a simple [logical clock algorithm](https://bliptext.com/articles/logical-clock-algorithm) used to determine the order of events in a [distributed computer system](https://bliptext.com/articles/distributed-computer-system).\nAs different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a [partial ordering](https://bliptext.com/articles/partially-ordered-set) of events with minimal overhead, and conceptually provide a starting point for the more advanced [vector clock](https://bliptext.com/articles/vector-clock) method.\nThe algorithm is named after its creator, [Leslie Lamport](https://bliptext.com/articles/leslie-lamport).\nDistributed algorithms such as resource synchronization often depend on some method of ordering events to function.\nFor example, consider a system with two processes and a disk.\nThe processes send messages to each other, and also send messages to the disk requesting access.\nThe disk grants access in the order the messages were received.\nFor 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.\nIf there is a timing delay causing the disk to receive both messages at the same time, it can determine which message [happened-before](https://bliptext.com/articles/happened-before) the other: A happens-before B if one can get from A to B 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.\nA logical clock algorithm provides a mechanism to determine facts about the order of such events.\nNote that if two events happen in different processes that do not exchange messages directly or indirectly via third-party processes, then we say that the two processes are concurrent, that is, nothing can be said about the ordering of the two events.\nLamport invented a simple mechanism by which the happened-before ordering can be captured numerically.\nA Lamport logical clock is a numerical software counter value maintained in each process.\nConceptually, this logical clock can be thought of as a clock that only has meaning in relation to messages moving between processes.\nWhen a process receives a message, it re-synchronizes its logical clock with that sender.\nThe above-mentioned vector clock is a generalization of the idea into the context of an arbitrary number of parallel, independent processes.\n\n# Algorithm\nThe algorithm follows some simple rules:\nIn [pseudocode](https://bliptext.com/articles/pseudocode), the algorithm for sending is:\ntime = time + 1;\nsend(message, time);\nThe algorithm for receiving a message is:\n(message, timestamp) = receive;\ntime = max(timestamp, time) + 1;\n\n# Considerations\nFor every two different events a and b occurring in the same process, and C(x) being the timestamp for a certain event x, it is necessary that C(a) never equals C(b).\nTherefore it is necessary that:\n\n# Causal ordering\nFor any two events, a and b, if there’s any way that a could have influenced b, then the Lamport timestamp of a will be less than the Lamport timestamp of b. 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.\nIf a and b can’t have any effect on each other, then it doesn’t matter which one came first.\n\n# Implications\nA Lamport clock may be used to create a [partial ordering](https://bliptext.com/articles/partially-ordered-set) of events between processes.\nGiven a logical clock following these rules, the following relation is true: if then C(a) < C(b), where means happened-before.\nThis 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 C(a) < C(b) then ), can be obtained by other techniques such as vector clocks.\nUsing only a simple Lamport clock, only a partial causal ordering can be inferred from the clock.\nHowever, via the [contrapositive](https://bliptext.com/articles/contrapositive), it's true that implies.\nSo, for example, if then a cannot have happened-before b.\nAnother way of putting this is that C(a) < C(b) means that a may have happened-before b, or be incomparable with b in the happened-before ordering, but a did not happen after b.\nNevertheless, Lamport timestamps can be used to create a [total ordering](https://bliptext.com/articles/total-ordering) of events in a distributed system by using some arbitrary mechanism to break ties (e.g., the ID of the process).\nThe caveat is that this ordering is artificial and cannot be depended on to imply a causal relationship.\n\n# Lamport's logical clock in distributed systems\nIn a distributed system, it is not possible in practice to [synchronize time](https://bliptext.com/articles/clock-synchronization) 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.\nIf 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.\nAmong the processes on the same local machine we can order the events based on the local clock of the system.\nWhen 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.\nA distributed system is said to have partial order if we can have a partial order relationship among the events in the system.\nIf 'totality', i.e., causal relationship among all events in the system, can be established, then the system is said to have total order.\nA single entity cannot have two events occur simultaneously.\nIf the system has total order we can determine the order among all events in the system.\nIf 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.\nLamport addressed ordering two events with the same timestamp (or counter): \"To break ties, we use any arbitrary total ordering < of the processes.\"\nThus 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.\nLamport clocks lead to a situation where all events in a distributed system are totally ordered.\nThat is, if, then we can say a actually happened before b.\nNote that with Lamport’s clocks, nothing can be said about the actual time of a and b. If the logical clock says C(a) < C(b), that does not mean in reality that a actually happened before b in terms of real time.\nLamport clocks show non-causality, but do not capture all causality.\nKnowing and shows c did not cause a or b but we cannot say which initiated c.\nThis kind of information can be important when trying to replay events in a distributed system (such as when trying to recover after a crash).\nIf 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.\n\n# Alternatives to potential causality\nThe happened-before relation captures potential causality, not true causality.\nIn 2011-12, [Munindar Singh](https://bliptext.com/articles/munindar-singh) proposed a declarative, multiagent approach based on true causality called information protocols.\nAn information protocol specifies the constraints on communications between the agents that constitute a distributed system.\nHowever, instead of specifying message ordering (e.g., via a state machine, a common way of representing protocols in computing), an information protocol specifies the information dependencies between the communications that agents (the protocol's endpoints) may send.\nAn agent may send a communication in a local state (its communication history) only if the communication and the state together satisfy the relevant information dependencies.\nFor 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.\nA remarkable thing about information protocols is that although emissions are constrained, receptions are not.\nSpecifically, agents may receive communications in any order whatsoever -- receptions simply bring information and there is no point delaying them.\nThis means that information protocols can be enacted over unordered communication services such as [UDP](https://bliptext.com/articles/user-datagram-protocol).\nThe bigger idea is that of application semantics, the idea of designing distributed systems based on the content of the messages, an idea implicated in the [end-to-end principle](https://bliptext.com/articles/end-to-end-principle).\nCurrent 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.\nBut if we had a suitable way of doing application semantics, then we wouldn't need such communication services.\nAn unordered, unreliable communication service would suffice.\nThe real value of information protocols approach is that it provides the foundations for an application semantics approach.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T21:46:38.030Z","updated_at":"2025-01-25T21:46:38.030Z","search_vector":"'lamport':1 'timestamp':2","search_content":" \n \n\n# \nThe **Lamport timestamp** algorithm is a simple [logical clock algorithm](https://bliptext.com/articles/logical-clock-algorithm) used to determine the order of events in a [distributed computer system](https://bliptext.com/articles/distributed-computer-system).\nAs different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a [partial ordering](https://bliptext.com/articles/partially-ordered-set) of events with minimal overhead, and conceptually provide a starting point for the more advanced [vector clock](https://bliptext.com/articles/vector-clock) method.\nThe algorithm is named after its creator, [Leslie Lamport](https://bliptext.com/articles/leslie-lamport).\nDistributed algorithms such as resource synchronization often depend on some method of ordering events to function.\nFor example, consider a system with two processes and a disk.\nThe processes send messages to each other, and also send messages to the disk requesting access.\nThe disk grants access in the order the messages were received.\nFor 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.\nIf there is a timing delay causing the disk to receive both messages at the same time, it can determine which message [happened-before](https://bliptext.com/articles/happened-before) the other: A happens-before B if one can get from A to B 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.\nA logical clock algorithm provides a mechanism to determine facts about the order of such events.\nNote that if two events happen in different processes that do not exchange messages directly or indirectly via third-party processes, then we say that the two processes are concurrent, that is, nothing can be said about the ordering of the two events.\nLamport invented a simple mechanism by which the happened-before ordering can be captured numerically.\nA Lamport logical clock is a numerical software counter value maintained in each process.\nConceptually, this logical clock can be thought of as a clock that only has meaning in relation to messages moving between processes.\nWhen a process receives a message, it re-synchronizes its logical clock with that sender.\nThe above-mentioned vector clock is a generalization of the idea into the context of an arbitrary number of parallel, independent processes.\n\n# Algorithm\nThe algorithm follows some simple rules:\nIn [pseudocode](https://bliptext.com/articles/pseudocode), the algorithm for sending is:\ntime = time + 1;\nsend(message, time);\nThe algorithm for receiving a message is:\n(message, timestamp) = receive;\ntime = max(timestamp, time) + 1;\n\n# Considerations\nFor every two different events a and b occurring in the same process, and C(x) being the timestamp for a certain event x, it is necessary that C(a) never equals C(b).\nTherefore it is necessary that:\n\n# Causal ordering\nFor any two events, a and b, if there’s any way that a could have influenced b, then the Lamport timestamp of a will be less than the Lamport timestamp of b. 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.\nIf a and b can’t have any effect on each other, then it doesn’t matter which one came first.\n\n# Implications\nA Lamport clock may be used to create a [partial ordering](https://bliptext.com/articles/partially-ordered-set) of events between processes.\nGiven a logical clock following these rules, the following relation is true: if then C(a) < C(b), where means happened-before.\nThis 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 C(a) < C(b) then ), can be obtained by other techniques such as vector clocks.\nUsing only a simple Lamport clock, only a partial causal ordering can be inferred from the clock.\nHowever, via the [contrapositive](https://bliptext.com/articles/contrapositive), it's true that implies.\nSo, for example, if then a cannot have happened-before b.\nAnother way of putting this is that C(a) < C(b) means that a may have happened-before b, or be incomparable with b in the happened-before ordering, but a did not happen after b.\nNevertheless, Lamport timestamps can be used to create a [total ordering](https://bliptext.com/articles/total-ordering) of events in a distributed system by using some arbitrary mechanism to break ties (e.g., the ID of the process).\nThe caveat is that this ordering is artificial and cannot be depended on to imply a causal relationship.\n\n# Lamport's logical clock in distributed systems\nIn a distributed system, it is not possible in practice to [synchronize time](https://bliptext.com/articles/clock-synchronization) 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.\nIf 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.\nAmong the processes on the same local machine we can order the events based on the local clock of the system.\nWhen 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.\nA distributed system is said to have partial order if we can have a partial order relationship among the events in the system.\nIf 'totality', i.e., causal relationship among all events in the system, can be established, then the system is said to have total order.\nA single entity cannot have two events occur simultaneously.\nIf the system has total order we can determine the order among all events in the system.\nIf 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.\nLamport addressed ordering two events with the same timestamp (or counter): \"To break ties, we use any arbitrary total ordering < of the processes.\"\nThus 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.\nLamport clocks lead to a situation where all events in a distributed system are totally ordered.\nThat is, if, then we can say a actually happened before b.\nNote that with Lamport’s clocks, nothing can be said about the actual time of a and b. If the logical clock says C(a) < C(b), that does not mean in reality that a actually happened before b in terms of real time.\nLamport clocks show non-causality, but do not capture all causality.\nKnowing and shows c did not cause a or b but we cannot say which initiated c.\nThis kind of information can be important when trying to replay events in a distributed system (such as when trying to recover after a crash).\nIf 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.\n\n# Alternatives to potential causality\nThe happened-before relation captures potential causality, not true causality.\nIn 2011-12, [Munindar Singh](https://bliptext.com/articles/munindar-singh) proposed a declarative, multiagent approach based on true causality called information protocols.\nAn information protocol specifies the constraints on communications between the agents that constitute a distributed system.\nHowever, instead of specifying message ordering (e.g., via a state machine, a common way of representing protocols in computing), an information protocol specifies the information dependencies between the communications that agents (the protocol's endpoints) may send.\nAn agent may send a communication in a local state (its communication history) only if the communication and the state together satisfy the relevant information dependencies.\nFor 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.\nA remarkable thing about information protocols is that although emissions are constrained, receptions are not.\nSpecifically, agents may receive communications in any order whatsoever -- receptions simply bring information and there is no point delaying them.\nThis means that information protocols can be enacted over unordered communication services such as [UDP](https://bliptext.com/articles/user-datagram-protocol).\nThe bigger idea is that of application semantics, the idea of designing distributed systems based on the content of the messages, an idea implicated in the [end-to-end principle](https://bliptext.com/articles/end-to-end-principle).\nCurrent 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.\nBut if we had a suitable way of doing application semantics, then we wouldn't need such communication services.\nAn unordered, unreliable communication service would suffice.\nThe real value of information protocols approach is that it provides the foundations for an application semantics approach.","revisionCount":0},"hasMore":false,"nextCursor":null}

History