On the possibility and impossibility of achieving clock synchronization
On the possibility and impossibility of achieving clock synchronization
复制标题
DOI：
10.1145/800057.808720
复制
发表时间：
1984-12
期刊：
影响因子：
--
通讯作者：
D. Dolev;Joseph Y. Halpern;H. Strong
中科院分区：
文献类型：
--
作者：
D. Dolev;Joseph Y. Halpern;H. Strong
众所周知，只要使用某种认证技术，在出现故障时钟数量超过参与时钟总数三分之一的情况下，就可以实现时钟同步。如果没有身份验证，可以容忍的故障数量一直是一个悬而未决的问题。在这里，我们表明，如果我们限制逻辑时钟在实时的某个线性函数内运行，那么当三分之一或更多的处理器出现故障时，如果没有身份验证，时钟同步是不可能的。然而，如果处理器生成消息的速率存在限制，那么我们表明，只要故障不会断开网络，无需身份验证即可实现时钟同步。最后，我们提供了网络中可以实现的同时性的接近度下限，作为网络传输和处理延迟属性的函数。
It is known that clock synchronization can be achieved in the presence of faulty clocks numbering more than one-third of the total number of participating clocks provided that some authentication technique is used. Without authentication the number of faults that can be tolerated has been an open question. Here we show that if we restrict logical clocks to running within some linear function of real time, then clock synchronization is impossible, without authentication, when one-third or more of the processors are faulty. However, if there is a bound on the rate at which a processor can generate messages, then we show that clock synchronization is achievable, without authentication, as long as the faults do not disconnect the network. Finally, we provide a lower bound on the closeness to which simultaneity can be achieved in the network as a function of the transmission and processing delay properties of the network.