共识算法
共识（consensus）与昨天提到的一致性经常是放在一起讨论的，一致性指的是系统的结果状态，共识则是一个手段，过程，解决的是多个节点对某个proposal达成一致意见的过程。
一般把出现故障但不伪造信息的情况成为“非拜占庭错误”；
出现故障并且伪造信息进行恶意相应的称为“拜占庭错误”，同时对应结点，称为拜占庭节点；
常见算法
Paxos 算法 与 Raft算法
Paxos算法将节点分为了三个逻辑角色：
- proposer:提出一个题案，等待其它结点选择、批准，通常担任该角色的为客户端；每个编号都应该有一个ID，通常是递增ID；
- accepter: 负责对题案进行投票，是否接受该题案；
- learner:获取投票结果，但不参与投票，可以将投票结果传播到其他地方；
基本过程：多个proposer争取到了提出提案的权利，得到权利的proposer发送提案给所有人，得到多数人确认通过的提案会成为最终批准的提案。
为了保证accepter能够获知其它accepter也收到了自己的投票信息，验证自己的投票结果是否构成了大多数的意见，并且proposer能收到自己的投票，该算法得实现两个提交阶段：
- prepare：
- 有权利的proposer发送自己的提案到accepter；
- accepter保留着收到过的提案中最大的编号。如果收到了新的提案，而该提案比保留编号要大，则返回已接受的编号和提案内容，更新当前最大编号，意味着不接受小于当前最大编号的提案；
- commit
- proposer如果接受到多数的回复，则准备发出带有刚才提案ID的接收消息。如果收到的回复不带有新的提案，则说明锁定成功，可以发送自己的提案内容；如果收到了新的提案内容，则替换提案ID为接受的提案中最大的ID值；如果没有收到回复，则重发；
- accepter收到消息之后，发现该提案ID不小于已接受的最大提案ID，则接受该提案，并更新信息；
- 一旦多数accepter接受了共同的提案ID，则形成最终决议。
Raft算法也将服务器节点分为三种逻辑角色：
- Leader: 处理所有的客户端交互，一次只有一个leader；
- Follower: 刚开始集群中所有节点都是follower；
- Candidate: 能被宣称leader；
基本过程：
- 首先是选举。任何一个follower都能成为一个candidate，成为candidate后向其它的follower发起选举自己的请求，自己也可以投票给自己，一旦票数大于二分之一，则表示通过、达成一致，成为leader；选出leader后，leader需要定期向follower发送信息，表示自己的通知，如果在一定时间内follower没有收到信息，则认为leader宕机，重新选leader；
- 以日志复制来表现raft算法，假设leader被选出后，此时客户端要求增加一个日志，leader会要求follower将该日志追加到自己的日志记录中去。多数的follower在追加日志成功后，会发出确认信息。然后，leader会通知所有的follower完成commit。
如果在这个过程中，由于网络分区或者故障，leader只能访问部分follower，那么另外一部分的f大多数follower则会选出新的leader，与客户端交互。这个新的leader会按以上步骤通知大多数的follower。此时，如果网络恢复了，旧的leader会变成follower，此时旧的leader的更新都必须回滚，从新的leader处同步所有数据。
其它一致性的保障可以参考：http://www.cnblogs.com/mindwind/p/5231986.html