简单分布式系统
我们先从最简单的问题开始。对于只有两个节点的分布式系统，一个客户端节点，一个服务器节点，客户端向服务器发送消息，想要操作服务器上的数据（存储或更新），最简单的算法1为：
1. 客户端每次向服务器发送一条命令
消息如果损坏，可以在消息中添加校验码。但是，如果这条消息丢失了，根本没到达服务器节点，那么这个算法是无法处理的。所以继续改进这个算法，服务器节点每收到一条消息，就发送一个确认消息给客户端节点。算法2：
1. 客户端每次向服务器发送一条命令
2. 服务器每收到一条命令，都会发送一条确认消息
3. 如果客户端在一定时间内没收到确认消息，就重新发送命令
客户端每次只发送一条命令，在收到服务器的确认信息之前，客户端不会发送下一条命令。这个算法依然有问题，如果确认消息丢失了，客户端没等到，那又会重新发送命令，这样服务器就有可能收到重复的命令。为了解决这种情况，就给每条命令加上序列号，这样通过序列号就可以判断出命令是否是重复的。对于多个服务器，这个算法也是行得通的，客户端给每个服务器都发送命令，当它收到所有服务器发来的确认消息后，就可以判断出命令都已经被服务器正常接收。
如果有多个客户端，算法2就无法处理了，因为无法保证一致性。假设有两个客户端同时维护一个服务器上的数据，发送一条命令的时间可以确定，但是命令到达服务器的时间和顺序是无法确定的，即使两个客户端同时发送命令，服务器接收到的顺序也是无法确定的。这种情况下，就需要保证客户端命令的串行化。增加一个“串行化器”的算法3：
1. 所有的客户端都向串行化器发送命令，每次发送一条
2. 串行化器将命令逐条转发给所有服务器
3. 串行化器收到针对某条命令的所有确认消息，它通知发送该命令的客户端该命令已经被执行
算法3虽然实现了不同节点的一致性的操作序列，但是这个方法不够“分布式”。而且，如果串行化器故障了，整个系统就崩溃了。换一种思路，应该可以想到“PV”操作。通过互斥、加锁的方式，让每次只有一个客户端能够发送命令。算法4：
阶段1
1. 客户端向所有服务器请求锁
阶段2
2. if 该客户端成功获得了所有服务器的锁 then
3. 该客户端以可靠的方式向每个服务器发送命令，之后释放锁
4. else
5. 该客户端释放已经获得的锁
6. 该客户端等待一定的时间，再重新进入阶段1
7. end if
算法4是一种两阶段协议，它确实能够比算法3有更好的一致性，但是它仍不能很好地处理异常。因为算法4必须保证所有的服务器都能正常响应，如果有一个服务器不能正常响应，就进行不下去了。还有多个客户端同时争抢大多数服务器的锁的时候，以及客户端释放锁之前发生故障等等情况该如何处理，都值得我们去思考。
两阶段提交协议（Two-Phase Commit, 2PC）,典型应用场景是数据库系统，第一个阶段称为事务的准备阶段，第二阶段中这个事务提交（Commit）或者撤销（Aborted）。使用了一个额外阶段的改进协议称为3PC。
投票
由上面的分析，我们可以看出，“锁”的效果也不是十分理想。接下来我们引入“投票”这种方式，来使得整个分布式系统达到一致的状态。票可以看做是一个弱化的锁。一个服务器可以随时发布新的票，即使前面的发布的票还没有被释放；票是会过期的，当客户端使用一张票给服务器发送消息时，它的票必须是最新的，才会被服务器接收。这种方式，系统不会因为持有票的某个客户端出故障而崩掉，因为服务器可以发布新的票，别的客户端也不会受影响。不像“锁”，获得锁的那个客户端如果出了故障，系统就会出问题。算法5：
阶段1
1. 客户端向所有的服务器请求一张票
阶段2
2. if 收到过半数服务器回复 then
3. 客户端将获得的票和命令一起发送给每个服务器
4. 服务器检查票的状态，如果这个票仍然是有效的，则存储命令并给这个客户端一个正反馈消息
5. else
6. 客户端等待，并重新进入阶段1
7. end if
阶段3
8. if 客户单从过半数服务器处得到了正反馈 then
9. 客户端告诉所有的服务器执行之前存储的命令
10. else
11. 客户端等待，然后重新进入阶段1
12. end if
这里的票可以使用计数器来实现，可以用计数器实现票号。每当服务器接收到一个发布票的请求时，就将计数器加1。这样客户端尝试向服务器发送请求使用某个票时，服务器可以判断这个票是否过期了。但是，算法5还是有问题，如果一个客户端成功让超过一半的服务器存储了它的命令，但是它如果非常慢，还没来得及告诉所有服务器执行它的命令的时候（第9行），另一个客户端已经将部分服务器中存储的命令更新为它的了，然后前一个客户端才广播所有的服务器执行命令，这时，就会导致一部分服务器执行前一个客户端的命令，一部分服务器执行后一个客户端的命令。
要解决上面的问题，假设前一个客户端为C1,后一个客户端为C2。如果在阶段1中，服务器不止发布票，还发布了它当前存储的命令，C2收到这个消息之后，就不要求服务器存储自己的命令了。这样C1和C2命令的先后顺序可以解决。但是，又有一个问题，如果在阶段1，一个客户端就从不同的服务器接收到多个不同的命令，它会很懵的，不知道该听哪一个，因为规定过半数服务器都一致的命令，所有客户端都必须无条件执行。所以，为了判断一个命令是不是最新命令，在阶段1服务器需要把自己的存储的命令的票号和命令都发给客户端。但是，如果服务器使用自己的票号，那么最新的票号不一定是最大的，为了解决这个问题，可以让客户端自己产生票号。这就相当于客户端节点自己提出了一个“提案”。把这些都完善了之后，实际上就是Paxos算法了。
Paxos算法
Paxos算法中有两个角色，一个是提案者，一个是接收者。Paxos分为两个阶段，第一个阶段为准备阶段（Prepare），第二个阶段为提交阶段（Commit）。在第一个阶段中，提案者发出提案请求，然后获得接受者的反馈。第二个阶段，判断提案是否得到大多数的支持，得到大多数支持之后进行最终确认。
准备阶段：
- 提案者发送自己计划提交的提案编号到多个接受者，试探是否得到大多数的支持
- 接受者时刻保留收到过提案的最大编号和接受的提案值。如果收到的提案号比目前保留的最大的提案号还要大，则返回自己已经接受的提案值，（如果还未接受到任何提案，则为空）给提案者，并更新当前最大提案号，并说明不再接受小于提案号的提案
提交阶段：
- 提案者如果收到大多数的回复（表示大部分人听得到它的请求），则可准备发出带有刚才提案号的接受消息。如果收到的回复中不带有新的提案，说明锁定成功。则使用自己的提案内容；如果返回中有提案内容，则替换提案值为返回中编号最大的提案值。如果没收到足够多的回复，则需要再次发出请求
- 接受者收到“接受消息”后，如果发现提案号不小于已接受的最大提案号，则接受该提案，并更新接受的最大提案。一旦多数接受者接受了共同的提案值，则形成决议，成为最终确认
具体算法可表示为算法6：
客户端（提案者）：
初始化
c //等待执行的命令
t = 0 //当前尝试的票号
阶段1
1. t = t + 1
2. 向所有的服务器发消息，请求得到编号为t的票
阶段2
7. if 过半服务器回复ok then
8. 选择Tstore值最大的（Tstore, C）
9. if Tstore > 0 then
10. c = C
11. end if
12. 向这些回复了ok的服务器发送消息:propose(t, c)
13. end if
阶段3
19. if 过半数服务器回复sucess then
20. 向每个服务器发送消息：execute(c)
21. end if
服务器（接受者）：
初始化
Tmax = 0 //当前已发布的最大票号
C = ⊥ //当前存储的命令
Tstore = 0 //用来存储命令C的票
阶段1
3. if t > Tmax then
4. Tmax = t
5. 回复：ok(Tstore, C)
6. end if
阶段2
14. if t = Tmax then
15. C= c
16. Tstore = t
17. 回复：sucess
18. end if
学习资料：《The Science of the BlockChain 区块链核心算法解析》 [瑞士]Roger Wattenhofer 著； 陈晋川，薛云志，林强，祝庆 译
