Paxos Made Simple Introduction :其实，这是最简单最明显的分布式算法之一。 其核心是宗教共识算法。
theconsensusalgorithmtheproblem共识算法确保仅从建议的值中选择一个。
共同的安全要求：
只有建议的一个值可能会被选择。 只选择了一个值的进程不知道已经选择了一个值，除非最终学习了已经选择的值。
共识算法有proposers、acceptors、and learners个作用。
算法基于这样的假设模型，假设了传统的异步、异步拜占庭模型。 除非一个代理记住了一些失败和重新启动的信息，否则所有节点在选择值时都会下降并重新启动，以前的解决方案可能会丢失。 数据可以重复、丢失或在任意时间发送，但不得损坏。
Choosing a Value选择单个加速器是最简单的，但容易出现单点故障。
多个加速器使用大多数accept原则选择值。 假设一个节点最多接受一个值，因为两个大多数必须相交，所以确保大部分足够大的集合只选择一个值。 如果不考虑消息的丢失，失败了的话，即使一个值被推荐给一个提案人，我们也希望这个值被选中。 这需要以下内容。
P1.一个acceptor必须接受它受到的第一个议案
考虑到同时提案，因为每个提案都满足很多条件，所以允许一个accept接受多个提案，我们通过用号码区分提案，可以选择多个提案，但是提案的值必须相同
P2.如果一个v值的提案被选择，更高序号的提案被选择的值也必须是v
因为被选择的话会被accept
P2a.如果一个v值的提案被选择，更高序号的提案被accept的值必须是v
由于异步P1条件，瘫痪的加速器必须接受最初的提案，因为违反P2a，所以加强限制
P2b.如果一个v值的提案被选择，更高序号的提案被issue的值必须是v
假设在n之前选择了m，v，则每个acceptor假定c具有m…((n-1 )编号，且n-1 )编号接受的提议的必须值为v
通过s集的大多数原则，只要确保以下条件，第n个就可以推出v，即n，v。
P2c.对于任意v和n,如果一个n,v被issued,必须要满足S中的没有acceptor，accept了一个提案或者一个低于n的最高序号的提案值是v被accepted
因为很难预测，学习已经被accept的东西很简单，所以通过获取promise进行控制，accept不会去大于n的东西。
Proposer的算法：
1.prepare :让加速器承诺不再接受小于n的，小于n的已经取得加速器。
2 .发送信息。 v必须是低于n的最高编号的提议值，如果没有任何提议，则v也可以是提议者选择的值
Acceptor算法：
可以接收prepare和accept请求，以防止ignore请求影响安全。
P1a.一个acceptor可以接收一个n序号的提案，如果它没有回应一个比n更大的prepare
小优化：已经接受了n，忽略小于n的，也忽略已经收到的提案的prepare要求
此优化后的加速器应记住最大建议号和最大准备请求号。 无论失败还是重新启动，请记住。 你可以随时取消提案。 在同一序列号issue上不尝试提出其他方案。
phase1.(a )向许多acceptors发送n准备请求
) b ) n大于任何东西，promise不接受小于n的东西，是promise携带前接受的最大提案
Phase2.(a)大多数acceptors对准备回应了，发送accept请求，携带n,v
(b)如果没有响应一个更大的准备请求，接收提案。
可以发送更大的号码取消提案。 更大的值表示忽略提案后，告诉提案人取消提案。
Learning a Chosen Value学习为了知道选择的值，最简单的算法是知道各acceptor收到了提案，但是通信量太多了。 非拜占庭模型假定这样做很简单，因此可以向区分为加速器的学习者发送消息，并将学习者发送到其他学习者。 此方法需要额外的循环来发现所有learners选定的值，虽然数据量稍少，但单点故障是最不可靠的。 更一般地说，用Learner集合，集合越大通信越复杂。 选择数值后，信息将会丢失，不再被发现。 此时，Learner可以询问加速器，但会发生加速器失败，不知道是否已接受该建议。 在这种情况下，再次达成了共识。 如果想知道某个learners是否被选择了值，就把learner作为提案者用以上算法发送提案。
Progress死锁选择proposer作为唯一的去往iss以确保该过程
ue提案，如果它发送的提案被大多数接收，发送的序号比之前的都大，它就会成功。通过取消提案，增大序号，这个区别出来的提案者最终会成功。 The Implementation这个算法选择一个leader,扮演着区别出来的proposer和learner。防止混淆，响应都会带着序号，acceptor必须记录些信息，需要稳定存储，失败时保存。这些遗留的信息就是描述保障机制，没有两个议案使用同一个序号发送。不同的提案者再不相交集中选择序号，每个提案者记住最高序号的提案它issue过的，然后开始phase 1使用比它用过的更高的序号。
Implementing a State Machine分布式系统最简单实现方式：一群客户端向服务端issue命令，服务器可以被描述为不可逆转状态机，以一个顺序运行客户端命令，状态机有一个目前状态；通过输入一个命令运行一步，产生一个输出和一个新的状态。例如，分布式银行系统的客户端可能是tellers,状态机的状态可能由所有用户的账户余额组成。一个取出将会被运行通过运行一个状态机命令减少一个账户余额，只有在余额充足，输出新的余额。
一个服务器会出现单点故障。所以我们使用服务器集群。因为状态机是不可逆转的，如果他们都运行相同顺序的命令，所有的服务器会产生相同的状态顺序和输出。一个客户端issue一个命令可以然后使用任何服务器产生的输出。
为了保证命令顺序，我们实现了一个共识算法的顺序独立实例。第几次实例选择的值就是序列中第几条状态机命令，在每次算法中，每一个服务器扮演三个角色。
在正常操作中，单一 一个服务器被选作leader,leader扮演区别的proposer(唯一一个可以issue提案的)在所有的算法实例中，客户端发送命令给给leader,leader决定命令在序列中出现的位置。如果一个leader决定一个客户端命令应该是135条，他会让这个命令在第135次共识算法中被选中。他通常会成功，可能会因为失败而失败，或则脑裂，认为第135条提案应该是另一个提案，但是共识算法会保证最多一条命令被选成135条提案。
在正常情况下，之前的leader宕机，新的leader被选出，新的leader要知道最全的被选出来的命令。假设知道1-134，138，139-，然后对135-137和大于139的运行phase 1。假设运行确定了135，140要提案的值，但是剩下的其他提案都还没确定。Leader对135，140运行phase2，于是选择135，140命令。
Leader等待其他的服务器学习所有leader知道的命令，现在可以执行1-135。但是不能运行138-140，因为136和137没有被选出来。Leader可以通过下两条客户端命令请求形成136，137。我们填充了gap,一个特殊的“no-op”命令让状态不改变。一旦“no-op”命令被选择，138-140就可以被运行。
命令1-140被选出，就可以进行后续的命令了。Leader可以在知道141被选出之前，propose命令142。这可能导致141命令丢失，142被选完。当leader获取141实例的返回失败时，会重新发送信息。如果没问题会选出141，然而，在之前的失败，会出现一个gap。总的来说，一个leader可以提前获取a条命令，就会产生a-1条命令gap。
只需要发送一个合理的短消息给每一台服务器，每次共识算法就可以使用相同的提案序号。在第1阶段中，只有当acceptors已经收到了某个proposer发来的第2阶段消息时，它才会响应不止一个简单的OK(响应中包含accepted的值)。所以一个服务器可以响应所有算法实例通过一个简单合理的短消息。
失败再重选leader是一个小概率的事件，主要开销用在了共识的第二阶段。可以看出，Paxos 共识算法的第2阶段在存在故障的情况下，其达成协议的可能代价是所有算法中最小的。因此，Paxos算法本质上是最优的。
目前的leader失败，要选择了一个新的leader的中间时期。没有leader没有命令会被提案。多个服务器认为它们是leader,可能会阻止任何值被选择，出现死锁。所以选取是被需要的去保证进程。
如果服务器集可以更改，那么必须有某种方法来确定哪些服务器实现了共识算法的哪些实例。最简单的方法是通过状态机本身。当前的服务器集可以成为状态的一部分，并且可以用普通的状态机命令更改。通过让执行i + α共识算法实例的服务器集合根据执行第i条状态机命令后的状态指定，我们可以允许leader提前获得α条命令。这允许一个简单的实现任意复杂的重新配置算法。