逻辑时钟:Lamport时间戳

Question

我目前正在尝试了解Lamport时间戳.考虑两个过程P1(产生事件a1,a2,...)和P2(产生事件b1,b2,......).设C(e)表示与事件e相关的Lamport时间戳.我为维基百科关于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),并不能适用.

我误解了什么？非常感谢帮助!

Answer 1

是的，该定义可能会有些混乱。到目前为止，其他所有人所说的都是正确的，但是为了更好地理解系统，可能遗漏了一个词。- 并发

如果您的进程p1和p2在同一台机器上运行，那么实际上不需要太多使用Lamport时钟（也许是某些非常特殊的情况）。相反，您只能使用操作系统提供的时钟。但是，如果p1和p2处于由缓慢且不可靠的网络分隔的计算机上怎么办？

Lamport假定您不信任本地时钟，并且您没有分布式系统的任何全局状态，在这种状态下，分别在2台计算机上发生了事件。那是您调用那些同时发生的事件的时候。

当您调试分布式系统的执行时，您自然会假设会看到事件a3和b3，而a3发生在b3之前。在您的特定情况下，您现在可以声明，是的，但这是错误的。但是，由于事件不相关，因为它们彼此之间没有通信，所以通常假定顺序是并发的，在这种情况下，对于整个执行过程，哪个事件是第一发生还是第二发生都没有关系。系统。

由于计算机和网络运行得如此快速且仍然非常精确，因此有时很难理解，让我们以略有不同的方式来看待同一件事：

p1和p2是几百年前生活在两个不同山谷中的两个人。他们使用pidgins进行交流，从不谈论何时完成某项任务，只是谈论他们做了什么。这样，没人知道a3是在b3之前发生还是在b3之前发生，因此它们是同时发生的。也许不是没有人，从p1和p2上观看的上帝可以看到它。

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

最后，还有另一种叫做矢量时钟的东西。每个进程都有系统中每个进程的Lamport时钟。这里的关键是，事件一个只会事件发生之前b如果所有兰波特时钟一个是小于或等于那些b。如果您在这个小示例上进行尝试，您会发现在其他=>它们并发之前没有发生任何事件。

Answer 2

兰波特假设：我们一般不能使用物理时间来找出其中发生的任意一对事件的顺序。在建议的示例中，您忽略了这个假设。

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

Answer 3

我发现了我的错误。我写：

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

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

这种关系称为偏序，以反映并非每对元素都需要相关的事实：对于某些对，可能在偏序集中没有一个元素先于另一个元素。

根据兰波特对“发生在之前”的定义，b3和a3不相关，因此b3没有“发生在” a3之前，因此问题中所述的方程不一定成立。