电脑clocks-(电脑clock是什么键)

Lamport Clocks回顾

矢量时钟

实现矢量时钟

计算两个矢量时钟的最大值

在两个矢量上应用<运算符

但是这种比较足以描述因果关系吗？

工作的例子

确定事件的因果历史所有事件的矢量时钟都可比吗？

通讯协定

那么消息交换花了多长时间？

完整的协议表示？

正确性及其违反

重要术语

FIFO（或有序）交付

Lamport Clocks与因果关系一致，但没有对其进行描述（或确定）。

如果A-> B，则表示LC（A）<LC（B）

但是，这种含义是不可逆的：

如果LC（A） B

由Friedemann Mattern和Colin Fidge独立发明。 两人于1988年撰写了有关该主题的论文。

但是对于矢量时钟，这种关系是可逆的：

A->B <==> LC(A) < LC(B)

Lamport Clock仅是一个整数，而Vector Clock是一个整数序列。 （“矢量”一词是在编程意义上使用的，而不是在幅度和方向上使用的）

在实现矢量时钟之前，必须满足两个前提条件：

1.您必须预先知道组成系统的进程数 2.所有过程都必须同意矢量中时钟值出现的顺序 在这种情况下，我们知道我们有三个进程Alice，Bob和Carol，向量中值的顺序将按进程名称的字母顺序进行排序。

因此，每个进程将分别为Alice，Bob和Carol创建其自己的矢量时钟副本，其初始值为[0,0,0]。

然后，通过应用以下规则来管理矢量时钟：

1.每个进程都维护着一个初始化为0的整数向量-对于每个我们希望与之通信的进程

2.在每个事件上，进程都会在向量时钟中增加其自身位置：这还包括内部事件，这些事件不会导致消息的发送或接收

3.发送消息时，每个进程都将其时钟的当前状态作为元数据与消息有效负载一起包括在内

4.收到消息时，每个进程都使用规则max（VC（self），VC（msg））更新其在矢量时钟中的位置。

如果在某个时间点，进程Alice中的矢量时钟的状态变为[17,0,0]，则意味着就Alice而言，它已记录了17个事件，而它认为进程Bob和 Carol还没有录制任何事件。

但是，我们如何取两个向量的最大值？

我们将在这里使用max的概念是每个元素的比较（也称为逐点最大值）

例如，如果我的VC是[1，12,4]，而我收到VC [7,0,2]，则逐点最大值将是[7,12,4]

<在两个向量的上下文中是什么意思？

这是通过对向量中的每个元素进行逐点比较并拒绝VC（A）= VC（B）的特殊情况来计算的。 那是：

对于VC中的所有元素，VC（A）i≤VC（B）i && VC（A）≠VC（B）

意味着对于矢量时钟A和B中的所有元素，VC（A）[i]处的元素必须小于或等于VC（B）[i]和VC（A）≠VC（B）处的元素

考虑两个矢量时钟VC（A）= [2,2,0]和VC（B）= [1,2,3]

VC（A）<VC（B）吗？

因此，对每个元素进行逐点比较可以得出：

Index VC(A)i ≤ VC(B)i Outcome

0 2 ≤ 1 false

1 2 ≤ 2 true

2 0 ≤ 3 true

然后，通过将所有结果进行“与”运算，得出总结果：

假&&真实&&真实=假

因此，我们可以得出结论：VC（A）不小于VC（B）。

好的，让我们以另一种方式进行比较。

VC（B）<VC（A）吗？

同样，我们对每个元素执行逐点比较，得出：

Index VC(B)i ≤ VC(A)i Outcome

0 1 ≤ 2 true

1 2 ≤ 2 true

2 3 ≤ 0 false

总体结果仍然为false，因为true && true && false = false

由于VC（B）不小于VC（A）并且VC（A）不小于VC（B），我们处于不确定状态。 关于这两个矢量时钟代表的事件，我们只能说它们是并发的，独立的或因果无关的（这三个术语是同义词）。

让我们看看如何在发送和接收消息时处理三个进程（Alice，Bob和Carol）中的矢量时钟：

发送完这些消息后，我们可以查看每个进程中矢量时钟如何随时间变化的历史记录。

如果我们选择一个特定的事件A，让我们确定A的因果历史中的事件。

A是发生在流程Bob中的一个事件，通过回顾Bob的其他事件，我们可以看到一个事件序列：

此外，通过跟踪导致事件A的消息，我们可以看到另一事件序列：

这里的共同点是：

