Vector clock
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 .
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
- CJ Fidge, Timestamps in message-passing systems that preserve the partial ordering , In K. Raymond, editor, Proc. of the 11th Australian Computer Science Conference (ACSC'88) , pp. 56-66, February 1988.
- Reinhard Schwarz and Friedemann Mattern , Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail (PDF; 278 kB), in Distributed Computing , No. 3 Vol. 7, Springer 1994.