同步分布式图模型与 BFS 波前

集中式 BFS 用一个 FIFO 队列安排展开顺序；这里各节点没有共享队列，轮次本身把波前同步起来。根在第 1 轮发送，距离为 1 的节点在轮末第一次得知根，并在第 2 轮发送。于是每个新波前刚好比上一个远一条边。“首次收到”能够锁定最短距离，依赖的正是这套旧状态收发规则。

逐轮不变量如何给出正确距离 ​

记完成第 $r$ 轮后已发现的集合为 $S_r$。对 $0\le r\le n-1$，证明

还要同时保持：第 0 轮末只有根的 $\mathit{new}$ 为真；第 $r\ge 1$ 轮末，$\mathit{new}$ 恰在距离为 $r$ 的节点上为真。这个辅助条件明确了下一轮究竟由谁发送。

初始时只有根被发现，命题成立。设第 $r-1$ 轮末命题成立。第 $r$ 轮的发送者恰是距离为 $r-1$ 的节点，其消息都携带 $r-1$。若尚未发现的 $v$ 收到其中一条，就得到一条长度为 $r$ 的根到 $v$ 的路径，所以 $\delta (s,v)\le r$；而 $v\notin S_{r-1}$ 又推出 $\delta (s,v)>r-1$，故其距离恰为 $r$。

反过来，任何距离为 $r$ 的节点 $v$，在一条最短路上都有距离为 $r-1$ 的前驱。该前驱本轮必发送，因而 $v$ 本轮一定被发现。两边合起来，新发现集合恰是第 $r$ 层；所有候选都携带 $r-1$，更新得到正确距离 $r$，并为下一轮设置正确的 $\mathit{new}$ 集合。这完成归纳。

父端口为什么组成一棵树 ​

每个非根节点恰在首次发现时选一个父节点，且

这里为简洁把 $p(v)$ 也用来指该端口另一端的节点。沿父指针行走，非负整数距离每次严格减少 1，因此不可能形成环，且恰走 $d(v)$ 步到达唯一距离为 0 的根。图连通，所以全部节点最终被发现；每个非根贡献一条父边，合成一棵覆盖全图的树。树上根路径的长度就是图距离，故它是 BFS 树。

标识规则只决定同层候选中的哪一个作为父节点。它使相同输入得到确定的父指针，但没有承诺整条根路径的标识序列在所有最短路中按字典序最小；那是另一种需要额外比较信息的输出要求。

菱形接尾链的完整执行 ​

取边集 $\{sa,sb,ac,bc,cd\}$，令

这里 $n=5,m=5$。下表每格记录轮末的“距离、父节点”，用 $\mathrm{\infty }$ 表示未发现，父节点名只是阅读便利，实际程序保存端口。

第 2 轮，$c$ 同时收到 $a$ 的 $(1,4)$ 与 $b$ 的 $(1,7)$；它比较发送者标识，选择 $a$。$c$ 自己的标识为 2，并不参与这次破平局。最终父边为 $sa,sb,ac,cd$，边 $bc$ 保留为网络边，却不进入这棵树。

各轮消息数依次为 $2,4,3,1$，总共 10 条。第 3 轮末所有输出已稳定，第 4 轮 $d$ 仍按一次转发规则发送，随后全体按共同约定停止。这也展示了“答案已经不变”和“执行到规定停止时刻”的区别。

一条路径上的全局最小标识下界 ​

现在换一个输出任务：要求每个节点输出全图实际出现的最小标识。即使允许 LOCAL 的任意长消息，远端的新信息也不能跳过通信距离。先证明一个局部性事实：固定拓扑和端口编号，若两次确定性执行在 $v$ 的半径 $r$ 邻域内具有完全相同的初始状态，则 $v$ 完成 $r$ 轮后的状态相同。这里初始状态包括自己的标识、度数、端口、共同规模及其他本地输入。[3]

证明对 $r$ 归纳。$r=0$ 就是初始状态相同。若半径 $r+1$ 内的初始状态相同，则 $v$ 及其每个邻居的半径 $r$ 所需信息相同；由归纳假设，它们第 $r$ 轮后的状态相同。因此第 $r+1$ 轮邻居向 $v$ 发送的消息、$v$ 的旧状态和收件箱都相同，确定性更新给出相同的新状态。消息再长也不会改变这个因果依赖。

