Vector clock - Wikipedia

submited by

Style Pass

2021-08-05 07:00:07

A vector clock is a data structure used for determining the partial ordering of events in a distributed system and detecting causality violations. Just as in Lamport timestamps, inter-process messages contain the state of the sending process's logical clock. A vector clock of a system of N processes is an array/vector of N logical clocks, one clock per process; a local "largest possible values" copy of the global clock-array is kept in each process.

Denote V C i {\displaystyle VC_{i}} as the vector clock maintained by process i, the clock updates proceed as follows:[1]

Without using the specific name "vector clock", the concept of a vector clock was first mentioned[2] in a 1986 paper by Rivka Ladin and Barbara Liskov where they use the term "multipart timestamp".[3] To quote from page 31 of the Liskov/Ladin paper:

We solve this problem by using multipart timestamps, where there is one part for each replica. Thus, if there are n replicas, a timestamp t is