微信号:TheAlgorithm

介绍:算法与数据结构知识、资源分享

码农们的聚餐,会复杂到什么程度?

2019-04-08 20:50 王卓

来自:码农翻身(微信号:coderising)


本文来自王卓的投稿,老刘做了修改。


王卓是北京邮电大学硕士,研究方向为区块链技术、共识算法及零知识证明,对区块链技术底层有较深的理解。

张大胖的部门连续加班三个月,系统终于上线了!


经理打算组织一次部门聚餐, 犒劳一下大家。至于去哪家饭店,就留给大家来讨论了。


没想到的是,这一伙人争得不可开交,谁都说不过谁,其中,争吵得最凶的是张大胖和刘瘦子,张大胖想去吃火锅, 刘瘦子想去吃烧烤, 剩下三个员工是墙头草, 也不知道听谁的。


经理看到这一群不省油的灯,突然想到一个办法,说到:“别吵了!咱们都是写程序的,用一个算法来解决这个问题吧。”


大家听到算法,一下子就来了兴致:“什么算法?”


“就是大名鼎鼎的Paxos啊,它有点儿复杂,大家正好学习一下。 这次咱们要出去聚餐,但是张大胖和刘瘦子的意见不统一,我们最终还是要选一家,这叫达成共识。这个共识啊只要有超过半数的人同意就可以了。”


“在开始之前,我先说几个要求, 咱们的目的是一起去吃饭,所以张大胖你不能给小A说去吃火锅,给小B说去吃烧烤,又给小C说去吃料理。你这样来回捣乱我可要罚你工资了!”


张大胖嘿嘿笑着同意。


“还有你,刘瘦子,如果小A,小B或者小C已经有人同意张大胖的意见了,你就别墨迹,别再坚持你的意见,跟着去吃就好了。”


刘瘦子也点头。


“最后小A,小B,小C你们仨,你们同意了一个人的提议就别来回当墙头草,确定吃哪个饭店就不要改啦!”


张大胖他们五个人听到经理讲了这些要求,默默记在心里。


经理接着说:“具体的算法也不难,就两个阶段:


1.给自己拉票阶段,这一阶段的目的是争夺“发言权”,只有多数人同意听你“发言”,才能进入下一阶段


2.确认阶段:确定去那个饭店吃饭。


经理一边说,一边给出了算法具体的步骤,张大胖刘瘦子一看,很简单啊!迫不及待地就开始玩起来了。


经理心里偷偷地笑了:简单!哼!等玩起来了够你俩折腾的!


第一次游戏


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给拉走了!


刘瘦子赶紧查找通信录,准备找出更多联系方式,给他们介绍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  我觉得这个PPT讲得还是比较好的。




●编号887,输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

程序员求职面试

更多推荐25个技术类公众微信

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

 
算法与数据结构 更多文章 2019年ACM程序设计大赛结果出炉,北大清华无缘前十,莫斯科大学第一 2019年3月份GitHub上最热门的开源项目 六千字干货文:到底要怎么去学算法? PNG 图片压缩原理解析 我在GitHub上找到了北大的计算机课程资料
猜您喜欢 在新加坡做运维是什么体验 新技能Get!如何速成数据分析师 程序员保护守则 | 新的一年让头发茁长成长 Vim Python大杀器 最新调查结果:68%的受访者认为OpenStack对OPNFV的成功非常重要