admin管理员组文章数量:1534403
2024年7月24日发(作者：)
1. 定义：同步时钟是分布式系统中一些应用程序的一个请求。当应用程序有时候需要同步
时钟时，可以使用全序。即使并不要求容错，经常需要同步时钟。正如我们即将看到的，
甚至实现一些“building blocks”的方法，假设不同节点的时钟是同步的。因此，不同节点
的时钟彼此同步是可取的。
2. 内部时钟和外部时钟：外部的时钟同步要求在来自外部时间参考的给定最大偏差之内维
护处理器时钟，这要求保持实时。内部的时钟同步要求不同处理器的时钟保持在彼此的
最大相对偏差内。外部的同步时钟也是内部的同步，然而反过来说不一定正确。而内部
的同步可能需要系统内部分布式行为的持续时间，外部的时钟同步可能需要在实时系统
中，事件发生的实际时间可能被指定。
3. 时钟同步有各个方面的问题。不仅仅是不同节点的时钟有不同的时间，也可能是有不同
的运行速度。一个时钟同步的尝试会要求不同处理器获得其他时钟的值。网络延迟（发
送-接收）是随机变化的。
4. Dual-faced：错误的时钟可能在不同的处理器得到不同的时钟值。
（3.2.1）
：我们假设在每个节点上有一个硬件时钟，由该节点上的处理器控制。一个失败模
型，可以捕获失败进程和失败物理时钟。进程编号为1,2,…,i,…,假设通过通信网络连接。
定义：Ci (t)表示在物理时间t读取时钟Ci （当试图读取这个时钟时，返回进程控制的时
钟值）。ci (t)第i个时钟到达值T的实际时间。不同进程的时钟值要彼此接近，并且接近真
正时间（外部时间），对于一个正确的时钟Ci 可以指定为：
|d(Ci/dt)-1|<ρ
对于一个典型的晶体控制的时钟，ρ是10
-5
。
5. 我们现在指定时钟同步的要求。这里有两个基本的要求。
S1. 在任意时间所有正确的处理器的时钟值必须趋近相等。也就是说对于一些常数β：
| Ci (t)- Cj(t)| ≤β
S2. 所有正确的处理器时钟在同步过程中改变的总数在小范围∑。
6. （3.2.2）确定的时钟同步协议：假设消息延迟的最大限度，检测信息丢失。
7. 详细内容：读取所有时钟取平均值（少数进程失效），对于dual-faced时钟（类似拜占庭，
时钟同步问题的方法存在只有错误时钟的数目在系统中少于n/3，该系统有n个时钟。），
为了使这种方法有效，我们要求：
1. 任意两个正确的进程获得大约相同的时钟值Ci 。
2. 如果Ci是正确的，那么所有正确的进程获得近似正确的Ci值。
公式1：如果max是信息交付的最大时间延迟，min是最小时间延迟，有n个进程，对
一个确定的时钟同步协议，可以达到同步的亲密是粗略的（max-min）（1-1/n）
Lundelius-Welch 和Lynch提出的方法[LL88]。这个方法可以处理各种各样的失败，假设
错误进程的数目少于n/3，，在n个进程的系统中。他要求只有n
2
信息在一轮同步中（与
在[LM85]使用的指数数目的消息相比），时钟在每一轮中调整的大小与错误进程的数目
无关。
公式2：逻辑时钟的值或者进程读取的始终返回值，通过申请修改硬件时钟提供的值获
得。即：
C(t)=H(t)+CORR(t)，
H(t)是时间通过硬件时钟在时间t显示，CORR(t)是一个调整函数，它的值随时间变化。
在每个再同步中，CORR(t)的值改变。逻辑时钟值通过该函数的值改变。
失效进程f，总进程3f+1个。
步骤：1.初始化：T0时刻，两个进程相差时间不超过β
2.每两个进程间可以通信。消息延迟是t`-t,传递时间区间[
-
，
],二者皆为
定值。
过程：Start为T0时刻，当进程到达Ti时刻触发一轮同步，广播这个消息并收集同一轮
其它进程的广播消息，等待时间外不接收消息。（与下一轮时间间隔
T）。
实例：进程j到达ti时刻，发送广播。进程k到ti时刻，广播。这时j在
时候内收到k的广播消息。公式3.
若有拜占庭故障，需如下计算：
去掉前f个，去掉后f个，剩下的取平均值。
【略
T的选值】
算法思想：进程i一直接收其他进程发来的消息，存到缓冲区中。当进程i到达Ti时刻
时发起同步，广播自己的时间T，同时接收其他进程发来的消息（在一定时间内进行等
待）。收到所有的消息后，进程i将收到的时间 去掉前f个，去掉后f个，剩下的取平
均值。作为调整时间，对自己的时刻进行修正。
T时间后再次发起同步。
8. （3.2.3）
9. 不精确的 不在乎时间延迟，无dual-faced问题，不考虑max延迟，但是有个最小延迟
min（已知）。J给i发消息，i收到后，将自己的时间T反馈给j。j收到这个反馈的真正
时间是t，2D是消息走一圈的延时。2d是真正一圈的延时。
10. 公式4;j收到i的反馈 信息的时间范围。延迟时间超过2u的不考虑。
最后：假设已经通过某种方法达到外部同步了，成为主时钟，其他是从时钟，从时钟读
取主时钟的人。精确时钟协议用于重置本地时钟，任意协议可以用来读取远程时钟。
版权声明：本文标题：3.2时钟同步 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1721803267a898198.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论