Logical clock

A logical clock is a component of a computer system that is used for giving events a unique time stamp. Unlike a "normal" real-time clock that measures the physical time, the only claim to a logical clock that it emits monotonically increasing values ​​, so that the causal order of events is evident.

The purpose of such a clock is to be able to bring events to their timestamps in a final order. In a system with only one process is trivial: one only needs a counter. Interesting is the problem if you try to synchronize the logical clocks of multiple processes ( Distributed systems ) so that you can specify a causal order for the entire system. Therefore, it is especially important to look at the sending and receiving of messages as events and provided with a time stamp.

The fact that this term is used to synchronize, has historical reasons: First, attempts to determine the causal order on real-time clocks that need to be kept in sync with this purpose. Later it was realized that it is sufficient and much easier to work with an abstract concept of time, which is limited to the determination of causality.

Watches condition and causal order

So you can now be derived from the timestamps of a causal ( semi-) order, the logical clock has the (weak) consistency criterion for watch (or watches the weak condition) meet (see also Happened -before relation):

• If the event was a cause of the event, e1 e2, then the time stamp of E1 is smaller than that of E2. In character:

The strong consistency criterion for watch (or watches strong condition) also requires that the converse must be true:

• If the time stamp of less than the E1 E2, then the event e1 e2 was a cause of the event. In character:

If the strong watches condition is satisfied, one can also read off the clock which events are concurrent.

From these relations results in general only a partial order. Not from each pair of two events can be said that the one was the cause of the other: The events can also be (causally ) to be independent, we then speak of concurrency (or even simultaneity - although that term is not exact in: see relativity of simultaneity ). In character:

For clarity to write ( Leslie Lamport ) to express the causal dependency of events

In this case, however, one must be careful that the arrow for you " is the cause of" not to be confused with the semantic implication ( ).

Application

Logical clocks find application mainly in areas in which causality and reliability play a major role. This is the case especially in transaction systems. They are used to process incoming messages and commands in the correct order. In particular, it is possible using logical clocks to design a reliable, well-ordered multicast protocol.

However, the method for synchronizing clocks of logic in large systems are generally quite inefficient. Therefore, time is in the "popular" protocols that have been found on the Internet dissemination, whether with the "physical" work - you simply hopes that the clocks of the various computers are not too different (an example for this is HTTP). Or one is limited to the synchronization of only two systems (client -server model ) using sequence numbers (as in TCP).

Method

There are various methods to realize consistent logical clocks in distributed systems. The best known are probably:

• The Lamport clock - it complies with relatively little effort, the (weak) Konsistenzkriterum.
• Vector clocks are a little more complicated, but suffice it to the strong Konsistenzkriterum.

There are also various methods to real-time clocks over a network to synchronize. See, inter alia, the algorithm of Cristian and the Network Time Protocol.

• Theoretical computer science
• Distributed system
• Database Theory
• Clock