同步系统

同步性提供的是一把有已知刻度的尺子。正确消息可能先到，也可能后到；只要不超过承诺的时间界，算法就能决定何时结束等待、进入下一阶段。因此同步并不要求所有处理器在同一物理瞬间执行每条指令，也不要求消息每次都花同样长的时间。

轮次进一步把具体到达顺序隐藏起来。算法关心“第 $r$ 轮收到了谁的什么消息”，而不是它们在这一轮的第几毫秒抵达。实现可以给消息附轮次标签，为提前到达的消息设置缓冲；但标签本身不能保证消息及时到达，时间界仍来自模型或底层机制。

在可靠无故障异步网络上，网络同步器公理库异步网络同步器Network synchronizer · Alpha synchronizer · Beta synchronizer用基本消息ACK与轮安全通知模拟同步轮，比较逐邻居α和树汇聚β的通信、延迟与缓冲条件。可以用ACK和SAFE证明某个逻辑轮的收件箱已完整，再允许下一轮更新。它模拟同步算法的轮接口，额外支付控制消息与等待成本，并没有向物理网络添加可用于故障判断的已知时延界。

超时能说明什么，取决于协议还承诺了什么。假设正确进程每轮必须发送心跳、链路可靠、唯一故障为崩溃，规定时限内没有心跳才可推出发送者已崩溃或某项模型假设被破坏。若协议允许正确进程沉默，或者链路允许丢包，“没有收到”就不能单独识别进程故障。

一条消息每轮只能前进一跳 ​

考虑无故障链 $A-B-C$。初始只有 $A$ 知道消息 $m$；每个知道消息的进程在下一轮转发给邻居。

第 1 轮中，$B$ 的发送动作依据初始状态，因此不能把本轮稍后才收到的 $m$ 同轮转给 $C$。一般地，在连通无向网络中，洪泛从源点到达距离为 $d$ 的顶点恰需 $d$ 轮；向全网广播的轮数是源点到其他顶点的最大距离，不超过网络直径 $D$。

这个界也有因果含义：在给定的一跳一轮模型中，距离大于 $r$ 的初始输入还不能影响某节点第 $r$ 轮后的状态。因此直径并非只是方便的估计量，它反映了信息传播的必经距离。

因此，保持源点以外所有节点的初始状态相同，仅将源点比特分别设为零和一；对距离源点 $d$ 的节点，前 $d-1$ 轮的两次执行不可区分。要在两次执行中都输出正确比特，至少需要 $d$ 轮。若其他节点的初始信息已泄露源点比特，这对局部视图相同的执行就不一定存在，不能沿用这个下界。

收到答案，不等于知道全网都收到 ​

一个节点收到消息 $m$ 后可以立即输出自己的答案，但它未必知道远端节点是否已经收到。如果所有节点预先知道总节点数上界 $N$，连通简单图中 $N-1$ 轮足以传播到所有节点；若没有任何合适的规模或距离上界，则还需要确认、汇聚或另一个终止检测机制。局部结果和全局完成是不同的知识状态。

崩溃发生在轮内时 ​

允许进程在发送过程中崩溃的模型，可能规定它只向一部分邻居发出本轮消息；另一些模型则把整轮发送视为原子动作。两种规格允许的执行不同，不能只写“同步且可崩溃”便认为算法证明已经完整。可靠信道保证已发送消息的交付，也不必保证崩溃进程把原计划的所有消息都发出。

同步不能凭空打破对称 ​

在一个至少有三个进程的匿名环上，假设所有进程运行同一确定性程序、初始状态相同，而且各自的端口角色也完全对称。第 1 轮中它们发出相同消息、收到相同形状的消息，转移到相同状态；归纳下去，每一轮仍然如此。

于是确定性程序无法只让其中一个进程宣布当选：要么所有进程同时宣布，要么都不宣布。这个选主公理库选主问题Leader election使所有正确进程最终一致输出同一唯一进程为领导者的分布式任务。障碍在完全同步、没有故障时仍存在。唯一标识、随机性或额外的不对称输入改变的是这个对称性条件，而不是同步性的定义。[1,2]

已知界、未知界与最终生效的界 ​

完全同步模型从规定的执行起点就提供算法可用的界。部分同步公理库部分同步模型Partial synchrony · Partially synchronous system时间界存在但其数值或开始生效时刻不为算法预先掌握的分布式系统模型。则要进一步说明是哪种放宽：例如界存在但算法不知道其数值，或者已知界只在某个未知的稳定时刻之后成立。算法面对的关键困难，是当前尚无法确认“这次等待是否已经足够长”。最近测到的最大延迟，也不能直接当作以后永远有效的已知上界。

Byzantine 进程还可以按时发送相互矛盾的消息；同步界约束时间，不约束消息内容。故障数、身份认证、信道可靠性和进程是否会永久停止，都必须作为独立条件写明。

同步模型使可靠广播公理库可靠广播Reliable broadcast保证有效性、一致性和完整性的广播抽象。、选主和一致性协议能够逐轮分析。证明通常先建立“第 $r$ 轮之后哪些信息已传播、哪些状态仍满足不变量”，再推出指定轮数内完成。使用超时的地方则要指出究竟依赖哪条已知界，不能把超时当成脱离模型的故障预言机。

轮数、消息条数和总比特数是不同成本。同样用 $D$ 轮完成洪泛的协议，可能反复发送已经见过的消息，也可能记录消息标识以抑制重复；二者时间上界相同，通信开销却不同。若每个节点只在首次得知时沿每条关联边转发一次，有向发送总数至多为 $2|E|$；允许无限重发便不能沿用这个界。模型规定每条消息是否有长度限制，也会改变一轮能交换多少信息。

分布式图算法常进一步区分 LOCAL 与 CONGEST：前者允许每边每轮任意有限长消息，后者限制每边每个方向每轮为 $O(\log n)$ 位；两者都把有限本地计算与通信轮数分开计量。Cole–Vishkin 颜色缩减公理库Cole–Vishkin 颜色缩减Cole–Vishkin color reduction · 确定性环三染色在给定一致方向的同步环上，用首次差异位反复压缩合法颜色，再以三轮消色得到三染色。给出一个完整例子：在给定一致方向和共同颜色上界 $K$ 的环上，每轮读邻点旧色、同时更新，最终得到三染色。其 $O({\log }^{\ast }K)$ 轮界并不同时意味着常数消息长度或常数本地计算；初始 $K=n^{O(1)}$ 时才直接满足这里的 CONGEST 消息界。

同步分布式图模型与 BFS 波前公理库同步分布式图模型与 BFS 波前Distributed graph models · LOCAL · CONGEST · 分布式 BFS从节点局部输入出发构造指定根的 BFS 树，证明逐轮距离、通信开销与全局最小标识的局部性下界。把这一轮模型落实为每个节点只保存距离与父端口的程序：逐轮不变量证明首次收到即最短，并区分离心率轮后的输出稳定与共同规模界规定的停止时刻。其全局最小标识例子还说明，即使 LOCAL 消息长度不限，远端输入仍必须逐跳传播。

从理论落到实现，核心工作是把“一轮”对应到可兑现的等待与处理规则，并明确故障假设。加入同步性可以排除某些异步执行中的无限拖延，但具体协议的活性仍需单独证明，不能由“系统同步”四个字直接推出。