Vector clock

from Wikipedia, the free encyclopedia

A vector clock is a software component (or protocol ) used to assign unique time stamps to messages . It is therefore a logical clock that allows the events in a distributed system to be assigned a causal order based on a time stamp ( sequentialization ) and, in particular, to determine the concurrency of events. It is an extension of the Lamport watch , which also meets the strong watch conditions . Vector clocks were developed independently by several scientists, notably Colin J. Fidge , Friedemann Mattern, and Frank Bernhard Schmuck .

Example of a system of vector clocks

functionality

The procedure for operating vector clocks is as follows: Similar to the Lamport clock, each process keeps a counter that is incremented with each event (especially when sending and receiving messages). But unlike the Lamport clock, the clock of each process does not just consist of a counter, but of a vector (or an array or an associative list) of counters: Each process remembers the count of all other processes, if known is. The current status of the clock is attached to every message sent.

With each event only the own counter is increased. If a message is received, an element-wise maximum is formed from the current and the received vector in order to determine the new status of the clock.

The implementation of a vector clock looks like this as pseudocode : Routine for sending a message: 

Uhr[PID]= Uhr[PID]+1;
Zeitstempel= Uhr;
sende(Nachricht,Zeitstempel);

It should be PID is a fixed, predetermined and unique for each process identifier , such as a process ID or an IP address (or a combination of these two). The clock fields for the processes that have not yet received a message are assumed to be zero.

Routine for receiving a message: 

(Nachricht,Zeitstempel)= empfange();
Uhr[PID]= Uhr[PID]+1;
 
for (Prozesse P) do begin
    Uhr[P]= max(Uhr[P],Zeitstempel[P]);
end;

Partial order

In order to be able to decide on the basis of the time stamp which message (or which event) is causally dependent on which other , a partial order relation is defined above the levels of the vector clock : an event A is a cause of event B if the counter for each Process in time stamp C (A) is less than or equal to the counter in time stamp C (B) for the corresponding process and is smaller for at least one of these counters. Formally:

Since the implication is valid in both directions for vector clocks, they satisfy the strong clock condition.

An implementation of the above order relation in pseudocode (A and B are the time stamps to be compared, the question is whether A was a cause of B): 

procedure ist_ursache(A,B):
    mindestens_ein_element_strikt_kleiner = NEIN;
    for (Prozesse P) do begin
        if ( A[P] > B[P] ) then return NEIN;
        if ( A[P] < B[P] ) then mindestens_ein_element_strikt_kleiner := JA;
    end;
     
    return mindestens_ein_element_strikt_kleiner;
end procedure;

Concurrency

It is entirely possible that neither A → B nor B → A applies, the procedure mentioned for the calls 

ist_ursache(A,B)
ist_ursache(B,A)

returns NO as an answer: The events are then concurrent, one also writes A || B . The decisive advantage of vector clocks over the simpler Lamport clocks is that the time stamp makes it possible to identify which events are concurrent. This results from the validity of the strong clock condition. It should be noted here that in contrast to the cause relation , concurrency is not transitive .

literature