本文来自王倬投稿，老刘做了修改。王卓，北京邮电大学硕士。研究方向为区块链技术、共识算法和零知识证明，对区块链技术底层有深刻理解。张胖子所在的部门连续三个月加班，系统终于上线了！经理计划组织一次部门晚宴来奖励大家。至于去哪家酒店，就留给大家商量了。没想到的是，这群人打的很凶，谁也说不上来。其中，张胖子和刘胖子吵得最厉害。张胖子想吃火锅，刘胖子想吃烤肉，剩下的三个员工都没用，也不知道该听谁的了。看到这群效率低下的灯，经理突然想到了一个解决办法，说：“别吵了！我们都是写程序的，我们用算法来解决这个问题吧。”众人一听算法，立马就来了。兴趣：“什么算法？”“就是大名鼎鼎的Paxos，有点复杂，你只要学会就可以了，这次出去吃饭，张胖子和刘胖子不同意，这叫达成共识，这个共识就够了只要超过一半的人同意。”“开始之前，我提几个要求，我们的目的是一起吃晚饭，所以你不能叫小A吃火锅，叫小B吃烤肉，叫小C吃炒菜，我会的你这样乱来，罚款你的工资！”张大胖笑着答应了。“还有你刘胖子，如果小A、小B、小C已经同意张胖子的看法，那你就别写了，别再坚持自己的意见了，跟着吧。”刘胖子也点了点头。.“***小A，小B，小C，你们三个，如果同意一个人的提议，就不要来回忽悠，决定去的餐厅也不要改变！”张大胖五人听到了管事的话。请求，默默记在心里。经理接着说：“具体的算法并不难，就两个阶段：1.为自己拉票的阶段。这个阶段的目的是为了争夺“话语权”。只有当大多数人peopleagreetolistentoyour"speak"canyouenterthenextstageStage2.Confirmationstage:确认去哪家餐厅吃饭经理边说边给出算法的具体步骤，张胖子和刘瘦看的很简单!他迫不及待地开始演奏了。经理暗自一笑：简单！哼！你们两个玩的时候折腾就够了！第一局1、拉票阶段，张胖子比较聪明。当他看到小A、小B、小C三个家伙头发乱糟糟，标准的格子衬衫，我就知道我还没交女朋友。为了让这三个人听他的，张胖子想出了一个主意：听我的提议，我给你们每人介绍一个女孩！小A和小B听了非常高兴。张大哥解决单身问题，听张大哥的！两人同时在小本子上写下：介绍个妹子，我可以答应酒店的求婚！张胖子开心了，他已经这么轻松的赢得了3个人的支持，小A，小B加上我自己（我对自己没有人格分裂），已经占多数了，不管小C同意不同意要不要，我有发言权。2.确定餐厅的张大胖告诉小A小B，我给你们介绍个妹子去吃火锅！小A和小B都赞同，并在本子上写下：介绍一个妹子去吃火锅。张胖子收到结果，知道自己的Paxos算法已经执行完毕，高兴地宣布：“好了，我们达成共识了，我们可以去吃火锅了！”第二局刘胖子傻眼了：“张胖子，你这家伙开的太快了，这样打下去也没意义，不行，我们再打一场！”张大胖道：“没问题，你怕是不会得逞吧？”说着，他赶紧跟小A、小B、小C联络：我给你们介绍个妹子，大家支持一下。小A和小B同意了，在本子上写下：介绍个妹子，我可以从餐厅推荐！结果小C说了一句，张大发，你不是认真的，刘黏糊说给我介绍两个妹子！原来小C早就听刘胖子说了，所以他在书上记起来了：介绍两个妹子，我可以答应餐厅的求婚！张大胖心里说，这刘胖子不傻，就知道这样拉拢人。但是既然小A和小B都同意了他，张胖子就知道他得到了大多数人的同意！尽快告诉他们吃饭的地方，别让这些蠢货跑了！然后他哼着小曲寻找女生的联系方式。找到联系方式后，张胖子进入第二阶段，准备彻底结束酒店纠纷。小A成功答应了吃火锅的提议，并记录下来：介绍妹子吃火锅。没想到的是，小B却背水一战：张胖子，你别认真，刘胖子说给我介绍两个妹子！开始了。增加赌注！给她们一人介绍三个妹子！果不其然，小B那两个傻子又转过身去，乐呵呵地撑着自己。与此同时，刘胖子还自以为“介绍了两个女孩子”得到了大多数人的支持，才可以进入第二阶段确认酒店。可当他联系上小B时，却悲哀地发现张胖子已经抬高了他的筹码（3个女生）。他又把小B带走了！刘胖子飞快的在通讯录里找了找，准备打听更多的联系方式，给四个女孩子介绍一下。张胖子也没闲着，直接进入第二关，顺利确认酒店。至此，张胖子的Paxos算法执行完毕，他知道大部分人都同意吃火锅了。刘胖子又开始拉票，想要夺回优势，却发现小A和小B都接受了吃火锅的提议。他们说：“刘瘦子，我们很想答应你，但是吃火锅的建议，我们已经答应了，也改不了了。不过，为了表示对你的尊重，我们还是决定以后一定要给你介绍吃火锅。”4个妹子。”刘胖子想起之前店长定下的规矩：“如果已经有人接受了餐厅的求婚，就不能再写了，去吃饭吧！”他叹了口气，进入了第二阶段，确认了餐厅的提议，但是他确定“吃火锅”的刘瘦子的Paxos算法也被执行了，最终达成了吃火锅的协议。总结一下，我发现如果你了解BasicPaxos算法，你会觉得很简单，但是很难说清楚你心里想的是什么，因为每个参与者的状态都在不断变化，细节太多，分支太多。所以我通过这个小游戏描述了BasicPaxos算法。说实话不是很严谨，比如小A、小B、小C如果收到Acceptwithmore"bribes"，虽然餐厅已经确认，但还是可以修改的。是的，这个没说在游戏中。这个游戏展示了典??型的情况遭遇执行时红色。完整算法见文章***部分。在BasicPaxos算法中，有两个最重要的角色：Proposer：张胖子和刘胖子Acceptor：小A，小B，小C，包括大胖子张和刘胖子，可以扮演多个角色。游戏中的“介绍n个女孩”，在Paxos算法中，是一个数字n。在BasicPaxos的两阶段协议中，Proposer在第一阶段向其他人发送Prepare(n)，试图获得“话语权”。这里的prepare(n)相当于“介绍n个女孩”。第二阶段发送Accept(n,v)尝试判断结果，这里n还是“介绍n个妹子”，v是吃火锅或者烧烤。由于有多个Proposer，可以发送Prepare(n)。这时候Acceptor需要根据n的大小来决定听谁的。所以会像小B一样在墙上长草，来回摆动。Proposer在第一阶段得到大多数人的支持后，会进入第二阶段，向其他人发送Accept(n,v)消息。某位Acceptor，比如小B，收到了张大胖的Accept(3，火锅)，并记录了吃火锅。这时候即使收到的消息是prepare(4)，数量也比较大。他告诉刘胖子，我决定选择火锅了。这个时候关键是刘胖子要跟着，不要硬要自己烤肉。一个有趣的问题，聪明的你可能已经看到了：如果张胖子和刘胖子交替争夺话语权，比如：张胖子介绍1个妹子赢小A，刘瘦介绍2个妹子赢小A赢了小B，B，小C张大发介绍了3个妹子，赢了小A，小B刘瘦子介绍了4个妹子，赢了小B，小C……这样，谁也进不了第二阶段，算法永远不完整。一种解决方案是让他们在开始新一轮之前随机等待一段时间。让其他人有机会研究该算法。算法贴出了详细的算法，有兴趣的可以仔细研究一下。算法来自：https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pptx我觉得这个PPT还是挺不错的。【本文为专栏作家“刘欣”原创稿件，转载请通过作者微信获取授权公众号coderising】点此查看该作者更多好文
