逻辑时钟：Lamport时间戳

Question

我目前正在尝试理解Lamport时间戳。考虑两个进程P1（产生事件a1，a2，...）和P2（产生事件b1，b2，...）。让C（e）表示与事件e相关联的Lamport时间戳。我按照Wikipedia关于Lamport时间戳的文章中描述的方式为每个事件创建了时间戳。

根据维基百科，对于所有事件e1和e2，以下关系成立：

如果e1在e2之前发生，则C(e1) < C(e2)。

让我们看看a1和b2。显然，a1发生在b2之前，由于C(a1) = 1且C(b2) = 3，因此该关系成立：C(a1) < C(b2)。

问题：该关系不适用于b3和a3。显然，b3发生在a3之前。但是，C(b3) = 4，C(a3) = 3。因此，C(b3) < C(a3)不适用。

我误解了什么？非常感谢您的帮助！

- typeduke

Answer 1

是的，这个定义可能有点令人困惑。到目前为止，大家所说的都是正确的，但也许缺少一个词，以更好地理解系统 -“并发”。

如果您的进程p1和p2在同一台机器上运行，那么实际上没有太多必要使用Lamport时钟（除非是一些极端情况）。相反，您可以使用操作系统提供的时钟。但是如果p1和p2位于通过缓慢且不可靠的网络分隔的计算机上怎么办？

Lamport假设您不能信任本地时钟，并且没有分布式系统的全局状态，其中记录了2台独立计算机上事件的顺序。这就是你称这些事件同时发生的时候。

当您调试分布式系统的执行并看到事件a3和b3时，自然会认为a3先于b3发生。在您的特定情况下，您现在会说：“是的，但是那是错误的”。然而，因为这些事件没有关联，因为它们彼此之间没有通信，所以顺序通常被认为是并发的，在这种情况下，哪个事件先发生哪个事件后发生对整个系统的执行都没有影响。

由于计算机和网络工作得如此之快且非常精确，有时很难理解，让我们稍微改变一下看法： p1和p2是生活在几百年前两个不同山谷中的人。他们使用信鸽进行交流，从未谈论过他们何时完成某项任务，只是谈论他们做了什么。这样，没有人知道a3是在b3之前发生还是之后发生，因此它们同时发生。也许除了上帝在p1和p2上方观察到这一点。

不幸的是，当您拥有分布式系统时，您不能成为上帝并同时监视p1和p2，原因是来自p1的消息可能比来自p2的消息需要更长时间。因此，即使您的监控系统（上帝）已经在接收有关b3的信息之前接收到有关a4的信息，这并不意味着它们以那种顺序发生，也许包含有关a4的信息的数据包只是走了更长或更慢的路径。

最后，还有另一种东西叫做向量时钟。每个进程在系统中都有一个Lamport时钟。关键在于，如果事件a的所有Lamport时钟都小于或等于事件b的Lamport时钟，则事件a仅会在事件b之前发生。如果你在你的小例子中尝试它，你会发现没有事件在另一个事件之前发生=>它们是并发的。

- peter

Answer 2

Lamport认为：我们通常不能使用物理时间来确定其中任意一对事件的顺序。在所提供的示例中，您忽略了这个假设。

P1和P2独立地增加它们的时钟。当事件发生时，发起进程将其当前值发送到目标进程，目标进程检查接收到的值是否小于其当前值。如果是，则将其当前值更改为接收到的值+1，否则丢弃接收到的值。在您的情况下，P1和P2不会发送它们的事件a3和b3。

- Andrei

---

你有没有关于“我们通常不能使用物理时间来确定其中任意一对事件的顺序”的参考资料？ - user820789

Answer 3

我发现了错误。我写道：

如果 e1 发生在 e2 之前，则 C（e1）

然而，Lamport 将“发生在之前”定义为部分排序。这是维基百科关于部分排序集的说法：

这种关系称为偏序以反映不是每一对元素都需要相关：对于某些对，可能没有一个元素在 poset 中先于另一个元素。

根据 Lamport 对“发生在之前”的定义，b3 和 a3 没有关系，因此 b3 没有“发生在”a3 之前，因此问题中陈述的等式不一定成立。

- typeduke

Answer 4

显然，b3发生在a3之前。

嗯，只有在假设A和B都同意并可以使用时间戳的通用时钟的情况下才成立。如果这样的东西存在，我们根本不需要Lamport时钟！

在制作图纸时，您使用了自己选择的物理时钟将事件放置在水平轴上。问题在于，A和B通常无法就物理时钟读数达成一致。他们的时钟可能会漂移等等，除非他们在同一个地方，否则没有办法完全对齐他们的时钟。

因此，这归结为“发生在之前”的定义。在分布式系统中，我们如何定义它而不诉诸于通用物理时钟？事实证明，我们能想到的最好的定义并不像通用物理时钟提供的那么强，其中两个事件要么同时发生，要么一个在另一个之前。

我们的新定义仅提供了部分排序。将有可以比较的事件和无法比较的事件（称为并发事件）。当两个事件是并发的时，“发生在之前？”这样的问题毫无意义！这略微类似于特殊相对论时间锥，但让我回到主题。 Lamport时钟读数承诺遵循你引用的（单向）关系中的发生在之前的定义是什么？莱斯利·兰波特在他的原始论文中提供了这样的定义。无论如何，定义如下：

1. a和b发生在同一个进程中，且a在普通意义下先于b发生（我们可以通过使用单调时钟为它们标记时间戳来轻松比较同一进程中的两个事件）。
2. a是一个进程发送消息的事件，而b是另一个进程接收此消息的事件。
3. 存在一个事件e，使得a在e之前发生，而e在b之前发生（传递性）。

这样的定义可以直观地理解为，如果a能够引起（影响）b，那么a就先于b发生。我们感兴趣的是因果关系。如果a能够引起b，则它们的Lamport不等式成立。

- Hubert Pietrzykowski