具体取 $n\ge 3$ 的路径 $v_0,\dots ,v_{n-1}$，直径 $D=n-1$，标识允许来自 $[2n]=\{1,\dots ,2n\}$。两次执行都令

仅改变最远端点：执行 A 中 $\mathrm{ID}(v_{n-1})=1$，执行 B 中为 2。每次执行的标识均唯一、均在允许范围内，且只需 $O(\log n)$ 位。拓扑、端口、共同 $n$ 及其他初始输入完全相同。

对任意 $r<n-1$，$v_0$ 的半径 $r$ 邻域都不包含被改变的端点，故其第 $r$ 轮状态相同；然而 A 的正确答案是 1，B 的正确答案是 2。如果算法在这之前给出最终输出，两次输出必相同，至少一次错误。因此任何正确的确定性算法，在这对合法输入上都不能保证少于 $n-1=D$ 轮完成。LOCAL 已有此下界，消息能力更弱的 CONGEST 也一样。

标识范围在这里承担实质作用。若事先承诺标识恰为 $[n]$ 的一个排列，所有节点一开始就能输出数值 1；识别谁拥有这个标识则是另一种任务。若节点初始就知道邻居标识，端点变化会提前泄露一跳，上述输入对只直接给出 $D-1$ 轮界。本页的 $D$ 轮论证因此明确采用“只知自己的标识”的输入契约。

哪些改变需要新的证明 ​

异步网络中，先到达的消息可能沿更多条快速边绕行，首次收到不再保证最少跳数；加权边也让“层数”与权重最短距离分离。故障、动态拓扑、共享无线信道和匿名网络则分别改变交付、邻接、带宽或破平局条件。这些模型仍可研究分布式图算法，但需要重新说明程序与不变量，不能仅更换模型名称便沿用本页结论。

设根的离心率为 $e(s)=\underset{v}{max}\delta (s,v)$。逐轮不变量表明，全部距离与父节点在 $e(s)\le D\le n-1$ 轮后稳定；本页明确采用的共同停止时刻则为 $n-1$ 轮。因而这是一个具有 $O(D)$ 输出稳定时间、$n-1$ 规定运行轮数的协议。要让程序在 $O(D)$ 轮内检测完成并停止，还需要另行设计确认与回声汇聚机制；单有父指针不会自动告诉节点谁已选择自己为父节点。[2]

每个节点至多沿每个端口发送一次，所以有向数据包总数满足

每包只含有限距离与发送者标识，共 $O(\log n)$ 位，因而协议满足 CONGEST，总有效载荷为 $O(m\log n)$ 位。停止计数器、距离、父端口和布尔量只需 $O(\log n)$ 位本地持久状态；逐条处理收件箱即可保留当前最小发送者，无需永久保存全部邻居标识。这里未计底层网络帧和实现缓冲，也不把逐轮等待直接称为常数本地 CPU 工作。

BFS 父树提供到指定根的最少跳路由：每个节点只须沿父端口转发，距离便严格下降。若要反向广播或汇聚，还可在建树后让节点向父节点报告身份，使父节点得到孩子集合，再设计后续协议。每个节点保存一条到根的方向，并不等于已经掌握任意两点之间的最短路。

局部性下界也帮助区分任务的需求。全局最小标识必须获取可能改变答案的远端信息；Cole–Vishkin 颜色缩减公理库Cole–Vishkin 颜色缩减Cole–Vishkin color reduction · 确定性环三染色在给定一致方向的同步环上，用首次差异位反复压缩合法颜色，再以三轮消色得到三染色。则在给定方向的环上不断交换局部颜色，以局部不变量取得合法染色。本页下界没有宣称一切图任务都需要直径轮数，也没有给出 CONGEST 特有的带宽瓶颈；它准确刻画的是指定全局输出的因果传播成本。

CONGEST割模拟与四色四环公理库CONGEST 割模拟与四色四环下界CONGEST cut simulation · Two-party simulation across a graph cut · CONGEST 通信下界归约构造直径至多3的四色四环检测实例，逐轮模拟固定图割，以精确消息编码把DISJ通信下界换算为CONGEST轮数下界。进一步给出只来自带宽的下界：即使直径至多3，指定节点的检测任务仍需$\mathrm{\Omega }(N/\log N)$轮。证明通过两方独立模拟两侧，将每边每方向的消息位数逐项记账，与本页的因果传播界互补。