paxos白话版

详细论证内容请参考作者写paxos-simple.pdf，开头就写了一句：The Paxos algorithm, when presented in plain English, is very simple.（表示鸭梨很大）

 

假设场景：a、b、c、d在一起工作，经常需要对某件事情快速达成一致（无对错、优先级区别）；且相互之间是通过消息沟通，可能存在消息丢失、重发等情况，但保证消息不会损坏.

1.选择其中某人来决定选择那个提议，且选择自己收到的第一个提议；如选择a.
问题：若a生病未来，则所有的事情都没法继续进行.
1.1 改进：选择多个人来决定选择哪个提议.
如何判定通过：当超过n/2+1.
问题：若a、b同时提出提议，a、b同意a+提议，d、c同步b+提议，则仍无法达成一致
1.1.1 改进：每个人可以选择多个提议.
问题：但存在a、b、c先同意a+提议，则a+提议通过；b、d、c同意b+提议，则同时存在多个被通过的提议.
1.1.1.1 改进：限制某个提议通过后，后续通过的提议的内容相同

2.关键如何保证：某个提议通过后，后续通过的提议的内容相同
2.1 等价条件：某个提议通过后，后续提出的议案的内容与已通过提议的内容相同
如何实现：二阶段提交
2.1.1 活锁问题
改进：选择其中某个人作为主提议者，其它人不能提出提议
问题：如何选择’主提议者’.

3.如何通知其它人已经通过的决议.

 

参见：http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf