Vector clock

A Vektoruhr is a software component (or a protocol) for assigning unique time stamps of messages. It is therefore a logical clock that allows you to assign ( sequencing ) and in particular to determine the concurrency of events the events in a distributed system based on a time stamp, a causal order. It represents an extension of Lamport clock, which also satisfies the strong condition watches. Vector clocks have been developed by several scientists independently, especially by Colin J. Fidge, Friedemann Mattern and Frank Bernhard jewelry.

Operation

The procedure during the operation of vector clocks are as follows: Similarly to the Lamport clock each process executes a counter, which is for each event (in particular the transmitting and receiving of messages ) is increased. But unlike the Lamport clock is here the clock of each process, not only from a counter, but from a vector (or an array or associative list) of counters: Each process keeps track of the count of all other processes, as far as the known is. The current state of the clock is appended each message you send.

At each event, only the personal counter is always increased. When a message is received, an element -wise maximum is formed in order to determine the new state of the clock from the current and the received vector.

As a pseudo-code implementation of a Vektoruhr looks like this: routine to send a message:

Clock [ PID ] = clock [ PID ] 1; Timestamp = clock; send ( message, timestamp); This PID is a fixed, predetermined and unique identifier, for example, a process ID or an IP address (or a combination of these two ) for each process. The clock for the processes from which no message has been received fields are assumed to be zero.

Routine for receiving a message:

( Message, timestamp) = receive (); Clock [ PID ] = clock [ PID ] 1;   for ( P processes ) do begin      Clock [P ] = max ( clock [P ], timestamp [P ]); end; partial order

To be able to decide based on the time stamp which message (or what event ) is taken from whichever other causally dependent is defined above the stands of Vektoruhr a partial order relation: an event A is a cause of event B if the counter for each process in the time stamp C (A) is less than or equal to the count in the time stamp C ( B) is strictly smaller for the corresponding process and for at least one of these counters. Formal:

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

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

Ist_ursache procedure (A, B):      mindestens_ein_element_strikt_kleiner = NO;      for ( P processes ) do begin          if ( A [ P ]> B [P]) then return NO;          if ( A [ P] < B [ P] ) then mindestens_ein_element_strikt_kleiner: = YES;      end;            return mindestens_ein_element_strikt_kleiner; end procedure; concurrency

It is quite possible that neither A nor B → B → A is true, therefore, the above procedure in the calls

Ist_ursache ( A, B) ist_ursache ( B, A) each NO returns in response: The events are then concurrently, one also writes A | | B. It is precisely the main advantage of vector clocks over the simpler Lamport clocks, that it is possible due to the time stamp to identify which events are concurrent. This follows from the validity of the strong watches condition. It must be noted that, in contrast to the cause concurrency relation is not transitive.