Paxos 与拜占庭将军问题

拜占庭将军问题是由 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 与拜占庭将军问题
上一篇:Ceph剖析:Paxos算法实现


下一篇:Raft和Paxos简易漫画理解