Logical clock

A logical clock is a component of a computer system that is used to give events a unique time stamp . Unlike a "normal" real-time clock , which measures the physical time , the only requirement of a logical clock is that it outputs strictly monotonically increasing values so that the causal order of the events can be identified.

The purpose of such a clock is to be able to bring events into a final order via their time stamp . In a system with only one process , this is trivial: you only need one counter. The problem becomes interesting when one tries to synchronize the logical clocks of several processes ( distributed systems ) in such a way that one can specify a causal order for the overall system. For this, it is above all necessary to regard the sending and receiving of messages as events and to give them a time stamp.

There are historical reasons why the term synchronize is used for this : At first, an attempt was made to determine the causal order using real-time clocks , which must be kept as synchronized as possible for this purpose. It was later recognized that it is sufficient and much easier to work with an abstract concept of time that is limited to determining causality.

Clock condition and causal order

The happened-before-relation indicates that an event takes place before an event ( ). Either a and b are events on the same process or a is the sending and b the receiving of a message. This relationship can also be read to permit a cause of could be. An actual causal relationship is not required. If so , it is also true that it could not have happened before (and accordingly cannot be a cause). ${\ displaystyle \ rightarrow}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a \ rightarrow b}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a \ rightarrow b}$ ${\ displaystyle b}$ ${\ displaystyle a}$

The set of all clocks in the system is represented by the function , which assigns a number (time stamp) to each event. In order to derive a causal ( half ) order from the time stamps , the (weak) consistency criterion for clocks (or the weak clock condition ) must be fulfilled. ${\ displaystyle C}$

If the event occurs before the event (in the sense of the happened-before relation), then the time stamp of is less than that of . In characters: ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle b}$

${\ displaystyle a \ rightarrow b \ Rightarrow C (a) <C (b)}$

These relations generally result in only a partial order . Not every pair of two events can be said to be the cause of the other. We then write:

{\ displaystyle a \ nrightarrow b}

If neither of the two events has the other, they are independent , one then speaks of concurrency (or even simultaneity - although this term is not exact in itself: see relativity of simultaneity ). In characters:

{\ displaystyle a \ nrightarrow b \ land \ b \ nrightarrow a \ Leftrightarrow a \ | b \ Leftrightarrow b \ | a}

An event is always parallel to itself: ${\ displaystyle \ forall a: a \ | a}$

Concurrency is symmetric , but not transitive : but : Let's imagine that event a and c are held at the same location so that a cause of c is so . Somewhere else the event b takes place completely independently, so it applies and or and . From the transitivity it would follow that also applies - but it does not, since according to the assumption it is true, i.e. a is the cause of c. ${\ displaystyle a \ | b \ Leftrightarrow b \ | a}$ ${\ displaystyle a \ | b \ land b \ | c \ \ not \ Rightarrow \ a \ | c}$ ${\ displaystyle a \ rightarrow c}$ ${\ displaystyle b \ | a}$ ${\ displaystyle b \ | c}$ ${\ displaystyle a \ | b}$ ${\ displaystyle c \ | b}$ ${\ displaystyle a \ | c}$ ${\ displaystyle a \ rightarrow c}$

The strong consistency criterion for clocks (or strong clock condition ) also requires that the converse must also apply:

If the timestamp is less than that of , then the event took place before the event . In characters: ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle b}$

${\ displaystyle C (a) <C (b) \ Rightarrow a \ rightarrow b}$

If the strong clock condition is met, you can also read on the clock which events are concurrent .

application

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

However, the methods for synchronizing logical clocks in large systems are generally quite inefficient . That is why the “popular” protocols that have found widespread use on the Internet either work with “physical” time - one simply hopes that the clocks of the various computers do not run too differently (an example of this is HTTP ). Or you limit yourself to the synchronization of only two systems ( client-server model) using sequence numbers (as with TCP ).

Procedure

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

the Lamport clock - it meets the (weak) consistency criterion with relatively little effort.
Vector clocks are a bit more complex, but meet the strong consistency criterion.

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

Individual evidence

↑ Lamport, Leslie (1978). "Time, Clocks and the Ordering of Events in a Distributed System" , Communications of the ACM , 21 (7), 558-565.

[1] Lamport, Leslie (1978). "Time, Clocks and the Ordering of Events in a Distributed System" , Communications of the ACM , 21 (7), 558-565.