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:
“Grammar is a tricky, inconsistent thing. Being the backbone of speech and writing, it should, we think, be eminently logical, make perfect sense, like the human skeleton. But, of course, the skeleton is arbitrary, too. Why twelve pairs of ribs rather than eleven or thirteen? Why thirty-two teeth? It has something to do with evolution and functionalism—but only sometimes, not always. So there are aspects of grammar that make good, logical sense, and others that do not.”
—John Simon (b. 1925)
“A junky runs on junk time. When his junk is cut off, the clock runs down and stops. All he can do is hang on and wait for non-junk time to start.”
—William Burroughs (b. 1914)
“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)