带有可变消息传输时间的Lamport时间戳

Question

我想我和Lamport时间戳有点误会了。它似乎期望消息在分布式端点之间传输的时间相同。

假设process p1依次向处理p2发送消息m1和m2。在本文算法部分的伪码之后，我们有：

# we start at 0
time(p1) = 0

# we send m1
time(p1) = time(p1) + 1 = 1
send(m1, 1)

# we send m2
time(p1) = time(p1) + 1 = 2
send(m2, 2)

如果m1在m2之前到达p2，那么一切都很好。但是如果m2是第一位的，我们就可以得到：

# we start at 0
time(p2) = 0

# we receive m2 first
time(p2) = max(2, time(p2)) + 1 = max(2, 0) + 1 = 3

# we receive m1 second
time(p2) = max(1, time(p2)) + 1 = max(1, 3) + 1 = 4

因此，在p2的本地时间(time(p2))中，m2的时间为3，m1的时间为4，这与最初发送消息的顺序相反。

我是错过了一些基本的东西，还是Lamport时间戳需要一致的旅行时间才能工作？

Answer 1

消息的时间是消息中包含的时间，而不是进程接收消息的时间。

定时器在两个进程之间逻辑上是共享的，因此它需要两个进程计数事件(发送)，这就是为什么接收方在接收到消息时增加一个事件的原因。

该算法试图保持两个进程的定时器保持同步，即使消息丢失或延迟，这也是为什么接收方对时间的看法和发送方对消息中所找到的时间的看法的最大值。如果这些信息不相同，则某些消息丢失或延迟。这将导致两个进程对时间有不同的看法，但在发送和接收下一条消息时(在任何方向)，时钟将被重新同步。

如果这两个进程同时发送一条消息，那么这两个消息将包含相同的时间，这就是为什么这不是一个总的顺序。但时钟最终仍将被重新同步。