码农们的聚餐，会复杂到什么程度？
作者丨王卓
责编 | 仲培艺
本文经授权转载自码农翻身（ ID：coderising）
张大胖的部门连续加班三个月，系统终于上线了！
经理打算组织一次部门聚餐， 犒劳一下大家。至于去哪家饭店，就留给大家来讨论了。
没想到的是，这一伙人争得不可开交，谁都说不过谁，其中，争吵得最凶的是张大胖和刘瘦子，张大胖想去吃火锅， 刘瘦子想去吃烧烤， 剩下三个员工是墙头草， 也不知道听谁的。
经理看到这一群不省油的灯，突然想到一个办法，说道：“别吵了！咱们都是写程序的，用一个算法来解决这个问题吧。”
大家听到算法，一下子就来了兴致：“什么算法？”
“就是大名鼎鼎的 Paxos 啊，它有点儿复杂，大家正好学习一下。 这次咱们要出去聚餐，但是张大胖和刘瘦子的意见不统一，我们最终还是要选一家，这叫达成共识。这个共识啊只要有超过半数的人同意就可以了。”
“在开始之前，我先说几个要求， 咱们的目的是一起去吃饭，所以张大胖你不能给小 A 说去吃火锅，给小 B 说去吃烧烤，又给小 C 说去吃料理。你这样来回捣乱我可要罚你工资了！”
张大胖嘿嘿笑着同意。
“还有你，刘瘦子，如果小 A，小 B 或者小 C 已经有人同意张大胖的意见了，你就别墨迹，别再坚持你的意见，跟着去吃就好了。”
刘瘦子也点头。
“最后小 A、小 B、小 C 你们仨，同意了一个人的提议就别来回当墙头草，确定吃哪个饭店就不要改啦！”
张大胖他们五个人听到经理讲了这些要求，默默记在心里。
经理接着说：“具体的算法也不难，就两个阶段：
1. 给自己拉票阶段，这一阶段的目的是争夺“发言权”，只有多数人同意听你“发言”，才能进入下一阶段；
2. 确认阶段：确定去哪个饭店吃饭。
经理一边说，一边给出了算法具体的步骤，张大胖刘瘦子一看，很简单啊！迫不及待地就开始玩起来了。
经理心里偷偷地笑了：简单！哼！等玩起来了够你俩折腾的！
第一次游戏
拉票阶段
张大胖人比较聪明，看到小 A、小 B、小 C这三个家伙头发乱糟糟的，以及标配的格子衬衫，一想就知道还没有女朋友。
为了让这三个人听自己的，张大胖想出来一个点子：听我的提议，我给你们每人介绍一位女生！
小 A、小 B 听到了，非常高兴，张大哥解决单身问题，听张大哥的！
与此同时，他俩在小本子上记下：介绍一位女生， 我可以同意饭店提议！
张大胖乐了，自己这么轻松已经取得 3 个人的支持，小 A、小 B 加上自己（我自己不会人格分裂反对我自己）， 已经是多数派了，不管小 C 是否同意， 我都有了发言权了。
确定饭店
张大胖给小 A、小 B 说， 我给你们介绍一位女生，去吃火锅！
小 A、小 B 都表示同意，在小本子上记下： 介绍一位女生，去吃火锅。
张大胖收到结果，知道自己的 Paxos 算法已经执行完毕， 高兴地宣布：“行了，我们已经达成了共识，可以去吃火锅了! ”
第二次游戏
刘瘦子傻眼了：“张大胖你这家伙下手太快了，你这样搞，一点意思都没有啊， 不行，我们再玩一次！”
张大胖说：“没问题， 我还怕你不成？”
话虽这么说，他赶紧和小 A、小 B、小 C 联系：给你们介绍一位女生，要支持我啊。
小 A、小 B 表示同意，在本子上记下：介绍一位女生， 我可以同意饭店提议！
结果小 C 说了句，张大胖，你不实在哈，刘瘦子说给我介绍俩女生呢！
原来小 C 由于已经听了刘瘦子的话了，本子记得是：介绍两位女生，我可以同意饭店提议！
张大胖心说，这刘瘦子也不笨嘛，也知道用这种方式来拉拢人。
不过既然有小 A、小 B 答应自己，张大胖知道自己有了多数派的同意！
自己赶快给他们说去哪吃就行，别让这几个墙头草跑了！然后哼着小曲儿去找女生联系方式了。
找到联系方式以后，张大胖进入第二阶段，准备彻底终结这次饭店之争。
小 A 顺利地同意了吃火锅的提议，记录了下来：介绍一位女生，去吃火锅。
没想到的是，小 B 已经反水了：张大胖，你不实在哈，刘瘦子说给我介绍俩女生呢！
张大胖心想，真是墙头草，看来只好从第一阶段的拉票重新开始了。
加大筹码！给他们每人介绍三位女生！果然，小 A、小 B 这两个墙头草再次反水，欢天喜地支持自己了。
与此同时， 刘瘦子美滋滋地以为，自己用“介绍两位女生”获得了多数派的支持，可以进入第二阶段，去确定饭店。
可是他和小 B 联系的时候，悲催地发现，张大胖已经提高了筹码（3 位女生）。又把小 B 给拉走了！
刘瘦子赶紧查找通信录，准备找出更多联系方式，给他们介绍 4 位女生。
张大胖可没有闲着，马上进入第二阶段，成功地确定了饭店。
至此，张大胖的 Paxos 算法执行完毕，他知道大多数人已经同意去吃火锅了。
刘瘦子再次发起拉票，试图重新占据优势，可是他发现小 A 和小 B 已经接受了吃火锅的提议。
他们说：“刘瘦子，我们很想答应你，可是，我们已经答应吃火锅的建议了，不能再变了，但是，为了表示对您的尊重，我们以后就认定确定吃火锅是得给我们介绍 4 位女生。”
刘瘦子想到经理之前定的规则：“如果已经有人接受过了饭店的提议，不能再墨迹了，跟着去吃就行了！”
他叹了口气，进入了第二阶段，确定饭店，不过他确定的也是“吃火锅”
刘瘦子的 Paxos 算法也执行完了， 最终达成了一致，去吃火锅。
总结
我发现对于这个 Basic Paxos 算法，你要是理解了，会发现很简单，但是想把脑子中的东西描述出来，却很难，因为每个参与者的状态都在不断地变化中，细节太多，分支太多。
所以就通过这个小游戏讲述了 Basic Paxos 算法，说实话，不太严谨，比如小 A、小 B、小 C 如果收到了带着更多“贿赂”的 Accept，虽然已经确定了饭店，还是可以修改的，这一点在游戏中就没提。
这个游戏展示了执行过程遇到的典型情况。 完整的算法参见文章的最后部分。
在 Basic Paxos 算法中，有两个角色最为重要：
Proposer：即张大胖和刘瘦子
Acceptor：小 A、小 B、小 C， 也包括张大胖和刘瘦子
一个人可以身兼多个角色。
游戏中的“介绍 n 位女生”，在 Paxos 算法中，就是一个数字 n。
在 Basic Paxos 这个两阶段的协议中，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、小 B
刘瘦子介绍 2 位女生，争取了小 B、小 C
张大胖介绍 3 位女生，又争取了小 A、小 B
刘瘦子介绍 4 位女生，又争取了小 B、小 C
……
这样一来，无论是谁都无法进入第二阶段，算法永远无法完成。
一种解决办法就是，可以让他们开始新一轮争取的时候，等待一个随机的时间。让其他人有机会去完成这个算法。
算法
贴一张详细的算法，有兴趣的可以仔细研究一下。
算法来自于：https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pptx
作者：王卓是北京邮电大学硕士，研究方向为区块链技术、共识算法及零知识证明，对区块链技术底层有较深的理解。
声明：本文经授权转载自码农翻身，如需转载请联系原作者。
【END】
作为码一代，想教码二代却无从下手：
听说少儿编程很火，可它有哪些好处呢？
孩子多大开始学习比较好呢？又该如何学习呢？
最新的编程教育政策又有哪些呢？
下面给大家介绍CSDN新成员：极客宝宝（ID：geek_baby）
戳他了解更多↓↓↓
热 文 推 荐
☞ 全方位测评Hive、SparkSQL、Presto 等七个大数据查询引擎，最快的竟是……| 程序员硬核测评
☞厉害了！超越 Google，16 岁少女发明眼疾诊断 AI 模型！
☞ 和 996 对着干的百亿巨头：不打卡，不设 KPI，福利好到爆，却称霸行业 20 年！
☞ 回报率29%! 大神用情感分析创建一个比特币交易算法, 原来交易玩的是心理战
☞ 她说：为啥程序员都特想要机械键盘？这答案我服！
System.out.println("点个在看吧！");
console.log("点个在看吧！");
print("点个在看吧！");
printf("点个在看吧！\n");
cout << "点个在看吧！" << endl;
Console.WriteLine("点个在看吧！");
Response.Write("点个在看吧！");
alert("点个在看吧！")
echo "点个在看吧！"
相关内容
微信扫码咨询专知VIP会员