2.1.2　向量时钟

逻辑时钟可以捕获潜在的因果关系，但是，这并不意味着一定有因果关系，逻辑时钟条件只是一个必要条件，并不是充分条件。分布式系统中的所有事件可能需要一个更强的时钟条件：

e→f当且仅当clock(e)<clock(f)。

该条件可按如下方式实现：为每一进程i赋一个长度为n的向量Vi，n是系统中所有进程的数量。每一个执行的事件都被赋一个本地向量。

每个向量都初始化为0，即：Vi[j] = 0，其中i, j = 1, …, N。进程i在每一个事件之前增加本地向量元素的值，Vi[j] = Vi[j] +1。当进程i发送消息的时候，会将本地向量Vi和消息一起发送。当进程j接收消息时，会将接收向量和本地向量的元素逐个进行比较，并将本地向量设置为两者之中较大的值，Vj[i] = max(Vi[i], Vj[i]), i = 1, …, N。

给定两个向量V和V'，V=V'当且仅当V[i] = V'[i], i = 1, …, N，并且V≤V'当且仅当V[i]≤V'[i], i = 1, …, N。如果至少存在一个j(1≤j≤N)，使得V[j]<V'[j]，并且，对所有的i≠j，其中，1≤i≤N，V[i]≤V'[i]，则V<V'。对任意两个事件e和f，e→f当且仅当V(e)<V(f)。如果既不满足V(e)<V(f)，又不满足V(f)<V(e)，那么两个事件是并发的。

图2-3中，我们为图2-1示例中的所有事件都赋了向量时间值。

图2-3　向量时钟