拜占庭将军问题是由 Paxos 算法作者莱斯利·兰伯特提出的点对点通信中的基本问题。
该问题要说明的含义是,在不可靠信道上试图通过消息传递的方式达到一致性是不可能的。
所以,Paxos 算法的前提是不存在拜占庭将军问题,即信道是安全的、可靠的,
集群节点间传递的消息是不会被篡改的。
一般情况下,分布式系统中各个节点间采用两种通讯模型:共享内存(Shared Memory)、
消息传递(Messages Passing)。而 Paxos 是基于消息传递通讯模型的。
Paxos算法:
(1)三种角色
- Proposer:提案者
- Acceptor: 表决者
- Learner: 同步者
(2) Paxos 算法的一致性
Paxos 算法的一致性主要体现在以下几点:
- 每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号 N, 即在整个集群中是唯一的编号 N,然后将该编号赋予其要提出的提案。
- 每个表决者在 accept 某提案后,会将该提案的编号 N 记录在本地,这样每个表决者中保存的已经被 accept 的提案中会存在一个编号最大的提案,其编号假设为 maxN。每个表决者仅会 accept 编号大于自己本地 maxN 的提案。
- 在众多提案中最终只能有一个提案被选定。
- 一旦一个提案被选定,则其它服务器会主动同步(Learn)该提案到本地。
- 没有提案被提出则不会有提案被选定。
- 参考:Paxos 与拜占庭将军问题