异步网络同步器

不能用“等得够久”证明异步消息不会再来，但可以让每个发送者证明：“我这一轮发出的东西都已送到。”收件节点从全部邻居拿到这份证明，便知道自己的本轮收件箱不会再增加。

ACK确认某条消息已经交付；SAFE确认某个发送者本轮全部发送完成；GO确认全网都满足这一条件。三者回答不同层次的问题。只给消息贴轮标签，而没有补齐缺失消息的判断机制，无法安全推进轮次。

慢消息到来以前，哪些节点能继续 ​

取四节点A–B–C–D的路径，另加边A–C，共4条边。第r轮中，A只发a给B，C只发c给B，其他节点不发基本消息；c被网络延迟。

A的a到B后，B立即缓存并回ACK。A收ACK后向B、C发SAFE(r)。B、D没有本轮发送，可分别向自己的邻居发SAFE(r)。C尚未收到c的ACK，不能发SAFE(r)。

B已收到a，也收到A的SAFE，但它还缺C的SAFE，因此不能把收件箱仅含a视为完整。等c终于到B，B把c放入第r轮收件箱并立即ACK；C收ACK后发SAFE，B才可用{a,c}计算下一状态。

同一轮的A也要等待邻居C的SAFE；D同样等待C。若网络别处节点已经进入r+1并发来未来轮消息，接收者先按标签缓存，不能把它误加到第r轮，也不能拒绝ACK直到自己的r+1开始，否则可能人为制造等待环。

为什么α的局部证明足够 ​

v进入r+1之前，已经收到每个邻居u的SAFE(r)。u发SAFE(r)之前，已固定本轮发送集合且收齐全部ACK，所以u发给v的每条第r轮消息都已经到达v。来自所有可能发送者的条件同时成立，v的第r轮收件箱完整。

随后按同步算法的转移函数更新，便得到与某次合法同步执行相同的第r轮后状态。对r归纳，可模拟整段同步执行。节点进入同一轮的物理时刻可以不同；模拟证明无需把这些时刻强行对齐。

可靠交付与有限本地计算也保证每轮的ACK、SAFE最终齐备，所以不会停在某个逻辑轮。若节点崩溃，这一等待可能永久持续；用超时跳过它会改变同步算法的故障语义，需要另行证明。

β怎样换取更少控制消息 ​

在同一网络中取根A、树边AB、BC、CD，树高h=3。D自身安全后UP给C；C须先等基本消息c的ACK，再结合D的UP发给B；B结合自己的安全向A汇聚。A收齐后，GO沿A→B→C→D广播。

这是在既有树上运行的确认与汇聚；建树时可使用回声波公理库回声波算法Echo algorithm · Echo wave · Flooding with echo以首次接触选父边、非树边双向回声结清一轮洪泛，使根无需已知直径也能确认全网覆盖。，但初始化成本须另计。树高影响每轮屏障延迟，不能只因总共n个节点就假定树是平衡的。

设基本同步算法运行T轮，总基本消息数M，每个基本消息加一个ACK。α每轮再发2m条SAFE，故总消息为 $O(M+Tm)$，加上初始化。β每轮汇聚与广播各用n−1条树消息，总消息为 $O(M+Tn)$，同样另计建立根树。

纯异步模型仍没有已知墙钟上界。若为性能比较将每次消息传输与本地处理归一为至多一个时间单位，α每模拟一轮只多常数级相邻握手，β多O(h)树延迟。这个分析用的单位上界不是算法检测超时的依据，不把物理网络变成已知界同步系统。

状态成本包括轮计数、各邻居SAFE标记、未清ACK身份和按轮收件箱；不能只计算一个round整数。基本消息长度还会增加轮号与身份字段，是否满足某个CONGEST位数限制，应结合模拟轮数与原消息格式判断。

同步器模拟的是无故障轮算法的消息接口，不制造故障检测器，也不打破匿名对称性。它让设计者先用轮不变量组织算法，再明确支付异步实现的确认和等待成本。