Vector clocks

给定的 Lamport 时间戳 $L(a)$ 和 $L(b)$ 并且 $L(a) < L(b)$，我们推断不出 $a \rightarrow b$ 或者 $a || b$.¹

要区分平行的这些事件，需要 vertor clocks:

• 假定分布式系统中有 $n$ 个节点，$N = \langle N_{1}, N_{2},…, N_{n}\rangle$
• 事件 $a$ 的向量时间戳写成 $V(a) = \langle t_{1}, t_{2},…, t_{n} \rangle$
• $t_{i}$ 是 $N_{i}$ 节点发生时间的数量
• 每个​节点​都有一个当前的向量时间戳 $T$
• 节点 $N_{i}$ 上的事件，向量时间戳 $T[i]$ 递增。
• 每个消息都附带上向量时间戳
• 接收者将消息中的向量时间戳合并到本地

除了标量和向量之间的区别之外，向量时钟算法与 Lamport 时钟非常相似。一个节点的向量时钟的初始值是系统中的每个节点的事件数，也就是 0。每当节点 $N_{i}$ 发生事件时，它就会增加其向量钟中的第 $i$ 个条目（它自己的条目）。(In practice, this vector is often implemented as a map from node IDs to integers rather than an array of integers. 在实践中，这里的向量通常是节点 ID 对应 Integer 的 map，而不是 Integer 的数组。)。当一个消息在网络上被发送时，发送者当前的向量时间戳被附加到该消息上。最后，当一个消息被接收时，接收者将消息中的向量时间戳与它的本地时间戳合并，方法是取两个向量的元素的最大值，然后接收者增加它自己的条目。

Vector clocks algorithm

Vector clocks example

假定节点向量是 $N = \langle A, B, C \rangle$:

事件 $e$ 的向量时间戳是一系列事件的集合， $e$ 和它的因果以来：${e} \cup {a | a \rightarrow e}$²​³

比如，$\langle2, 2, 0\rangle$，第一个 2 是表示来自于 $A$ 的两个事件，第二个 2 是表示来自于 $B$ 的两个事件，并且没有来自于 $C$ 的事件。

Vector clocks ordering

Define the following order on vector timestamps(in a system with $n$ nodes):

• $T = T’ \iff T[i] = T’[i]$ for all $i \in {1, …, n}$
• $T \le T’ \iff T[i] \le T’[i]$ for all $\in {1, …, n}$
• $T < T’ \iff T \le T’$ and $T \neq T’$
• $T || T’ \iff T > T’$ and $T’ > T$

$V(a) \le V(b) \iff ({a} \cup {e | e \rightarrow a}) \subseteq ({b} \cup{} {e | e \rightarrow b})$

Properties of this order:

• $(V(a) < V(b)) \iff (a \rightarrow b)$
• $(V(a) = V(b)) \iff (a = b)$
• $(V(a) \rVert V(b)) \iff (a \rVert b)$

然后，我们对向量的时间戳进行部分排序。如果第一个向量的每个元素都小于或等于第二个向量的相应元素，我们就说一个向量小于或等于另一个向量。如果一个向量小于或等于另一个向量，并且它们至少有一个元素是不同的，那么这个向量就严格小于另一个向量。然而，如果一个向量在一个元素中的值较大，而另一个向量在另一个元素中的值较大，那么这两个向量是不可比的。例如，$T = \langle2, 2, 0\rangle$ 和 $T’ = \langle0, 0, 1\rangle$ 是不可比的，因为 $T[1] > T’[1]$ 但 $T[3] < T’[3]$。

向量时间戳的部分顺序与发生之前关系所定义的部分顺序完全对应。因此，向量时钟算法为我们提供了一种在实践中计算发生前关系的机制。