时间与全局状态
时间与全局状态涉及分布式系统如何在没有共享时钟和瞬时全局视图的情况下对事件进行排序并推断其集体状况。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
在分布式系统中，事件发生在没有共享时钟的独立进程中；时间与全局状态的研究提供了关系和算法——逻辑时钟和向量时钟、快照和有序交付——使系统能够因果地排序事件并捕获一致的全局状态。
Scope
该领域涵盖逻辑时钟和“先发生”关系、物理时钟同步、向量时钟以及因果关系和并发性的检测、一致性全局快照的确定，以及可靠多播所需的排序保证（FIFO、因果、全序）。这些工具共同使分布式系统能够在没有全局时钟的情况下，对“何时”和“何种状态”做出有意义的陈述。
Sub-topics
Core questions
- 在没有共享物理时钟的情况下，如何对不同进程的事件进行排序？
- 一个进程如何确定两个事件是因果相关的还是并发的？
- 在计算持续进行的同时，如何记录一致的全局快照？
- 为了保持因果关系，消息传递需要哪些排序保证？
Key theories
- 先发生关系和逻辑时钟
- Lamport的“先发生”关系定义了事件上的偏序因果关系，逻辑（标量）时钟为其分配一致的时间戳，提供了一种与时钟无关的顺序概念，足以为许多协议构建全序。
- 向量时钟和因果关系
- 向量时钟扩展了逻辑时钟，通过比较两个时间戳，可以精确地捕获一个事件是否因果地先于另一个事件，或者两者是否并发，从而实现精确的因果关系跟踪。
- 一致性全局快照
- Chandy-Lamport快照算法通过沿通道传播标记，在不暂停系统的情况下记录一致的全局状态——包括进程状态和传输中的消息。
Clinical relevance
逻辑时钟和向量时钟是因果一致性、复制存储中的冲突检测以及分布式执行调试的基础；一致性快照是分布式检查点、死锁和终止检测以及流处理故障恢复的基础。
History
Lamport于1978年发表的论文引入了逻辑时间和“先发生”关系，这是计算机科学中最常被引用的成果之一；Chandy和Lamport于1985年将一致性全局快照形式化；Fidge和Mattern在1980年代后期独立开发了向量时钟，完善了推理时间与状态的基础工具包。
Key figures
- Leslie Lamport
- K. Mani Chandy
- Colin Fidge
- Friedemann Mattern
Related topics
Seminal works
- lamport1978
- chandy1985
- fidge1988
Frequently asked questions
- 为什么分布式系统不能只使用同步的物理时钟？
- 物理时钟会漂移，并且无法在具有可变延迟的网络中完美同步，因此两个事件的实时顺序可能不明确。逻辑时钟和向量时钟则捕获了对正确性真正重要的因果顺序。
- 什么使全局快照“一致”？
- 如果快照包含消息的接收，那么它也必须包含该消息的发送，这样的快照才是一致的。这种状态可能在执行过程中发生过，尽管从未在全局范围内观察到任何单一瞬间。