因果逻辑时钟

概述

因果逻辑时钟（Lamport时钟）是Leslie Lamport于1978年提出的一种分布式系统中的逻辑时间概念，用于定义分布式系统中事件的偏序关系，建立逻辑时间的概念。

关键内容

1. 核心思想：
2. 在分布式系统中，物理时钟难以保持完全同步，因此引入逻辑时钟来捕获事件间的因果关系

3. 使用整数计数器来表示逻辑时间，通过简单的递增规则来维护时间顺序

4. 基本规则：

5. 每个进程维护自己的逻辑时钟，初始值为0
6. 进程内部的事件发生时，时钟递增
7. 发送消息时，将当前时钟值附加到消息中

8. 接收消息时，将本地时钟更新为max(本地时钟, 消息时钟) + 1

9. 偏序关系：

10. 如果事件a发生在事件b之前(happens-before)，则a的逻辑时间小于b的逻辑时间

11. 该方法能够捕获事件间的因果关系，但不能判断事件是否并发

12. 应用场景：

13. 分布式系统中的事件排序
14. 确定事件间的因果关系
15. 用于分布式调试和日志分析

16. 作为其他一致性算法的基础

17. 意义：

18. 为分布式系统中的时间概念提供了理论基础
19. 与Paxos算法、拜占庭将军问题共同构成了Lamport在分布式系统领域的三大贡献
20. 深刻影响了后续分布式系统的设计理念

来源

• 18-lamport-paxos — 提及Lamport时钟作为Lamport三大贡献之一
• Leslie Lamport — 发明者及其贡献

相关

• Leslie Lamport — invented
• 分布式系统 — applied_in
• 事件排序 — relates_to
• 因果关系 — captures