阅读笔记（十四）时钟同步问题综述《An Overview of Clock Synchronization 》

你的名字 2023-07-02 05:23 2阅读 0赞

### 一. 简介 ###

《An Overview of Clock Synchronization 》一文是优秀的时钟同步方面的综述类文章，此文详细介绍了各种不同的时钟同步方案，并给出了大量参考文献供以后续深入学习，可以说是时钟同步方向较好的入门级文献资料。  
  本文根据同步/异步，是否可靠将模型分为四类，并分别介绍。其中异步模型指进程间传递消息并无时间规定，也不需要阻塞等待。而同步模型这里指的的分区同步：每个进程采用真实时间时钟，并近似相等，或采用同样的时钟频率并且时钟漂移极小。同步模型通常会阻塞等待消息回复，因此有严格的时间规定。

### 二. 异步可靠模型 ###

对于异步可靠模型，最经典的算法莫过于Lamport Clock。Lamport Clock采用逻辑时间完成了异步分布式模型中的时钟同步问题，详细可以参考之前写的文章。Lamport Clock常用于配置时间戳的版本管理系统，并可用于解决互斥包含问题。

### 三. 异步不可靠模型 ###

对于不可靠模型来说，想实现时钟同步算法要更为复杂。根据FLP不可能性，我们可以知道不存在一个使得所有节点均达成共识的解，因此这里需要对Lamport Clock进行一些修改，使其可以容忍一定的失败（f个节点的失败）。常见的技术是等待至f + 1个进程超时，则设置他们的时钟为i + 1。这种做法用于概率一致性算法，如Ben-Or，DLS。这些算法往往给出了一个较为满意的解，但是通常较为复杂，不易于实现。

### 四. 分区同步可靠模型 ###

对于分区同步可靠模型，最重要的是如何知道各部分同步时延的上下限，依次来判断当前是否存在问题。根据Lundelius 和 Lynch的研究结果，对于一个全连接的n个节点的网络，延迟的下限是 u(1 - l/n),其中u是一个根据消息时延变化的量。该部分结果被talpern, Megiddo 和 Munshi进一步研究并用于骨干网络。

### 五. 分区同步不可靠模型 ###

该部分存在较多不同的算法，各个算法的模型均有着不同的设定，因此较难进行比较和筛选。主要包括：【3】-【8】。在该文中，给出了这些算法的比较，但是有众多数学公式，在此难以表述清楚，建议查看论文原文。

### 参考文献 ###

【1】M. Ben-Or, “Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols,” Proe. 2 “a Ann. A CM Syrup. on Principles of Distributed Computing, pp. 27-30, 1983  
【2】C. Dwork, N. Lynch, and L. Stockmeyer, “Consensus in the Presence of Partil Synchrony,” J. ACM, vol. 35, no. 2, pp. 288-323, 1988.  
【3】L. Lamport and P. Melliar-Smith, “Synchronizing Clocks in the Presence of Faults,” J. ACM, vol. 32, no. 1, pp. 52-78, Jan. 1985  
【4】K. Marzullo, Loosely-Coupled Distributed Services: A Distributed Time Service, Ph.D. Thesis, Stanford Univ., 1983.  
【5】J. Lundelius Welch and N. Lynch, ~A New Fault-Tolerant Algorithm for Clock Synchronization,” In\]ormation and Computation, vol. 77, no. 1, pp. 1-36~ April 1988.  
【6】J. Halpern, B. Simons, R. Strong, and D. Dolev, “Fault-Tolerant Clock Synchronization,” Proe. 3"a Ann. A CM Syrup. on Principles of Distributed Computing, pp. 89-102, Aug. 1984:  
【7】S. Mahaney and F. Schneider, “Inexact Agreement: Accuracy, Precision and Graceful Degradation,” Proc. 4th Ann. ACM Syrup. on Principles of Distributed Computing, pp. 237-249, Aug. 1985.  
【8】T.K. Srikanth and S. Toueg, “Optimal Clock Synchronization,” J. ACM, vol. 34, no. 3, pp. 626-645, July 1987.