1.事件A具有因果历史中所有事件的时空图可达性。也就是说，无需将笔从纸上抬起或及时倒退，我们就可以将A过去的任何事件与A连接起来。 2.从A向后看，我们可以看到其因果历史中的所有矢量时钟值均满足关系发生前的情况：也就是说，所有先前的矢量时钟值均小于A的矢量时钟值。 除此之外，通过查看A之后的事件（换句话说，A在某个将来事件的因果历史中），我们可以看到所有这些向量时钟值都大于A。

考虑事件A和B。是否可以使用先发生关联来关联它们的矢量时钟值？

为了满足这种关系，一个事件的矢量时钟必须小于另一事件的矢量时钟（按点表示）。 但是在这种情况下，这显然是不正确的：

VC(A) = [2,4,1]VC(B) = [0,3,2][2,4,1] < [0,3,2] = false[0,3,2] < [2,4,1] = false

矢量时钟都不大于或小于另一个。 因此，关于这两个事件，我们只能说它们是独立的，并发的或因果无关的，或者A || B．

但是，这确实意味着我们可以轻松地告诉计算机如何确定两个事件是否因果相关。 我们要做的就是比较这两个事件的向量时钟值。 如果我们可以确定一个小于另一个，则可以肯定知道矢量时钟值较小的事件发生在矢量时钟值较大的事件的因果历史中。

另一方面，如果小于关系不能被满足，那么我们可以确定这两个事件是因果无关的。

协议的非严格定义是它是计算机用于相互通信的一组约定的规则。

让我们举一个简单的例子：

一个过程发送消息 嗨，你好吗？ 到另一个过程。 根据我们的简单协议，当进程接收到此特定消息时，需要发送响应良好，谢谢

但是，我们的协议中没有规定要发送第一个消息的过程是什么，或者在收到“ Good，thank”消息后应该发生什么。

以下两个图都是我们协议的有效运行：

否，这是不允许的，因为我们的协议指出消息“好，谢谢”应仅在收到消息“ Hi，您好”后发送。 因此，发送这种未经请求的消息会构成协议违规

怎么样-这是违反协议的行为吗？

嗯，这很难说。 也许协议运行正确，而我们只是在看某个特定的时间点，而这并不能提供完整的故事。

这里的要点是，Lamport图只能表示逻辑时间-也就是说，它描述了事件序列发生的顺序，但是它不能让我们知道事件之间电脑经过了多少时间。

但是考虑到逻辑时钟仅与事件的顺序有关，以下两个事件序列看起来是相同的也就不足为奇了：

问：是否可以使用Lamport图为我们提供给定协议中所有可能的消息交换的完整表示？ 答：不！

事实证明，存在无限多种不同的Lamport图，它们都表示协议的有效运行。

这里的要点是，Lamport图可以很好地表示协议的特定运行，但是它不能表示该协议的所有可能的运行，因为将会有无限多个。

Lamport图还可以很好地表示违反协议的情况-例如，在上图中，Alice发送了消息Good，这要感谢Bob没有先向Bob发送消息Hi，你好吗？

在讨论我们希望是真实的系统属性时，谈论此类属性正确性的一种方法是绘制一个表示其违规的图表。

例如，考虑发送和接收消息的顺序

在分布式系统中，不仅可以发送和接收消息，还可以传递消息。

嗯，听起来好像传递这个词有一些非常具体的含义……是的，确实如此。

可以很直观地理解发送和接收，但是在分布式系统的上下文中，消息传递的概念具有高度特定的含义：

正在发送(sending)

导致发送消息的显式行为。发送过程完全控制何时或是否发送该消息。因此，消息发送处于活动状态。

接收(receiving)

消息到达时发生的动作。接收过程无法控制何时或是否有消息到达-它们只是显示…或不显示。因此，从接收过程的角度来看，接收是被动的。

交货(delivery)

收到消息后对消息执行的任何处理。对于接收过程，它可以选择何时以及是否处理收到的消息。因此，邮件传递处于活动状态。 例如，即使您无法控制何时接收消息，也可以选择将这些消息放入队列中，并且仅在以后认为正确的某个时间对其进行处理。 这被称为传递接收到的消息，这不同于简单接收消息。

如果某个进程在消息M1之后发送消息M2，则接收进程必须先传递M1，然后传递M2。

我们可以使用下图来表示协议违规，例如FIFO异常。

这是一个示例，其中图提供了一种非常有用的方式来表示违反协议的某些正确性属性。