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, clock, distributed and/or systems:
“The truth is, that common-sense, or thought as it first emerges above the level of the narrowly practical, is deeply imbued with that bad logical quality to which the epithet metaphysical is commonly applied; and nothing can clear it up but a severe course of logic.”
—Charles Sanders Peirce (1839–1914)
“What says the Clock in the Great Clock Tower?
And all alone comes riding there
The King that could make his people stare,
Because he had feathers instead of hair.
A slow low note and an iron bell.”
—William Butler Yeats (1865–1939)
“Indiana was really, I suppose, a Democratic State. It has always been put down in the book as a state that might be carried by a close and careful and perfect organization and a great deal of—[from audience: “soap”Ma reference to purchased votes, the word being followed by laughter].
I see reporters here, and therefore I will simply say that everybody showed a great deal of interest in the occasion, and distributed tracts and political documents all through the country.”
—Chester A. Arthur (1829–1886)
“Before anything else, we need a new age of Enlightenment. Our present political systems must relinquish their claims on truth, justice and freedom and have to replace them with the search for truth, justice, freedom and reason.”
—Friedrich Dürrenmatt (1921–1990)