Lamport Clock算法

算法"/>

Lamport Clock算法

        Lamport Clock 是一种表达逻辑时间的逻辑时钟（logical clock），能够计算得到历史事件的时间偏序关系。

        假设 P0进程是分布式集群中心节点中的监控者，用于统一管理分布式系统中事件的顺序。其他进程在发送消息之前和接受事件消息之后都需要告知 P0 进程，告知的过程是异步的。

        如图上图，P1 需要发生消息给 P2。P1在发送消息之前先告知 PO，之后再发送消息给 P2，P2在收到消息后立即告知 PO。将过程中的消息交互分别标识为“事件 A”、“事件 B”和“事件 C”，则对于不同进程的事件序列如下所示。

                对于 P0 进程，A->C；

                对于 P1 进程，A->B;

                对于 P2 进程，B->C;

        由偏序关系具有传导性，所以整个事件的顺序应该就是 A -> B -> C。

        但在实际过程中，往往伴随着网络等延迟，这时候事件消息的发送与接收并不能保证顺序性。如下图所示，可能就会出现 PO 进程接收到事件 C 消息早于事件 A，

        此时对于 P0 进程来说就是 C->A；

                对于 P1 进程，A->B;

                对于 P2 进程，B->C;

        由 P1 和 P2 得出 A->C，但对于 P0 来说 C->A,互相矛盾了。

        Lamport Clock存在二个假设和五条规则.

        结合这三个假设和五条规则，则可以解决上面因网络延迟造成消息乱序的场景