共识与协调
共识与协调旨在解决独立进程（仅通过消息通信）如何在存在延迟和故障的情况下就共同的值或行动达成一致。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
共识是指一组进程，每个进程提出一个值，所有进程最终决定一个单一的共同值，使得该决定有效，所有正确进程达成一致，并且每个正确进程最终做出决定，即使某些进程发生故障。
Scope
该领域涵盖共识问题及其变体（一致性、原子广播、有效性、终止性）、确定性异步共识的FLP不可能性基础结果、Paxos和Raft等实用共识协议、拜占庭容错协议，以及互斥和领导者选举等经典协调问题。它是容错分布式计算的理论和实践核心。
Sub-topics
Core questions
- 在何种时序和故障模型下，共识是可解的，何时被证明是不可能的？
- 实用协议如何规避FLP不可能性同时保持安全性？
- 为了容忍崩溃故障和拜占庭故障，需要多少复制？
- 进程如何可靠地协调对共享资源的访问或选举领导者？
Key theories
- FLP不可能性
- 在完全异步系统中，如果即使只有一个进程可能崩溃，任何确定性协议都无法保证共识，因为慢速进程无法与失败进程区分开来；这一结果促使了部分同步、随机化和故障检测器的发展。
- 基于法定人数的共识
- Paxos等协议通过要求重叠的多数（法定人数）接受提议来达成一致，确保任何两个决定都在一个正确进程处相交，从而在轮次和领导者变更中保持一致性。
- 拜占庭协议界限
- 在经典同步设置中，当多达f个进程可能任意行为时，要达成一致至少需要3f+1个进程，这是一个严格的界限，它塑造了所有拜占庭容错系统的设计。
Clinical relevance
共识是可靠基础设施的支柱：协调服务、复制数据库、分布式锁和区块链都运行共识协议以保持副本一致性，这使得该领域直接负责现代云系统的持久性和可用性保障。
History
1982年的拜占庭将军论文和1985年的FLP不可能性结果界定了达成一致的局限性；Lamport的Paxos（1989年传阅，1998年发表）提供了一个实用的异步安全协议，后来关于拜占庭容错和Raft的工作使得共识既能抵御恶意故障，又易于实现。
Debates
- FLP不可能性是否使得共识在实践中无法实现？
- FLP排除了在完全异步模型中始终既安全又活跃的确定性协议，但实际系统通过假设最终同步或使用随机化来规避它，从而保持无条件安全并在网络行为良好时实现活跃性。
Key figures
- Leslie Lamport
- Nancy Lynch
- Michael Fischer
- Michael Paterson
- Barbara Liskov
Related topics
Seminal works
- fischer1985
- lamport1998
- lamport1982byz
Frequently asked questions
- 为什么共识被认为是分布式系统中最困难的问题？
- 因为许多其他协调任务——原子广播、复制状态机、分布式锁——都可以归结为共识，而共识本身在异步崩溃故障模型中被证明无法确定性地解决，因此任何解决方案都必须做出仔细的时序或随机性假设。
- 共识与复制数据库有何关系？
- 复制数据库通过就操作顺序达成一致来保持其副本的一致性，这正是共识决策的序列；这就是为什么像分布式键值存储这样的系统在其核心嵌入了共识协议。