Distributed Computing Theory · 交互式可视化
分布式计算理论可视化实验室
从 CAP 三选二到 FLP 不可能性，从共识上界到拜占庭容错。8 个模块拆解分布式系统在异步、故障、消息丢失下的根本理论极限。
编号 150分类 Cross-disciplinary模块 8风格 Linear Dark依赖 零渲染 SVG
01CAP 定理 · Consistency Availability Partition
在网络分区 (P) 不可避免时，系统只能在一致性 (C) 与可用性 (A) 间二选一。点击三角顶点切换系统选择，观察分区下的行为。
CP (保一致)
AP (保可用)
CA (无分区)
分区发生时：CP 拒绝写入保证一致 (如 ZooKeeper/Paxos)；AP 接受写入允许分歧 (如 Dynamo/Cassandra)；CA 假设网络可靠，现实不存在。
02FLP 不可能性 · 异步共识无解
Fischer-Lynch-Paterson (1985)：异步系统中只要有一个进程可能崩溃，确定性共识协议无法同时保证终止性与安全性。逐步演示为何永远存在「不确定」执行。
阶段0
初始 双价 (bivalent) 状态可被调度推迟到无限——只要有一个进程能在关键时刻崩溃，共识既不能保证终止。实践中用随机化或放宽终止性绕过。
03共识上界 · Quorum 与容错阈值
崩溃故障需 N ≥ 2f+1 (多数派)；拜占庭故障需 N ≥ 3f+1。调节故障数 f 观察所需副本数与容忍度。
故障数 f
2
所需副本 N: —
Quorum: —
容错率: —
CFT：N=2f+1，Quorum=f+1 (多数写)。BFT：N=3f+1，Quorum=2f+1 (需超过 2/3 一致)。这是 Raft/Paxos 与 PBFT/HotStuff 的根本分界。
04Wait-Free 层次 · 共识数层级
共识数 (consensus number) CN(X) = 用对象 X 能解共识的最大进程数。层级严格：读/写=1，test-and-set/swap=2，compare-and-swap=∞。点击层级查看。
读写寄存器
TAS / Swap
队列 / 栈
CAS / LL-SC
共识数 CN: —
层级: —
能解 N 进程共识: —
Herlihy 层次定理：若 CN(Y) > CN(X)，则 Y 不能用 X 无等待 模拟。CAS (CN=∞) 是通用原语，可构造任意对象的无等待实现。
05拜占庭将军问题 · Byzantine Generals
叛变将军可发任意消息。切换叛徒数量与叛徒行为，观察忠诚将军能否达成一致行动。
06故障模型对比 · Failure Model Spectrum
崩溃 (crash) → 遗漏 (omission) → 时序 (timing) → 拜占庭 (byzantine)，故障行为越来越「任意」。切换模型查看进程可能的行为集合。
Crash
Omission
Timing
Byzantine
故障模型是包含关系：crash ⊂ omission ⊂ timing ⊂ byzantine。模型越强，协议越复杂、副本越多。实际系统多按 crash 假设设计，安全关键场景才用 BFT。
07一致性保证级别 · Consistency Levels
从线性一致性 (最强) 到最终一致性 (最弱)，层级按可组合性排列。点击级别查看保证与代价。
Linearizable
Sequential
Causal
FIFO (PRAM)
Eventual
层级：Linearizable ⊃ Sequential ⊃ Causal ⊃ FIFO ⊃ Eventual。线性一致性可组合 (LOCUS)，但需全局总序与同步，延迟最高；最终一致性性能最好但推理最难。
08分布式计算模型 · Shared Memory vs Message Passing
共享内存 (读写寄存器) 与消息传递 (send/receive) 是两种基本模型，在异步可崩溃下等价。切换模型与同步假设查看可解问题。
异步+崩溃：共识不可解 (FLP)。同步+崩溃：共识可解 (Paxos 退化为多数派)。共享内存与消息传递可通过 队列/寄存器模拟 互译，计算能力等价。