土法炼钢 · 系统与基础设施

【分布式系统百科】05 · 分布式系统的复杂性度量：消息复杂度、轮次复杂度与空间下界

2026-04-13 | distributed | #complexity #message-complexity #round-complexity #lower-bound #consensus #leader-election #distributed-systems

顺序算法用时间复杂度和空间复杂度就能衡量好坏。分布式算法多了消息复杂度、轮次复杂度和容错数量三个维度，三者之间存在不可调和的 trade-off。本文从选主、共识、广播三个典型问题出发，梳理这些度量指标的定义、下界和工程影响。