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 process, 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 < of the processes." 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.
Read more about this topic: Lamport Timestamps
Famous quotes containing the words logical, distributed and/or systems:
“Nature’s law says that the strong must prevent the weak from living, but only in a newspaper article or textbook can this be packaged into a comprehensible thought. In the soup of everyday life, in the mixture of minutia from which human relations are woven, it is not a law. It is a logical incongruity when both strong and weak fall victim to their mutual relations, unconsciously subservient to some unknown guiding power that stands outside of life, irrelevant to man.”
—Anton Pavlovich Chekhov (1860–1904)
“Taking food alone tends to make one hard and coarse. Those accustomed to it must lead a Spartan life if they are not to go downhill. Hermits have observed, if for only this reason, a frugal diet. For it is only in company that eating is done justice; food must be divided and distributed if it is to be well received.”
—Walter Benjamin (1892–1940)
“People stress the violence. That’s the smallest part of it. Football is brutal only from a distance. In the middle of it there’s a calm, a tranquility. The players accept pain. There’s a sense of order even at the end of a running play with bodies stewn everywhere. When the systems interlock, there’s a satisfaction to the game that can’t be duplicated. There’s a harmony.”
—Don Delillo (b. 1926)