2.6 复杂度度量

对于同步的分布式算法，我们通常考虑两种复杂度度量：时间复杂度和通信复杂度。

同步网络系统时间复杂度是根据所有要求的输出都生成或者进程全部停止时已运行的轮数度量的。如果系统允许可变的开始时间，则时间复杂度会从任一进程被唤醒的第一轮开始度量。

通信复杂度通常按已发送的非空消息的个数来度量。有时，我们也会考虑消息的比特数。

在实践中，时间复杂度更为重要一些，不仅是对同步的分布式算法，对所有的分布式算法都是这样的。通信复杂度只有当拥塞严重到处理进程缓慢时才变得重要。这说明我们似乎可以忽略通信复杂度而只考虑时间复杂度。然而，通信负载对时间复杂度的影响不仅仅是某个单独的分布式算法的函数。在一个典型网络中，许多分布式算法同时运行，共享同一网络带宽。任一单个算法加入链路的消息负载都会增加该链路总的消息负载，从而加剧形成影响所有算法的拥塞。因为要量化任一算法的消息对其他算法性能的影响是很难的，这里我们只简单分析单个算法所产生的消息数（同时试图使其最小化）。