0

大家好,我想问一下分布式系统中的逻辑时钟。Lamport 算法定义当事件 a 在进程 Pi 中发送消息,并且在进程 Pj 中事件 b 接收到该消息,则可以定义事件 a 在 b 之前发生。假设进程 Pj 在事件 b 收到消息之前,事件 c 发生在 Pj 上(因此 c 在 b 之前发生)并发送消息进程 Pi,然后进程 Pi 在事件 a 之后在事件 d 收到消息,那么我们就有事件 c , 以及 a, 发生在 d 之前。

我的问题是,如何定义事件 a(第一个事件发生在 Process Pi 上)和事件 c(第一个事件发生在 Process Pj 上)之间的关系?如何让进程 Pi 和 Pj 都同意事件 a 和 c 的顺序?

Lamport 算法:http ://en.wikipedia.org/wiki/Lamport_timestamps

4

2 回答 2

3

答案很简单。基于 Lamport 算法,您无法定义事件 a 和 c 之间的任何关系。我们知道的所有事情是:

a -> b 和 c -> d 和 a -> d 和 c -> b

但是您不能得出结论 a -> c 或 c -> a 仅此而已。

于 2011-11-08T13:49:24.757 回答
0

重要的是这些过程在事件发生的顺序上是一致的。为了同步逻辑时钟,Lamport 定义了一种称为先前发生的关系。表达式 a -> b 读作“a 出现在 b 之前”。这种发生关系可以在两种情况下看到:

  1. 如果 'a' 和 'b' 是同一进程的事件,并且 'a' 发生在 'b' 之前,则 a -> b 为真。

  2. 如果'a'是一个进程发送消息的事件,'b'是另一个进程接收到消息的事件,那么a->b也是如此。

算法是如何工作的?

每条消息都有发送者的发送时间。所以接收器修改时间,以防它的时间小于发送器的时间。所以算法同步接收器的时钟。发送到另一个进程的每条消息都将包含发送消息的时间单位,因此会检查时钟。

于 2021-07-10T06:03:23.887 回答