编辑“︁一致性协议”︁

= 一致性协议 =

'''一致性协议'''（Consensus Protocol）是分布式系统中多个节点就某个值或状态达成一致的算法。它是构建可靠分布式系统的核心，确保即使部分节点故障或网络分区，系统仍能维持数据一致性和正确性。常见应用包括数据库复制、区块链、分布式存储等。

== 基本概念 ==
在分布式系统中，节点间需要通过通信协作完成任务。由于网络延迟、节点故障等因素，各节点可能观察到不同数据状态。一致性协议的目标是：
* '''安全性'''（Safety）：所有正确节点最终达成相同决定。
* '''活性'''（Liveness'''）：系统最终能做出决定（不无限阻塞）。

典型问题如'''拜占庭将军问题'''描述：如何让分散的将军（节点）在存在叛徒（故障节点）时达成一致进攻或撤退的决定。

== 常见协议 ==
=== 1. Paxos ===
由Leslie Lamport提出，分为'''准备阶段'''和'''接受阶段'''：
# 提案者（Proposer）向接受者（Acceptor）发送提案编号。
# 接受者承诺不接受比当前编号更小的提案。
# 提案者收到多数派接受后发送提案值。

<syntaxhighlight lang="python">
# 简化版Paxos伪代码
class Acceptor:
    def __init__(self):
        self.promised_id = 0
        self.accepted_value = None

    def prepare(self, proposal_id):
        if proposal_id > self.promised_id:
            self.promised_id = proposal_id
            return {"status": "promised", "accepted_value": self.accepted_value}
        return {"status": "rejected"}

    def accept(self, proposal_id, value):
        if proposal_id >= self.promised_id:
            self.accepted_value = value
            return {"status": "accepted"}
        return {"status": "rejected"}
</syntaxhighlight>

=== 2. Raft ===
更易理解的替代方案，将节点分为'''Leader'''、'''Follower'''和'''Candidate'''三种角色：
* Leader处理所有客户端请求并复制日志。
* Follower被动接收更新。
* Candidate参与选举。

<mermaid>
stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: 选举超时
    Candidate --> Leader: 获得多数票
    Leader --> Follower: 发现更高任期
    Candidate --> Follower: 发现更高任期
</mermaid>

=== 3. PBFT（实用拜占庭容错） ===
解决拜占庭故障（节点可能恶意响应），需至少3f+1个节点容忍f个故障节点。分三阶段：
# 客户端向主节点发送请求。
# 主节点广播至备份节点。
# 节点执行请求并回复客户端。

== 数学基础 ==
共识协议通常满足以下条件：
* '''协定性'''（Agreement）：所有正确节点决定相同值。
* '''完整性'''（Integrity）：每个节点最多决定一个值。
* '''有效性'''（Validity）：若某节点决定值v，则v必由某节点提出。

形式化表示为：
<math>
\forall p,q \in \text{Correct}: \text{decision}_p = \text{decision}_q
</math>

== 实际案例 ==
=== 案例1：Etcd中的Raft ===
Kubernetes使用Etcd存储集群状态，其Raft实现保证：
* Leader选举：5秒内完成故障转移。
* 日志复制：所有写操作需多数节点确认。

=== 案例2：比特币的Nakamoto共识 ===
通过工作量证明（PoW）实现概率性共识：
* 矿工竞争解哈希难题。
* 最长链被接受为有效历史。

== 挑战与权衡 ==
{| class="wikitable"
|+ 协议对比
! 协议 !! 故障模型 !! 消息复杂度 !! 延迟
|-
| Paxos || 崩溃故障 || O(n²) || 2轮RTT
|-
| Raft || 崩溃故障 || O(n) || 1轮RTT
|-
| PBFT || 拜占庭 || O(n²) || 3轮RTT
|}

== 进阶主题 ==
* '''最终一致性'''（Eventual Consistency）：如DNS系统，允许临时不一致。
* '''CAP定理'''：一致性（Consistency）、可用性（Availability）、分区容忍（Partition Tolerance）三者不可兼得。
* '''量子共识'''：未来可能利用量子纠缠实现超快共识。

[[Category:分布式系统]]
[[Category:算法]]

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:并行与分布式算法]]