Fault-tolerant clock synchronization
Fault-tolerant clock synchronization
复制标题
容错时钟同步
DOI：
--
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
D. Dolev
中科院分区：
文献类型：
--
作者：
Joseph Y. Halpern;B. Simons;H. Strong;D. Dolev
本文给出了两个简单有效的分布式算法：一个用于保持网络中的时钟同步，另一个用于允许新的处理器加入网络，使它们的时钟同步。该算法容忍任何类型的链路和节点故障。保持同步的算法将适用于任意网络（而不仅仅是完全连接的网络），并且只要正确的处理器保持通过无故障路径连接，就可以容忍任何数量的处理器或通信链路故障。因此，它代表了对其他时钟同步算法（例如[LM1，LM2，LL1]）的改进。我们的算法允许新的处理器加入要求超过一半的处理器是正确的，这是一个要求，这是可以证明是必要的。
This paper gives two simple efficient distributed algorithms: one for keeping clocks in a network synchronized and one for allowing new processors to join the network with their clocks synchronized. The algorithms tolerate both link and node failures of any type. The algorithm for maintaining synchronization will work for arbitrary networks (rather than just completely connected networks) and tolerates any number of processor or communication link faults as long as the correct processors remain connected by fault-free paths. It thus represents an improvement over other clock synchronization algorithms such as [LM1,LM2,LL1]. Our algorithm for allowing new processors to join requires that more than half the processors be correct, a requirement which is provably necessary.