messaging - 逻辑时钟 : Lamport Timestamps

Question

我目前正在尝试了解 Lamport 时间戳。考虑两个进程 P1 (产生事件 a1 、 a2 、...)和 P2 (产生事件 b1 , b2 ,...)。让 C(e) 表示与事件相关的 Lamport 时间戳 e .我为每个事件创建了时间戳，如 Wikipedia article about Lamport timestamps 中所述。 :



根据维基百科，以下关系适用于所有事件 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 是 100 年前生活在两个不同山谷中的两个人。他们使用 pidgins 一起交流，从不谈论他们何时完成某项任务，只谈论他们做了什么。这样，没有人知道，如果 a3 之前发生过 b3 或者反过来，因此它们同时发生。也许不是没有人，上帝从上看 p1 和 p2 可以看到。

不幸的是，当你有一个分布式系统时，你不能成为上帝看着 p1 和 p2 同时，只是出于来自 的消息的原因p1 可能需要比 更长的时间p2 .所以即使你的监控系统(大神)收到了的信息b3 在收到关于的信息之前a4 这并不意味着它们是按这个顺序发生的，也许包中包含有关 的信息。 a4 只是走了更长或更慢的路径。

最后还有一个东西叫vector clocks .每个进程对于系统中的每个进程都有一个 lamport 时钟。这里的关键是，事件 只会发生在事件 之前b 如果 的所有 lamport 时钟小于或等于 b .如果你在你的小例子上试一试，你会发现在另一个 之前没有发生任何事件。 => 它们是并发的 .