Tight bounds for clock synchronization
Tight bounds for clock synchronization
复制标题
DOI：
10.1145/1667053.1667057
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
C. Lenzen;Thomas Locher;Roger Wattenhofer
中科院分区：
文献类型：
--
作者：
C. Lenzen;Thomas Locher;Roger Wattenhofer
我们提出了一种新的时钟同步算法，并证明了严格的上限和下限的最坏情况下的时钟偏差，可能会发生在任何两个参与者在任何给定的分布式系统。更重要的是，相邻节点之间的最坏情况下的时钟偏差（渐近）最多比最佳可能界限大两倍。虽然以前的结果只集中在网络直径上的偏斜界限的依赖性，我们证明了我们的技术是最佳的最大时钟漂移，消息延迟的不确定性，和施加的时钟速率的界限。所给出的结果都在一个一般模型中，其中时钟漂移和消息延迟可以在预先指定的范围内任意变化。此外，我们的算法表现出一些其他非常理想的属性。首先，该算法确保时钟值保持在真实的时间的仿射线性包络中。在没有外部计时器的情况下，无法获得关于真实的时间的准确度的更好的最差情况界限。其次，该算法最小化了在给定时间段内需要交换的消息的数量和大小。此外，对于每个邻居，仅必须在本地存储少量比特。最后，我们的算法可以很容易地适应各种其他突出的同步模型。
We present a novel clock synchronization algorithm and prove tight upper and lower bounds on the worst-case clock skew that may occur between any two participants in any given distributed system. More importantly, the worst-case clock skew between neighboring nodes is (asymptotically) at most a factor of two larger than the best possible bound. While previous results solely focused on the dependency of the skew bounds on the network diameter, we prove that our techniques are optimal also with respect to the maximum clock drift, the uncertainty in message delays, and the imposed bounds on the clock rates. The presented results all hold in a general model where both the clock drifts and the message delays may vary arbitrarily within pre-specified bounds. Furthermore, our algorithm exhibits a number of other highly desirable properties. First, the algorithm ensures that the clock values remain in an affine linear envelope of real time. A better worst-case bound on the accuracy with respect to real time cannot be achieved in the absence of an external timer. Second, the algorithm minimizes the number and size of messages that need to be exchanged in a given time period. Moreover, only a small number of bits must be stored locally for each neighbor. Finally, our algorithm can easily be adapted for a variety of other prominent synchronization models.