Dotted Version Vectors

Let's learn what dotted version vectors are and how they provide scaling of 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 (n1,n2)(n_1,n_2) represents all the numbers from 11 to n1n_1 plus the number n2n_2.

For example, the pair (4,7)(4,7) represents the sequence [1,2,3,4,7][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 v1v_1, v2v_2 the relationship v1v2v_1\leq v_2 holds if the sequence represented by v1v_1 is a subset of the sequence represented by v2v_2. More specifically:

  • (m)(m)(m) \leq (m^{\prime}) if mmm \leq m^{\prime}
  • (m)(m,n)(m)\leq(m^{\prime},n^{\prime}) if mmm=m+1=nm\leq m^{\prime} \vee m=m^{\prime}+1=n^{\prime}
  • (m,n)(m)(m,n)\leq(m^{\prime}) if nmn\leq m^{\prime}
  • (m,n)(m,n)(m,n)\leq(m^{\prime},n^{\prime}) if nm(mmn=n)n\leq m^{\prime} \vee (m\leq m^{\prime}\wedge n=n^{\prime})

Get hands-on with 1200+ tech skills courses.