Vector clock

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 a vector (equivalently, a 1-dimensional array) of n logical clocks, one clock per process. Besides maintaining its own clock, every process also keeps track of the largest value of each of the other processes' clocks that it has so far been informed of.

The clock updates proceed as follows, where VCi denotes the value of the vector clock maintained by process i:

Example of a system of vector clocks. Events in the blue region are the causes leading to event B4, whereas those in the red region are the effects of event B4.

History

Lamport originated the idea of logical Lamport clocks in 1978. However, the logical clocks in that paper were scalars, not vectors. The generalization to vector time was developed several times, apparently independently, by different authors in the early 1980s. At least 6 papers contain the concept. The papers canonically cited in reference to vector clocks are Colin Fidge’s and Friedemann Mattern’s 1988 works, as they (independently) established the name "vector clock" and the mathematical properties of vector clocks.

Partial ordering property

Vector clocks allow for the partial causal ordering of events. Defining the following:

Properties:

Relation with other orders

Limitations under Byzantine failures

Vector clocks can reliably detect causality in distributed systems subject to crash failures. However, when processes behave arbitrarily or maliciously—as in the Byzantine failure model—causality detection becomes fundamentally impossible , rendering vector clocks ineffective in such environments. This impossibility result holds for all variants of vector clocks, as it stems from core limitations inherent to the problem of causality detection under Byzantine faults.

Other mechanisms

See also