Dotted Version Vectors

Dotted version vectors is a technique that makes it possible to successfully identify concurrent versions, and allows the version vectors to scale with the number of servers.

The following characteristic of this technique allows it to achieve this.

Characteristic that makes it possible to scale version vectors

Each entry in the vector is not a single number anymore, but a pair of numbers. This can encode a sequence of numbers that are not fully sequential but contain one gap.

The pair $(n_1,n_2)$ represents all the numbers from $1$ to $n_1$ plus the number $n_2$.

For example, the pair $(4,7)$ represents the sequence $[1,2,3,4,7]$. Note that the second number is optional and some entries can still be a single number. This can be leveraged to keep track of concurrency between multiple versions.

The order between the two versions is now defined in terms of the contains relationship on the corresponding sequences. So, for vectors $v_1$, $v_2$ the relationship $v_1\leq v_2$ holds if the sequence represented by $v_1$ is a subset of the sequence represented by $v_2$. More specifically:

• $(m) \leq (m^{\prime})$ if $m \leq m^{\prime}$
• $(m)\leq(m^{\prime},n^{\prime})$ if $m\leq m^{\prime} \vee m=m^{\prime}+1=n^{\prime}$
• $(m,n)\leq(m^{\prime})$ if $n\leq m^{\prime}$
• $(m,n)\leq(m^{\prime},n^{\prime})$ if $n\leq m^{\prime} \vee (m\leq m^{\prime}\wedge n=n^{\prime})$