PAXOS算法应该是目前所有分布式算法的鼻祖，它由大师LESLIE LAMPORT所提出，在此基础上衍生出了RAFT，multi-paxos等多种算法，本质上都是一个目的：在分布式的环境中如何保证若干个节点得到一个共识结果？

问题描述

共识算法是指：在一个分布式系统中有多个相互独立的节点，每个节点都可以提议一个值，但是最后只会有一个值会被接受。当一个值被接受的时候，分布式系统中所有的节点都可以将这个决定记录在自己的存储中，供用户查询使用。请注意以下几点：

  • 所有被提议的值中只会有一个值被接受
  • 只有当一个值被接受后，分布式系统中的节点才能记录这个值，这个过程我们通常称为学习。

对于集群中的节点，我们将其分为3种角色：

  1. proposer：负责发起提议
  2. acceptor：负责决定提议（即决定选取哪一个提议）
  3. leaner：负责获取被接受的提议，并将提议提供给外界使用

对于所有的分布式节点，我们假设如下：

  • 节点之间通过发送消息的方式进行通信，p2p
  • 节点所有操作均是异步的
  • 不考虑拜占庭将军问题，即没有节点会故意发送错误信息，所有的节点都会按照预设模式发送信息
  • 任何节点都以随机的速度进行工作，可能会因为停止而失败，已经停止的节点随时有可能重启。节点必须含有一定的持久化方式，否则如果集群中所有节点都挂掉的话，集群将丢失之前的决议信息。
  • 消息发送消耗的时间也是随机的，消息可以重复、丢失，但是不会被篡改。

值的选择

所有复杂的算法都离不开最简单的模型，设想一下，如果集群中只有一个acceptor，那么它只要决定它所接收的第一个提议即可。这个模型满足上述的所有问题，但是如果唯一的acceptor因为某些原因无法提供服务（网络断开或者宕机），将导致整个集群无法继续工作。（典型的单点问题）

为了避免单点问题，那么我们必须选取acceptor的集合来代替单个acceptor。为了保证仅有一个值被选取，那么只有足够多的acceptor共同确定的值才能被作为整个集群所决定的值。这里的足够多即大于集群数量的一半，用反证法可轻松证明，这里就不赘述了。

接下来要讨论的问题是：每一个acceptor将按照如何的规则确定值？假设一个acceptor在一段时间内收到了a，b，c三个值，那么它会选择哪个作为自己所确认的值呢？理论上来讲：选a、b、c都没有关系；但是当你接受到a之后，由于网络能因素，可能根本就没有b、c了…因此，选择第一个接受的值自然是较为稳妥的方案。

  • P1：一个acceptor必须接受它所收到的第一个提议值。

但是集群内同一时刻会有多个不同提议值存在，最极端的情况下：集群中只有两个acceptor，一个接受了值a，另一个接受了值b，此时算法将无法继续进行。 消息中只含有提议值的话，这个问题将无法避免，因此我们引入新的信息用于辅助acceptor决定在这种情况下应选择什么样的值。LAMPORT 大佬的方案是：我们将这些提议都加一个单调不减的序号，并且每个提议值的序号都各不相同（具体实现这里不考虑）。于此，提议的信息变为一个二元组：序号 + 值。当大多数acceptor确定这个提议，也就等同于确定了这个值。这二者在过程里是等价的。

回到刚才的问题：一个acceptor能否多次确认一个提议？如果不能，那么两个节点的死锁问题就无法得到解决；那么答案自然就是可以了，如何做呢？在常人无法跨越的思维鸿沟前面，大佬又来指路了：只要保证提议的值是一样的，一个acceptor可以确认多个提议。 由于1.提议的序列号随时间递增；2.一个系统往往随着时间的推移而变得有序。因此，序列号大的提议往往代表着包含同值小序列号的信息，因此不难得出结论：值一样的话，选序列号大的那个。根据以上推论，我们可以得出第二个约束条件：

  • P2: 对于任意一个acceptor，当它选择了值为v的提议后，它将会同样选择每一个序列号更大，且值同样为v的提议。

P2可以保证：当任意一个value被集群决定后，不会被其他value替代。因为任意一个acceptor只会接受同样value的提议，对于集群而言，任一value被多数acceptor确定后，虽然确认的提议可能会变，但这些acceptor都不会改变value的值