分布式网络算法中round complexity（轮次复杂度）的含义及实例讲解

首先我们先拆解你提到的定义核心逻辑，再结合实例做具体说明：

在同步模型中，时间以被称为轮（rounds）的时钟滴答数来衡量，也就是说，处理器是按‘lock step（锁步）’进行计算的。运行分布式算法时，不同节点完成计算所需的轮次可能各不相同，这种情况下，所有节点所需的最长时间即为该算法的时间复杂度。

定义核心要点 #

• 它和单节点算法的时间复杂度衡量逻辑完全不同：单节点算法统计的是运算指令的量级，而分布式同步模型的时间复杂度不关心单个节点的计算量，仅以全局统一的通信轮次作为统计单位
• 锁步是同步模型的前提：所有节点的时钟完全对齐，每一轮所有节点同时执行三个步骤：接收上一轮其他节点发送的消息、完成本地计算、向外发送本轮要传递的消息，所有节点的动作严格对齐时钟节拍，不会出现时差

实例讲解 #

我们用最经典的洪泛广播算法举例：
现在有4个节点组成线性拓扑：A-B-C-D，需求是把A存储的一条消息同步给所有节点，规则是每一轮每个节点可以把自己刚收到的新消息发送给所有相邻节点。
每一轮的执行结果如下：

• 第1轮：A把消息发给邻居B，A完成自己的所有任务；B成功收到消息
• 第2轮：B把消息发给邻居C，B完成自己的所有任务；C成功收到消息
• 第3轮：C把消息发给邻居D，C完成自己的所有任务；D成功收到消息

4个节点完成任务的轮次分别是1、2、3、3，按照定义取所有节点的最长耗时，该广播算法在这个拓扑下的时间复杂度就是3轮。
我们可以用更生活化的例子理解：你要通知10层楼的所有员工开会，规则是每一轮已经收到通知的人只能给相邻楼层的人传话，所有人同时行动，那么不管前9层的人多早收到通知，这个通知算法的时间复杂度都等于最高的第10层员工收到消息的轮次。

常见误区 #

很多初学者会把消息总传输量、单节点计算量当成分布式时间复杂度的统计维度，这是错误的。同步模型下只要单节点能在当前轮的时钟间隔内完成计算、发送消息，哪怕它要处理百万级别的运算，也不会额外增加时间复杂度。

内容的提问来源于stack exchange，提问作者black sheep 369