我們必須研究分布式，因?yàn)楝F(xiàn)實(shí)世界就是這個(gè)樣子

初識(shí)計(jì)算機(jī)

2013 年萊斯利蘭伯特獲得圖靈獎(jiǎng)，此時(shí)他 72 歲，距離他 1978 年發(fā)表 “時(shí)間主籍、時(shí)鐘及分布式系統(tǒng)中事件的順序” 一文，已過(guò)去 35 年逛球。在此之前千元，人們便奇怪為何蘭伯特?zé)o緣圖靈獎(jiǎng)，有人認(rèn)為他批評(píng)別人過(guò)于尖銳需忿，所以人緣不佳诅炉。這些討論無(wú)疑佐證了他的圖靈獎(jiǎng)確乎名至實(shí)歸。

獲獎(jiǎng)儀式上屋厘，他要做一個(gè)演講涕烧，蘭伯特身著體恤衫和短褲上臺(tái)，他一頭灰白長(zhǎng)發(fā)汗洒，蓬蓬松松的和滿腮的灰白胡須連在一起议纯，看上去更像一個(gè)電影導(dǎo)演，而不像一個(gè)科學(xué)大師溢谤。圖靈獎(jiǎng)的授獎(jiǎng)儀式瞻凤，沒(méi)有奧斯卡的珠光寶氣憨攒，也沒(méi)有諾貝爾獎(jiǎng)那么嚴(yán)肅，就是一個(gè)簡(jiǎn)單的學(xué)術(shù)交流會(huì)阀参。 蘭伯特用 PPT 介紹了并發(fā)系統(tǒng)研究上的歷史肝集，他幽了一默：“你們表?yè)P(yáng)我發(fā)明了因果關(guān)系，難道在之前蛛壳，因果關(guān)系不存在杏瞻？”

蘭伯特的獲獎(jiǎng)介紹是這樣寫(xiě)的：“他對(duì)分布式和并發(fā)系統(tǒng)的理論及實(shí)踐，做出了重大貢獻(xiàn)衙荐，尤其是他提出了諸多的概念捞挥，例如 ‘因果關(guān)系和邏輯時(shí)鐘’、‘安全性和活性’忧吟、‘復(fù)制狀態(tài)機(jī)’砌函，還有‘順序一致性’×镒澹”

蘭伯特是紐約人讹俊，1954 年他入學(xué)就讀 “Bronx 科學(xué)高中”，這所學(xué)校非常厲害斩祭，學(xué)生們都是天才劣像，每年從 2 萬(wàn)報(bào)考生中選取不到 1 千人入學(xué)。學(xué)校在全美高中的綜合實(shí)力排名 30摧玫，但在另一個(gè)排名上這學(xué)校全球第一，那就是諾貝爾獎(jiǎng)得主人數(shù)绑青。該校共計(jì)有 8 名學(xué)生是諾貝爾獎(jiǎng)得主诬像，若將該校視作國(guó)家，也能在這個(gè)榜單上排名全球第 23闸婴。

高中畢業(yè)后坏挠，他進(jìn)入麻省理工，讀數(shù)學(xué)專業(yè)邪乍，并于 1960 年獲得學(xué)士學(xué)位降狠。麻省理工不必多說(shuō)，工程和計(jì)算機(jī)學(xué)科排名全球一二庇楞，諾貝爾得獎(jiǎng)人數(shù) 93榜配。他的碩士學(xué)位和博士學(xué)位，分別獲得于 1963 年和 1972 年吕晌，都是在一所叫布蘭迪斯的大學(xué)蛋褥，這所學(xué)校是猶太人社群在美國(guó)建的第一所大學(xué)，建校初期睛驳，愛(ài)因斯坦還曾為該欣有模籌過(guò)款膜廊。

大約就在?“Bronx 科學(xué)高中”，蘭伯特開(kāi)始對(duì)計(jì)算機(jī)感興趣淫茵，甚至曾嘗試自己做一臺(tái)計(jì)算機(jī)爪瓜，為此他自己學(xué)習(xí)了布爾代數(shù)，并研究電腦電路匙瘪。美國(guó)的科技界一貫對(duì)青少年很友好铆铆，HP 給了喬布斯電腦零件，而蘭伯特則參觀了 IBM 在紐約的實(shí)驗(yàn)室辆苔，還帶走了一些真空管算灸。蘭伯特和一個(gè)小伙伴，就用這些真空管做了一個(gè) 4 位的計(jì)數(shù)器驻啤。

高中畢業(yè)后菲驴，蘭伯特才有機(jī)會(huì)碰到真正的計(jì)算機(jī)。那是一個(gè)暑期社會(huì)活動(dòng)骑冗，蘭伯特得到了一個(gè)工作機(jī)會(huì)赊瞬，到愛(ài)迪生聯(lián)合電氣在紐約的供電公司工作。那工作最初是很無(wú)聊的贼涩，后來(lái)蘭伯特聽(tīng)說(shuō)公司里有電腦巧涧，就跑去電腦中心，求人家給他轉(zhuǎn)崗遥倦，他成功了谤绳。之后，他就在電腦中心給一臺(tái) IBM 705 裝卸 “磁帶” 和 “紙帶”袒哥。 IBM 705 在當(dāng)時(shí)可是最強(qiáng)大的計(jì)算機(jī)了缩筛，60 秒內(nèi)可做 24 萬(wàn)次運(yùn)算。蘭伯特一邊干粗活打雜堡称，一邊偷偷學(xué)藝瞎抛。就是在這里，他學(xué)會(huì)了編程却紧。他的第一個(gè)程序桐臊，是用 IBM 705 計(jì)算 “e” 為一個(gè) 125 位的十進(jìn)制數(shù)字。等到他念了大學(xué)晓殊，放暑假了断凶，他還到供電公司來(lái)工作，但他的崗位已經(jīng)是程序員了挺物。

蘭伯特在高中時(shí)懒浮，數(shù)學(xué)就很優(yōu)秀。但進(jìn)入麻省理工大學(xué)后，他的專業(yè)最初是物理砚著，當(dāng)時(shí)他覺(jué)得學(xué)物理更好找工作次伶，而學(xué)數(shù)學(xué)唯一的出路似乎就是當(dāng)老師。然而稽穆，第二年冠王，他從物理專業(yè)轉(zhuǎn)到了數(shù)學(xué)專業(yè)，原因呢舌镶，據(jù)他說(shuō)柱彻，是數(shù)學(xué)專業(yè)不需要寫(xiě)論文就能畢業(yè)。

在蘭伯特早期的求學(xué)和工作生涯中餐胀，物理哟楷、數(shù)學(xué)和計(jì)算機(jī)都已涉及。但直到很久之后否灾，蘭伯特才意識(shí)到自己也許工作在一個(gè)叫做 “計(jì)算機(jī)科學(xué)” 的領(lǐng)域卖擅，畢竟，那時(shí)候計(jì)算機(jī)才剛剛出現(xiàn)墨技，在人們的認(rèn)知中惩阶，計(jì)算機(jī)只是算盤(pán)一樣的工具，甚至在科學(xué)家眼中也是如此扣汪。壓根就沒(méi)有一個(gè)叫計(jì)算機(jī)的學(xué)科吠卷，這和沒(méi)有吸塵器學(xué)科是一個(gè)道理岖瑰。

早年間，蘭伯特曾經(jīng)研究哈希表技術(shù)杏慰，當(dāng)他正在搞這個(gè)的時(shí)候搔谴，有人在 CACM 上發(fā)表了一篇針對(duì)哈希表的研究文章大州。蘭伯特看出那篇文章中的成果還有改進(jìn)的必要窄绒，他寫(xiě)了篇評(píng)論汞贸，發(fā)給了 CACM，告訴編輯暗膜，他發(fā)現(xiàn)了還有三種變形算法，而該文中并未提及鞭衩。然而遺憾的是学搜，編輯退了他的稿，認(rèn)為他的主意沒(méi)有價(jià)值论衍。 更遺憾的是瑞佩，過(guò)了幾年，蘭伯特發(fā)現(xiàn)坯台，他所建議的三種變形算法中的兩種炬丸，分別在 CACM 上發(fā)表。

這個(gè)退稿事件在蘭伯特的心中產(chǎn)生了兩個(gè)結(jié)果，一個(gè)是稠炬，他覺(jué)得也許自己真的是一位計(jì)算機(jī)科學(xué)家了焕阿；另一個(gè)是，科技期刊的編輯們首启，未必都靠譜暮屡。而蘭伯特與期刊編輯們的爭(zhēng)論，在蘭伯特的學(xué)術(shù)生涯中毅桃，這并非最后一次.......

蘭伯特在讀博士期間褒纲，為了掙學(xué)費(fèi)和生活費(fèi)，在一位教授的推薦下钥飞，從 “馬薩諸塞計(jì)算機(jī)聯(lián)盟” 找到了一個(gè)職位莺掠。?

“馬薩諸塞計(jì)算機(jī)聯(lián)盟” 又稱之為 COMPASS，在當(dāng)時(shí)相當(dāng)有名氣读宙，該公司的雇員中頗多計(jì)算機(jī)大牛彻秆，包括另一位圖靈獎(jiǎng)獲得者 - 羅伯特弗洛伊德，還有 Stephen Warshall 和?Michael J. Fischer论悴，這兩位雖然并非圖靈獎(jiǎng)得主掖棉，但都在計(jì)算機(jī)科學(xué)上做出了卓越貢獻(xiàn)。Fischer 有眾多學(xué)生后來(lái)都成了大牛膀估，其中有一位女學(xué)生是華人幔亥，名叫姚儲(chǔ)楓，她的丈夫就是圖靈獎(jiǎng)得主中唯一的華人姚期智教授察纯。

蘭伯特博士畢業(yè)后帕棉，原準(zhǔn)備去科羅拉多大學(xué)教書(shū)的，這是中規(guī)中矩的道路饼记，他本來(lái)以為學(xué)數(shù)學(xué)的出路就是教書(shū)香伴。然而，COMPASS 公司問(wèn)他：“我們正計(jì)劃在加州搞個(gè)新辦公室具则，要不你到加州去即纲？ 繼續(xù)為我們工作如何？” 蘭伯特想了下博肋，點(diǎn)頭了低斋。 正當(dāng)蘭伯特準(zhǔn)備動(dòng)身去加州，COMPASS 又找他匪凡，有點(diǎn)不好意思膊畴，問(wèn)他：“加州新辦公室的計(jì)劃要黃，不過(guò)沒(méi)事病游，你還是去加州唇跨，繼續(xù)為我們工作如何？” 就是說(shuō)，蘭伯特可以不用去辦公室上班了买猖。蘭伯特想了下改橘，又點(diǎn)頭了。之后的五年政勃，蘭伯特就在加州工作唧龄，自由自在，不用去辦公室奸远，當(dāng)然也沒(méi)有辦公室既棺，每年回一趟波士頓總部交差就行。

COMPASS 公司的主要產(chǎn)品是 FORTURN 編譯器懒叛，偶爾也從國(guó)防部接一點(diǎn)外包合同丸冕。蘭伯特在 COMPASS 的一個(gè)項(xiàng)目，是為?Foxboro 公司制造的電腦設(shè)計(jì)文件系統(tǒng)薛窥。這個(gè)項(xiàng)目胖烛，是蘭伯特初次接觸并發(fā)系統(tǒng)。蘭伯特接到這個(gè)項(xiàng)目時(shí)诅迷，還在馬薩諸塞佩番，并未去加州。其時(shí)罢杉，他的一個(gè)朋友邀請(qǐng)他去新墨西哥呆上一兩個(gè)月趟畏，度度假，這個(gè)朋友在那里有一個(gè)莊園滩租。而 COMPASS 也就同意了赋秀。

當(dāng)然蘭伯特并非真的度假，他去了新墨西哥后律想，很快便寫(xiě)出了一本厚厚的“書(shū)”猎莲，完成了那個(gè)項(xiàng)目。蘭伯特的這本“書(shū)”技即，之后就成了工程人員開(kāi)發(fā) “編譯器” 的圣經(jīng)著洼。而 COMPASS 經(jīng)此項(xiàng)目，對(duì)蘭伯特徹底放心了而叼，這是個(gè)不需要監(jiān)控的員工郭脂，他去那里工作都一樣。這才安排蘭伯特只身去往加州澈歉。從此，蘭伯特在 COMPASS 不僅擁有不去辦公室的自由屿衅，還有了可以自己選題的自由埃难，COMPASS 則不斷從政府那里簽一些合同交給蘭伯特，也就罩住了他的費(fèi)用，COMPASS一點(diǎn)都不虧涡尘。

蘭伯特到了加州忍弛，僅僅 6 個(gè)月后，面包店算法面世考抄。

面包店算法

蘭伯特加入 COMPASS 的同時(shí)细疚，也成為了 CACM 的會(huì)員。這里要先介紹下 ACM川梅，ACM 翻譯成中文是 “國(guó)際計(jì)算機(jī)協(xié)會(huì)”疯兼，這是計(jì)算機(jī)領(lǐng)域全球最權(quán)威，影響力最大的組織贫途。圖靈獎(jiǎng)就是 ACM 設(shè)立的一個(gè)獎(jiǎng)項(xiàng)吧彪。 CACM 則可以翻譯成 “ACM 通訊”，是 ACM 旗下的一份期刊丢早。蘭伯特博士畢業(yè)于 1972 年姨裸，同年成為 CACM 會(huì)員。CACM 是月刊怨酝，每月都會(huì)寄送給所有會(huì)員傀缩。

蘭伯特在 CACM 上讀到一篇文章，介紹進(jìn)程互斥（mutual exclusion）算法农猬。他心想赡艰，咦，我可以發(fā)明更簡(jiǎn)單的算法啊盛险。于是瞄摊，他就寫(xiě)了篇文章，寄給了 CACM 的編輯苦掘，編輯很痛快的給他退了稿换帜，并指出其中有個(gè) Bug。這給了蘭伯特一個(gè)打擊鹤啡，也給了他兩個(gè)教訓(xùn)惯驼。第一個(gè)教訓(xùn)是，并發(fā)問(wèn)題是很難的递瑰；第二個(gè)教訓(xùn)是祟牲，任何算法都要有嚴(yán)謹(jǐn)?shù)淖C明。 蘭伯特知恥后勇抖部，發(fā)誓一定要解決這個(gè)問(wèn)題说贝，很快他就寫(xiě)出了新論文，順利發(fā)表慎颗，且這篇論文折服了很多人乡恕，之前大家都不大相信不依賴底層互斥居然能實(shí)現(xiàn)多線程并發(fā)問(wèn)題言询。

并發(fā)系統(tǒng)與互斥問(wèn)題的提出，源自艾茲格·W·迪科斯徹（?Edsger W. Dijkstra）傲宜，這是大神級(jí)的計(jì)算機(jī)科學(xué)家运杭，早在1972 年便獲得圖靈獎(jiǎng)。迪科斯徹是并發(fā)系統(tǒng)函卒、分布式系統(tǒng)的鼻祖辆憔。1965 年他在 CACM 上發(fā)表的短文 “并行程序的控制”，拉開(kāi)了一場(chǎng)關(guān)于并行系統(tǒng)研究的大幕报嵌，該文深刻影響了現(xiàn)代操作系統(tǒng)虱咧、程序語(yǔ)言的設(shè)計(jì)思路。

迪科斯徹提出“進(jìn)程互斥”問(wèn)題沪蓬，所用的場(chǎng)景是哲學(xué)家聚餐彤钟。一群哲學(xué)家共 5 人湊一起圍著圓桌吃飯，每位哲學(xué)家的左右各有一把叉子跷叉，拿起兩把筷子就能用餐逸雹。但若是五位哲學(xué)家同時(shí)拿起自己左邊的叉子，那么他們都沒(méi)了右邊的叉子云挟，就此進(jìn)入“死鎖”狀態(tài)梆砸。計(jì)算機(jī)中“死鎖”這個(gè)詞是迪科斯徹發(fā)明的。迪科斯徹的解決方案中引入了 “信號(hào)量” （semaphore）概念园欣，如同一個(gè)服務(wù)生一樣帖世，協(xié)調(diào)這些哲學(xué)家們。

而蘭伯特在街道上溜達(dá)的時(shí)候沸枯，觀察到面包店里的生意很紅火日矫，收銀員忙碌應(yīng)付擁擠的顧客，他靈光一閃绑榴，設(shè)計(jì)出了面包店算法哪轿。 目的是設(shè)計(jì)一個(gè)規(guī)則，保證收銀員一次只服務(wù)一個(gè)顧客翔怎，從而不至于在兩位或多位顧客的七嘴八舌中暈死窃诉。蘭伯特讓每位顧客進(jìn)入面包店后，自行取一個(gè)號(hào)碼赤套，然后根據(jù)這個(gè)號(hào)碼的大小排隊(duì)飘痛。這思想中的創(chuàng)新在于，蘭伯特并不需要安排一個(gè)單獨(dú)的店員負(fù)責(zé)發(fā)放號(hào)碼容握，而是讓新來(lái)顧客們打聽(tīng)其他顧客的號(hào)碼宣脉，然后自己發(fā)一個(gè)號(hào)碼給自己，只要這個(gè)號(hào)碼大于其他人的即可剔氏。

面包店算法一出脖旱，給并行系統(tǒng)的設(shè)計(jì)堪遂，提供了一條嶄新的思路，之后千樹(shù)萬(wàn)樹(shù)梨花開(kāi)萌庆，涌現(xiàn)出很多并行算法來(lái)。蘭伯特在計(jì)算機(jī)上成功碩碩币旧，但他最驕傲的践险，還是面包店算法。按照他的解釋吹菱，別的成果都有祖先巍虫，多少都要受他人的啟發(fā)和影響，獨(dú)有面包店算法是徹頭徹尾的原創(chuàng)鳍刷，仿佛是從空氣中擒獲的星星占遥。

1977 年蘭伯特離開(kāi)了 COMPASS，原因很簡(jiǎn)單输瓜，COMPASS 突然要求他回到馬薩諸塞瓦胎，而蘭伯特不想離開(kāi)加州。蘭伯特接受了來(lái)自 SRI 的職位尤揣，那時(shí)候搔啊，似乎只有 SRI 和施樂(lè) PARC 兩家才有計(jì)算機(jī)科學(xué)研究，但施樂(lè)不給蘭伯特機(jī)會(huì)......

SRI 是 “斯坦福研究院” 的簡(jiǎn)寫(xiě)北戏，由斯坦福大學(xué)發(fā)起并成立的研究機(jī)構(gòu)负芋，1977 年從斯坦福大學(xué)獨(dú)立出來(lái)。據(jù) 2015 年數(shù)據(jù)嗜愈， SRI 有 2100 名雇員旧蛾，收入 5 億多美元。

SRI 之所以雇傭蘭伯特蠕嫁，是為了一個(gè) NASA 的合同锨天，NASA 委托 SRI 為飛機(jī)開(kāi)發(fā)一個(gè)容錯(cuò)電腦系統(tǒng)。這個(gè)項(xiàng)目叫做 SIFT拌阴。其背景是 70 年代的石油危機(jī)绍绘，航空公司和飛機(jī)制造商都希望飛機(jī)更省油，而設(shè)計(jì)一套系統(tǒng)能夠提升飛機(jī)的穩(wěn)定性迟赃，減少摩擦力陪拘，更省油似乎是可能的。SIFT 就是用來(lái)控制飛機(jī)的穩(wěn)定系統(tǒng)纤壁。SIFT 的另外一個(gè)目的是提高戰(zhàn)斗機(jī)的操控性能左刽。這個(gè)項(xiàng)目就引出了著名的“拜占庭將軍問(wèn)題”。

拜占庭吉將軍問(wèn)題

SIFT 項(xiàng)目所面臨的一個(gè)難題是酌媒，要在多個(gè)不可靠的處理器之間達(dá)成協(xié)議上的一致欠痴。這個(gè)難題最終由蘭伯特和 Rob Shostak迄靠、Marshall Pease 三人一起搞定，所以論文上喇辽，也就簽署了三人之名掌挚。實(shí)情是，雖然蘭伯特排名第一作者菩咨，但他是后來(lái)者吠式，而 Rob Shostak 和 Marshall Pease 二人的研究更早，且已有了成果抽米。?Shostak 提出最少必須有 4 個(gè)處理器特占，Pease 則從數(shù)學(xué)上論證了 3n+1 的邏輯，即失效處理器的個(gè)數(shù)云茸，必須小于總數(shù)的三分之一是目。

在進(jìn)入 SIFT 項(xiàng)目之前，蘭伯特已經(jīng)開(kāi)始思考計(jì)算機(jī)上的 “任意失效” 問(wèn)題标捺。之前人們所應(yīng)對(duì)的多是 “故障”懊纳，也就是設(shè)備奔潰宕機(jī)，無(wú)應(yīng)答宜岛。而 “任意失效”长踊，則意味著設(shè)備可能發(fā)出故意擾亂分布式計(jì)算的錯(cuò)誤指令∑汲“任意失效” 后來(lái)被稱為 “拜占庭故障”身弊，是計(jì)算機(jī)中所能發(fā)生的最壞的故障。用團(tuán)隊(duì)合作來(lái)比喻列敲，隊(duì)友死了或者偷懶不干活并非最壞的情況阱佛，豬隊(duì)友拖后腿，搗亂戴而，叛變才是最大的麻煩凑术。1977 年，蘭伯特就寫(xiě)過(guò)一篇文章所意，用狀態(tài)機(jī)來(lái)克服 “任意失效” 類型的故障淮逊，在該文中，蘭伯特使用了數(shù)字簽名扶踊，也就是非對(duì)稱加密算法的簽名技術(shù)泄鹏。

蘭伯特專攻并發(fā)系統(tǒng)和分布式，而數(shù)字簽名是密碼學(xué)領(lǐng)域秧耗，原本二者并無(wú)關(guān)聯(lián)备籽。但無(wú)巧不成書(shū)，蘭伯特居然有位好朋友名叫懷特菲爾德·迪菲分井！ 又一位圖靈獎(jiǎng)獲得者车猬，且是非對(duì)稱加密算法的鼻祖霉猛。真是英雄風(fēng)云際會(huì)啊珠闰！ 1974 年惜浅，蘭伯特和迪菲在咖啡館里閑坐，迪菲就絮叨自己的研究伏嗜，說(shuō)起了設(shè)計(jì)一個(gè)單向算法是多么困難赡矢。蘭伯特聽(tīng)了，想了想阅仔，說(shuō)這不難吧，隨手在餐巾紙上寫(xiě)了一點(diǎn)子公式弧械。蘭伯特寫(xiě)的數(shù)學(xué)公式八酒，后來(lái)就被迪菲與赫爾曼寫(xiě)入 “加密學(xué)的新方向” 一文 - 該文當(dāng)是密碼學(xué)領(lǐng)域開(kāi)天辟地的文章 - 文中也就列出了蘭伯特，算是蘭伯特做出了貢獻(xiàn)刃唐。當(dāng)然到了 2009 年羞迷，非對(duì)稱加密和分布式系統(tǒng)再次走到一起，親密接觸画饥，生出了比特幣和區(qū)塊鏈衔瓮，那是后話了。

迪菲在科技學(xué)術(shù)界一向以自由奔放的性情受人敬仰抖甘，迪菲自稱 “離經(jīng)叛道者”热鞍。蘭伯特也是自由自在的散仙形象，這兩位大師做朋友衔彻，只能說(shuō)友誼的小船天注定薇宠。看看下面的照片艰额，二人的面相氣質(zhì)是不是頗為相近那澄港。

分布式系統(tǒng)與非對(duì)稱加密算法的首次接觸，就是 1977 年蘭伯特的這篇論文柄沮。而在與?Rob Shostak回梧、Marshall Pease 兩人合作的 “拜占庭將軍問(wèn)題” 一文中，蘭伯特的貢獻(xiàn)是數(shù)字簽名共識(shí)算法祖搓，在文中叫 “書(shū)面協(xié)議”狱意。另外，Pease 設(shè)計(jì)的算法非常難懂棕硫，是蘭伯特在最終版本中髓涯，改寫(xiě)成了現(xiàn)在這一版易懂的算法，也就是用了遞歸算法的 “口頭協(xié)議”哈扮。

簡(jiǎn)單說(shuō)說(shuō) “拜占庭將軍問(wèn)題”纬纪，10 位將軍圍城蚓再，只能通過(guò)信使送信，需要就進(jìn)攻還是撤退達(dá)成一致包各，那么如何設(shè)計(jì)算法摘仅？ 其中還有一個(gè)大麻煩是，將軍中可能存在奸細(xì)问畅，這奸細(xì)將軍就是前述的 “任意失效” 類型的故障娃属，奸細(xì)將軍會(huì)發(fā)出不一致的惡意消息，擾亂忠誠(chéng)將軍的決策护姆。 蘭伯特的論文中矾端，給出了兩種算法，在奸細(xì)數(shù)小于等于 n卵皂，將軍總數(shù)大于等于 3n+1 的情況下秩铆，可以在忠誠(chéng)將軍之間達(dá)成一致。后來(lái)灯变，人們圍繞拜占庭將軍問(wèn)題殴玛，設(shè)計(jì)了眾多算法，比如蘭伯特自己的 PAXOS添祸，Miguel Castro 和 Barbara Liskov 的 PBFT滚粟，Diego Ongaro 和 John Ousterhout 的 RAFT 算法。

之所以叫?“拜占庭將軍問(wèn)題”刃泌，背后還有一段故事凡壤。Jim Gray，又一位圖靈獎(jiǎng)得主蔬咬，提出過(guò) “中國(guó)將軍問(wèn)題”鲤遥，蘭伯特就生了效仿的心。他做了點(diǎn)微創(chuàng)新林艘，改成 “阿爾巴尼亞將軍”盖奈。當(dāng)時(shí)的阿爾巴尼亞是封閉的社會(huì)主義國(guó)家，與外界絕少交流狐援，他覺(jué)得這很安全钢坦，不會(huì)觸怒任何人。但他的同事不同意啥酱，說(shuō)你還得考慮移民在外的阿爾巴尼亞人爹凹，人家的民族自尊心也要尊重啊。于是镶殷，蘭伯特就干脆改成一個(gè)業(yè)已不存在的國(guó)家 “拜占庭”禾酱。

論文發(fā)表了，從此開(kāi)啟了分布式系統(tǒng)的一場(chǎng)大戲。然而颤陶，SIFT 項(xiàng)目卻并不怎么樣颗管，最終他們交差了，代碼也裝在了模擬器上滓走，但最終是否在飛機(jī)上實(shí)用垦江，連蘭伯特都不知道。沒(méi)人知道他們做的工作是否真的有用搅方。

但是多年后比吭，蘭伯特遇到波音的工程師，那工程師告訴蘭伯特姨涡，當(dāng)他讀了 “拜占庭將軍問(wèn)題” 后衩藤，不由自主罵了句：“媽的，原來(lái)需要四個(gè)涛漂】锻”

蘭伯特 1977 年加入 SRI，1985 年離開(kāi)怖喻。蘭伯特當(dāng)時(shí)對(duì) SRI 里設(shè)置太多非科研的管理職位，非常反感岁诉。恰好锚沸，Bob Taylor 剛剛離開(kāi)施樂(lè)，加入 DEC 并創(chuàng)建了 SRC涕癣，SRC 是 DEC 系統(tǒng)研究中心的簡(jiǎn)寫(xiě)哗蜈。蘭伯特就高高興興去了 SRC。

比之 SRI坠韩，SRC 的研發(fā)就更正規(guī)了距潘。在蘭伯特看起來(lái)，SRI 只是因?yàn)橛许?xiàng)目只搁，才找到他音比。而 SRC 的目標(biāo)則更大，要設(shè)計(jì)未來(lái)的計(jì)算機(jī)氢惋。SRI 內(nèi)部的溝通很少洞翩，SRC 的社區(qū)氣氛更濃。

蘭伯特對(duì) Bob Taylor 非常認(rèn)可焰望，高度評(píng)價(jià) Taylor 的管理技巧骚亿，并說(shuō) Taylor 是自己的導(dǎo)師。

蘭伯特一生都在企業(yè)的研究院中工作熊赖，從未在大學(xué)任教来屠。他在修博士學(xué)位時(shí)，還以為自己會(huì)在大學(xué)中教書(shū)研究度過(guò)一生，然而走上了企業(yè)的路后俱笛，一切都變了捆姜。 在他剛剛工作的那個(gè)時(shí)代，計(jì)算機(jī)還算不上大學(xué)中的一個(gè)學(xué)科嫂粟，沒(méi)有人會(huì)跑到大學(xué)去學(xué)習(xí)編程娇未，大學(xué)中也不會(huì)開(kāi)一個(gè)專業(yè)叫計(jì)算機(jī)專業(yè)。蘭伯特在剛開(kāi)始研究計(jì)算機(jī)時(shí)星虹，那還是一片荒地零抬，他也并沒(méi)把計(jì)算機(jī)當(dāng)回事。即便他想回到大學(xué)教書(shū)宽涌，也沒(méi)有什么計(jì)算機(jī)方面的內(nèi)容值得傳授平夜。在他看來(lái)，直到90年代以后卸亮，計(jì)算機(jī)才可算是一個(gè)獨(dú)立學(xué)科忽妒。

另外，蘭伯特覺(jué)得在企業(yè)中混兼贸，有一大好處段直，就是能夠從產(chǎn)業(yè)中抓獲真正的問(wèn)題。而在大學(xué)中溶诞，就沒(méi)有那么好的機(jī)會(huì)鸯檬，只能坐在實(shí)驗(yàn)中幻想問(wèn)題。SIFT 是飛機(jī)制造中的真實(shí)問(wèn)題螺垢；PAXOS 來(lái)自 SRC 設(shè)計(jì)系統(tǒng)中遇到的問(wèn)題喧务；面包店算法雖然不是實(shí)際的行業(yè)問(wèn)題，但對(duì)編程非常重要枉圃；Disk Paxos 是 DEC 工程師要解決磁盤(pán)存儲(chǔ)問(wèn)題而設(shè)計(jì)的功茴；蘭伯特一直都在跟實(shí)際的問(wèn)題做斗爭(zhēng)。

“最有價(jià)值的問(wèn)題孽亲，是產(chǎn)業(yè)中還未意識(shí)到坎穿，而你已經(jīng)先人一步看到的問(wèn)題》稻ⅲ” 蘭伯特說(shuō)赁酝。

盡管他認(rèn)識(shí)到這個(gè)道理，但蘭伯特性情還是內(nèi)向的旭等，他自認(rèn)交游甚少酌呆，更樂(lè)意于坐在家中研究，他也確實(shí)總有大把的問(wèn)題去研究搔耕。而且他的論文隙袁，多數(shù)都是自己?jiǎn)为?dú)搞的痰娱。

時(shí)間與時(shí)鐘

還在 COMPASS 工作的時(shí)候，大約是 1977 年菩收，蘭伯特收到了一篇論文梨睁，來(lái)自?Bob Thomas 和 Paul Johnson，論文內(nèi)容是關(guān)于復(fù)制數(shù)據(jù)庫(kù)的娜饵。蘭伯特讀了一下坡贺，心說(shuō)，這算法有錯(cuò)誤啊箱舞，其中的邏輯導(dǎo)致因果關(guān)系錯(cuò)亂遍坟。

因果關(guān)系是人們認(rèn)知世界最為常用的一種邏輯，雖然有時(shí)候它并不那么清晰晴股，也不那么可靠愿伴。而因果關(guān)系錯(cuò)亂，就好比兒子撮合父親和母親認(rèn)識(shí)电湘，這在計(jì)算機(jī)中肯定是不可以的隔节。

蘭伯特于是動(dòng)手，為 Bob Thomas 和 Paul Johnson 修正錯(cuò)誤寂呛，這就寫(xiě)出了他那篇最知名怎诫，引用數(shù)最多的論文 - “時(shí)間、時(shí)鐘及分布式系統(tǒng)中事件的順序”贷痪。此文對(duì)計(jì)算機(jī)科學(xué)貢獻(xiàn)甚大刽虹，首次提出了邏輯時(shí)鐘、偏序的概念呢诬，革新了人們的時(shí)間觀念，尤其是在分布式系統(tǒng)中對(duì)時(shí)間的認(rèn)識(shí)胖缤。?

絕對(duì)時(shí)間是不存在的尚镰，也是不重要的，事件的因果關(guān)系才最重要?

在對(duì)此問(wèn)題的研究中哪廓，蘭伯特展現(xiàn)了他的才華和研究特點(diǎn)狗唉，他并不僅僅從算法和計(jì)算機(jī)的角度出發(fā)看待問(wèn)題，而是將研究的基礎(chǔ)建筑在一般的物理世界涡真。 要知道他曾經(jīng)念過(guò)一陣子物理學(xué)分俯，后來(lái)才轉(zhuǎn)到數(shù)學(xué)專業(yè)。

不僅對(duì) “時(shí)間哆料、時(shí)鐘” 一文缸剪，蘭伯特絕大多數(shù)的研究，都以一般的物理問(wèn)題為出發(fā)點(diǎn)东亦。他不愿意將問(wèn)題定義在計(jì)算機(jī)杏节、特定算法等狹窄的領(lǐng)域。比如，蘭伯特對(duì) “互斥” 問(wèn)題的定義奋渔，是怎樣避免兩個(gè)人同時(shí)做一件事镊逝。 “同時(shí)” 這個(gè)詞，便是物理意義上的描述嫉鲸。 蘭伯特認(rèn)為扭仁，很多計(jì)算機(jī)科學(xué)家會(huì)陷入薩丕爾—沃爾夫假說(shuō)。薩丕爾—沃爾夫假說(shuō)認(rèn)為骨稿，人們的思維是由語(yǔ)言定義的仪媒。這顛覆了 “語(yǔ)言是思維的載體” 這個(gè)傳統(tǒng)而廣為接受的認(rèn)知。在薩丕爾—沃爾夫假說(shuō)中捻爷，人們混淆了語(yǔ)言和現(xiàn)實(shí)辈灼。當(dāng)人們觀察到現(xiàn)實(shí)，則人們一定要發(fā)明語(yǔ)言去描述這個(gè)現(xiàn)實(shí)也榄，進(jìn)而將語(yǔ)言視為現(xiàn)實(shí)巡莹。而無(wú)法用語(yǔ)言描述的現(xiàn)實(shí)，并不存在甜紫。蘭伯特認(rèn)為這是一種病降宅，他稱之為薩丕爾—沃爾夫綜合征。

蘭伯特并不愿意浪費(fèi)自己的時(shí)間囚霸，將解決的 “實(shí)際問(wèn)題” 建基于某種特定的語(yǔ)言腰根，那樣的問(wèn)題方案，一旦脫離了特定語(yǔ)言拓型，就將一無(wú)用處额嘿。

蘭伯特確實(shí)也從物理學(xué)中得到了養(yǎng)分，他設(shè)計(jì)的邏輯時(shí)鐘劣挫，無(wú)疑受到了愛(ài)因斯坦狹義相對(duì)論册养，以及閔可夫斯基四維時(shí)空的啟發(fā)。在他的論文中压固，將愛(ài)因斯坦和閔可夫斯基的論文列為引文球拦。而物理學(xué)界也頗為欣賞蘭伯特的研究，雖然蘭伯特的思想帐我，還是多應(yīng)用在計(jì)算機(jī)領(lǐng)域坎炼。 不止一位物理學(xué)家告訴蘭伯特，他的 “時(shí)間拦键、時(shí)鐘”一文對(duì)自己頗有價(jià)值谣光。

蘭伯特的研究風(fēng)格，為其成果的傳播帶去了深刻的影響芬为。一方面其論文的價(jià)值抢肛，仿若冰山狼钮，隨著時(shí)間流逝，人們?cè)桨l(fā)認(rèn)識(shí)其重要性捡絮；另一方面其論文有各種解讀熬芜，適用于各種問(wèn)題，而各種誤讀也相伴而來(lái)福稳。 對(duì)于 “時(shí)間涎拉、時(shí)鐘” 一文，有人認(rèn)為這是關(guān)于互斥的論文的圆，有人認(rèn)為這是關(guān)于事件排序的論文鼓拧，蘭伯特苦笑說(shuō)，我這是關(guān)于狀態(tài)機(jī)的論文啊越妈。 人們聽(tīng)了季俩，更加質(zhì)疑，大喊你這不是關(guān)于狀態(tài)機(jī)的梅掠。蘭伯特自己都困惑了酌住，趕緊翻出論文再檢查一遍，文中確定無(wú)誤提及了狀態(tài)機(jī)阎抒，他才松了一口氣酪我，我這就是關(guān)于狀態(tài)機(jī)的論文。

有人研究程序問(wèn)題且叁，有人研究數(shù)學(xué)問(wèn)題都哭，而蘭伯特研究物理問(wèn)題。 他是計(jì)算機(jī)科學(xué)家逞带，專業(yè)是數(shù)學(xué)欺矫，自然用的數(shù)學(xué)方法，但研究的問(wèn)題卻是物理問(wèn)題展氓。

毛刺（Glitch）問(wèn)題

14 世紀(jì)法國(guó)有位哲學(xué)家叫布里丹穆趴，他在觀察驢的時(shí)候，發(fā)現(xiàn)了一個(gè)有趣的問(wèn)題带饱。假設(shè)有一頭驢，它是絕對(duì)理性的阅羹，那么當(dāng)它處在兩堆干草之間勺疼，兩堆一模一樣的干草，且距離一樣遠(yuǎn)捏鱼，那么這頭理性的驢會(huì)活活餓死执庐。因?yàn)樗睦硇裕屗鼰o(wú)法選擇去吃那一堆干草导梆。

聽(tīng)上去荒謬轨淌，但該問(wèn)題確實(shí)引出了很多哲學(xué)思考迂烁。 有人提出，為了解決吃草的問(wèn)題递鹉，驢最好建立自己的信仰盟步，用信仰來(lái)幫助決策。也有人據(jù)此提出問(wèn)題躏结，人們到底是否具有真正意義上的自由意志却盘。

計(jì)算機(jī)發(fā)展了幾十年，突然發(fā)現(xiàn)自己鋼鐵電磁之軀媳拴，也如驢一般優(yōu)柔寡斷黄橘，常常死在兩堆干草之間。 因?yàn)橛?jì)算機(jī)電路處理的都是 1 和 0 兩種信號(hào)屈溉，看上去斬釘截鐵塞关，沒(méi)什么可猶豫的。然而不幸的是子巾，這兩種信號(hào)在電路上是通過(guò)電壓實(shí)現(xiàn)的帆赢，而電壓的增減并非“不連續(xù)的”，而是“連續(xù)的”砰左。這就帶來(lái)了驢子的問(wèn)題匿醒，在某個(gè)時(shí)間點(diǎn)上，電壓很可能非1非0缠导，而是一個(gè)類似 0.5的中間值廉羔，計(jì)算機(jī)怎么辦？在當(dāng)前大多數(shù)的同步電路中僻造，有一個(gè)系統(tǒng)時(shí)鐘憋他，通過(guò)系統(tǒng)時(shí)鐘來(lái)為所有的電路信號(hào)提供時(shí)鐘頻率，只要保證電壓信號(hào)在約定的時(shí)鐘時(shí)間是穩(wěn)定的 1 或 0髓削，便解決了這個(gè)問(wèn)題竹挡。這是當(dāng)前的主流方法，幾乎所有的計(jì)算機(jī)都是這樣設(shè)計(jì)的立膛。

系統(tǒng)時(shí)鐘起到了“仲裁人”的作用揪罕，這就意味著一旦遇到了布里丹之驢的困境，就需要引入“仲裁人”宝泵。蘭伯特的解決思路則不需要仲裁人好啰，他稱這種算法為 “仲裁人問(wèn)題”。

這篇論文的發(fā)表儿奶，可謂坎坷框往，被拒了一家又一家，被拒一次又一次闯捎，最終在 “物理學(xué)基礎(chǔ)” 期刊上發(fā)表椰弊。

蘭伯特提出的思路许溅，在電腦電路和芯片上的實(shí)現(xiàn)，就是異步電路秉版，至今沒(méi)有進(jìn)入主流應(yīng)用贤重。另一位圖靈獎(jiǎng)獲得者 Ivan Sutherland，他比蘭伯特獲獎(jiǎng)還要早沐飘，也在研究異步電路并為異步電路鼓吹游桩。?Ivan Sutherland 還是電腦圖形界面的發(fā)明人，不是他的慈悲耐朴，也許命令行的歷史還要更長(zhǎng)久借卧，沒(méi)準(zhǔn)至今還在用。想想看筛峭，在 DOS 命令行里輸入指令：ecommerce buy -taobao no 09898651铐刘，多么醉人的操作。感謝?Sutherland影晓。

與迪科斯徹合作

艾茲格·W·迪科斯徹（?Edsger W. Dijkstra）是并發(fā)與分布式系統(tǒng)的鼻祖镰吵，比蘭伯特更早。他是荷蘭人挂签，1952 年成為荷蘭的“第一位”程序員疤祭。他在計(jì)算機(jī)領(lǐng)域的研究，幾乎涉及了這個(gè)新領(lǐng)域的一切饵婆，他是計(jì)算機(jī)科學(xué)的真正奠基者勺馆，人們很難再找到一人在計(jì)算機(jī)領(lǐng)域的成就能夠超越他。也是在他的推動(dòng)下侨核，計(jì)算機(jī)編程從一種莫名其妙的藝術(shù)草穆，發(fā)展成為一門(mén)真正的學(xué)科。他獲得 1972 的圖靈獎(jiǎng)搓译，這一年蘭伯特剛剛獲得拿到博士學(xué)位悲柱。

在蘭伯特眼中，迪科斯徹該是半師半友的地位些己，他在圖靈獎(jiǎng)演講中豌鸡，第一張 PPT 便提及是迪科斯徹開(kāi)創(chuàng)了并發(fā)和分布式系統(tǒng)。

蘭伯特與迪科斯徹合作過(guò)一篇論文段标，僅此一篇涯冠，那是一篇關(guān)于“并發(fā)系統(tǒng)垃圾收集”的論文。

此事緣起于迪科斯徹的 EWD 報(bào)告怀樟。EWD 即迪科斯徹名字的首字母功偿。迪科斯徹喜歡用鋼筆寫(xiě)作盆佣，從 1962 年開(kāi)始往堡，他把自己寫(xiě)的所有手稿稱為 EWD械荷，并為每個(gè)稿子加以編號(hào)。他會(huì)影印每份稿子虑灰，發(fā)送給同事和朋友們吨瞎。同事和朋友們就繼續(xù)影印，并在計(jì)算機(jī)學(xué)界散發(fā)穆咐，由此業(yè)內(nèi)稱之為 “EWD 報(bào)告”颤诀，若放在今天，就類似于個(gè)人博客或者個(gè)人公眾號(hào)对湃。最后一份 EWD 報(bào)告是2002 年 4 月 14 日的崖叫，而同年 8 月 6 日迪科斯徹病逝，可見(jiàn)他的勤奮拍柒。 EWD 報(bào)告現(xiàn)有約 1300 多份稿件心傀。

說(shuō)回他們的合作。蘭伯特讀了迪科斯徹的 EWD 報(bào)告拆讯，覺(jué)得對(duì)這篇文章脂男，自己可以提出更簡(jiǎn)單的算法，于是他寫(xiě)信給迪科斯徹种呐。迪科斯徹看后宰翅，很欣賞，便要將蘭伯特列為論文的合作者爽室。同時(shí)汁讼，迪科斯徹寄了一份詳細(xì)的原稿給蘭伯特，蘭伯特讀了后肮之，也惺惺相惜掉缺，但遺憾的發(fā)現(xiàn)，迪科斯徹的證明非常嚴(yán)謹(jǐn)可靠戈擒。蘭伯特起了點(diǎn)好強(qiáng)之心眶明，暗下決心一定要找出點(diǎn)小錯(cuò)誤來(lái)，肯定會(huì)有小錯(cuò)誤的筐高，他告訴自己搜囱。當(dāng)時(shí)蘭伯特剛剛設(shè)計(jì)了一種針對(duì)并發(fā)系統(tǒng)算法的邏輯證明方法，蘭伯特打定主意柑土，要用自己的方法蜀肘，認(rèn)真的完成證明，幫助迪科斯徹修正那個(gè)還沒(méi)發(fā)現(xiàn)的小錯(cuò)誤稽屏。然而扮宠，蘭伯特剛開(kāi)始工作 15 分鐘，就發(fā)現(xiàn)算法里有個(gè)錯(cuò)誤狐榔，并不是小錯(cuò)誤坛增，而是嚴(yán)重的錯(cuò)誤获雕，算法是錯(cuò)的。蘭伯特用掉了整個(gè)周末收捣，一方面解決了那個(gè)錯(cuò)誤届案，另一方面用自己的方法給出了嚴(yán)謹(jǐn)?shù)淖C明。后來(lái)他才發(fā)現(xiàn)罢艾，實(shí)際上迪科斯徹也解決了那個(gè)錯(cuò)誤楣颠。但迪科斯徹認(rèn)為無(wú)需蘭伯特那嚴(yán)謹(jǐn)?shù)姆椒ǎJ(rèn)為沒(méi)必要嘛咐蚯。最終發(fā)表論文的時(shí)候童漩，二人做了妥協(xié)，在兩種方法上折中處理了一下春锋。 后來(lái)睁冬，另外兩位學(xué)者?Susan Owicki 和?David Gries 也采用類似蘭伯特那嚴(yán)謹(jǐn)?shù)姆椒ǎ瑢?xiě)出了證明的論文看疙。但令蘭伯特想笑的是豆拨，之后迪科斯徹提及他的方法，卻總是說(shuō) Owicki-Gries 算法能庆。蘭伯特心說(shuō)施禾，這明明是我先給你看的啊。 多年之后搁胆，蘭伯特回首往事弥搞，覺(jué)得自己當(dāng)時(shí)有點(diǎn)傾向于用程序語(yǔ)言或者類程序語(yǔ)言的方法解決問(wèn)題。后來(lái)蘭伯特意識(shí)到渠旁，若你不打算寫(xiě)程序攀例，那就不要用程序語(yǔ)言。算法不是程序顾腊。

上面提及的 Susan Owicki 是一位女性計(jì)算機(jī)學(xué)家粤铭，她是很有建樹(shù)的計(jì)算機(jī)學(xué)者，但在 2002 年竟然轉(zhuǎn)行杂靶，做起了心理醫(yī)生梆惯。

蘭伯特在研究中，一向關(guān)注對(duì)算法的嚴(yán)謹(jǐn)證明吗垮，這種風(fēng)格伴隨了他的所有工作垛吗，他認(rèn)為比較起來(lái)，70年代的歐洲學(xué)者還是比較老派烁登，看待數(shù)學(xué)證明比美國(guó)人更嚴(yán)肅怯屉。

順序一致性

在面包店算法中，蘭伯特用到了計(jì)數(shù)器，由于可能需要多個(gè)計(jì)數(shù)器锨络，就需要解決計(jì)數(shù)器的一致性問(wèn)題蝗敢。這是蘭伯特研究的一個(gè)重要領(lǐng)域：順序一致性問(wèn)題（Sequential consistency）。蘭伯特在這個(gè)問(wèn)題上的成果足删，深刻影響了計(jì)算機(jī)軟件訪問(wèn)共享內(nèi)存的方式。他為共享內(nèi)存定義了三種寄存器锁右，安全寄存器失受、?規(guī)則寄存器、原子寄存器咏瑟。

現(xiàn)代編程語(yǔ)言 Java 和 C++ 在實(shí)現(xiàn)內(nèi)存一致性上拂到，均采用了順序一致性理論。今天占據(jù)主流的多核處理器码泞，也要感謝蘭伯特在 1979 年所做出的研究兄旬。

蘭伯特從 75 年便開(kāi)始對(duì)這個(gè)問(wèn)題感興趣，他作了一些演講交流余寥，但應(yīng)者寥寥领铐，他就將研究擱置了。84年宋舷，另外一位學(xué)者?Jay Misra 發(fā)表了論文绪撵，蘭伯特一看，與自己的方向相近祝蝠。于是蘭伯特重新開(kāi)始寫(xiě)自己的論文音诈，完成后寄給了 CACM，當(dāng)時(shí)的編輯恰好是?Fred Schneider绎狭。?Schneider 看到論文细溅，給蘭伯特打電話，說(shuō)自己看不懂儡嘶。蘭伯特就在電話里給他解釋喇聊，解釋來(lái)解釋去，蘭伯特把自己給解釋暈了蹦狂，他大吃一驚承疲，原來(lái)算法是錯(cuò)的。他趕緊重新改論文鸥咖。由此他對(duì)?Schneider 非常感謝燕鸽，因此若不是?Schneider 的 “不懂”，自己就要擺個(gè)大烏龍了啼辣，在期刊上發(fā)表一篇錯(cuò)誤論文啊研，惹天下英雄嘲笑，那可真是蒙羞。在他的一次演講 PPT 上党远，曾經(jīng)出現(xiàn)過(guò) Bug削解，這都讓蘭伯特耿耿于懷。所以沟娱，蘭伯特真是松了一口氣氛驮。

蘭伯特說(shuō)過(guò)一句話：永遠(yuǎn)不要說(shuō) “顯然正確”，一切都需要證明济似。

PAXOS 算法

Paxos 算法是蘭伯特非常重要的成果矫废，至今在分布式系統(tǒng)中廣為應(yīng)用。Paxos 算法的論文砰蠢，名為 “兼職議會(huì)”蓖扑，完成于 1989 年，但正式發(fā)表在 TOCS 上台舱，卻是 1998 年律杠，9 年過(guò)去了。其中的故事非常曲折竞惋。

在拜占庭將軍問(wèn)題提出后柜去，蘭伯特看到過(guò)一本書(shū)，介紹如何做數(shù)據(jù)庫(kù)容錯(cuò)系統(tǒng)拆宛。蘭伯特認(rèn)為該書(shū)的描述是錯(cuò)的诡蜓，因?yàn)樵诜植际角闆r下，書(shū)中引入了一個(gè) Leader胰挑，而要選出 Leader蔓罚，其實(shí)又回到了拜占庭將軍問(wèn)題上來(lái)。蘭伯特開(kāi)始思考如何構(gòu)造一個(gè)可實(shí)用的算法瞻颂，解決拜占庭將軍問(wèn)題豺谈。

要知道，在拜占庭將軍問(wèn)題的論文中贡这，雖然提出了 “口頭協(xié)議” 和 “書(shū)面協(xié)議” 兩種方案茬末，但其前提是在一個(gè)同步系統(tǒng)中應(yīng)用。

問(wèn)題是盖矫，現(xiàn)實(shí)世界中我們要應(yīng)對(duì)的丽惭，都是異步系統(tǒng)。在計(jì)算機(jī)和網(wǎng)絡(luò)領(lǐng)域辈双，更是如此责掏。另外，這兩種方案的計(jì)算非常復(fù)雜湃望，并不實(shí)用换衬。

但蘭伯特早已開(kāi)始疑心痰驱，在異步系統(tǒng)中，拜占庭將軍問(wèn)題是無(wú)解的瞳浦。道理很簡(jiǎn)單担映，人們無(wú)法判斷一個(gè)異步系統(tǒng)中的節(jié)點(diǎn)到底是死掉了，還是未死叫潦，也許節(jié)點(diǎn)只是響應(yīng)速度慢蝇完。蘭伯特在一次演講中提出了這個(gè)意見(jiàn)，然而矗蕊，另一位大牛?Butler Lampson 勸蘭伯特說(shuō)：“雖然有這么個(gè)障礙在短蜕，但應(yīng)該可以設(shè)計(jì)一個(gè)算法，在故障節(jié)點(diǎn)不多的情況下拔妥，保證有效節(jié)點(diǎn)達(dá)成一致性〈锕浚” 這給了蘭伯特信心没龙，他開(kāi)始認(rèn)真思考。

Butler Lampson 的姓與蘭伯特相近缎玫，蘭伯特曾經(jīng)就這個(gè)梗開(kāi)過(guò)玩笑硬纤。Butler Lampson 于 1992 年獲得圖靈獎(jiǎng)，而且他倆都在微軟工作過(guò)赃磨。第一臺(tái)計(jì)算機(jī) Xerox Alto 就是在?Lampson 的主持下研發(fā)出來(lái)的筝家。

1985 年 MICHAEL J. FISCHER、NANCY A. LYNCH邻辉、MICHAEL S. PATERSON 三人的著名論文 “存在故障進(jìn)程時(shí)分布式共識(shí)之不可能” 發(fā)表溪王，從形式上嚴(yán)謹(jǐn)論證了異步環(huán)境下，分布式系統(tǒng)無(wú)法達(dá)成共識(shí)值骇，這就是著名的 FLP 不可能原理莹菱。蘭伯特對(duì)此大加贊賞，評(píng)論該論文是分布式系統(tǒng)研究中最重要的論文吱瘩。蘭伯特認(rèn)為 FLP 論文比自己的思考更高明道伟。

蘭伯特在思考過(guò)程中，設(shè)計(jì)了 Paxos 算法使碾。雖然 FLP 不可能原理指出蜜徽，你無(wú)法保證在異步環(huán)境下在分布式系統(tǒng)中達(dá)成一致，但蘭伯特認(rèn)為票摇，我們可以提高達(dá)成一致性的概率拘鞋。

Paxos 是為了達(dá)成一致性的算法，在一點(diǎn)運(yùn)氣的幫助下矢门，系統(tǒng)可以得到一個(gè)一致結(jié)果掐禁。即便運(yùn)氣不好怜械，系統(tǒng)的一致性也不會(huì)被破壞。

蘭伯特完成算法傅事，寫(xiě)成名為 “兼職議會(huì)” 的論文缕允。在之前，他的拜占庭將軍的故事很受歡迎蹭越，于是蘭伯特就決定也構(gòu)造一個(gè)故事來(lái)寫(xiě)論文障本。他把場(chǎng)景搞到了希臘的一個(gè)小島 Paxos 上，Paxos 的議會(huì)中响鹃，議員都是兼職的驾霜，他們進(jìn)進(jìn)出出，如何在這樣的混亂秩序下买置，就法律條文達(dá)成一致性的投票粪糙？ 蘭伯特寫(xiě)這個(gè)故事很可能非常過(guò)癮，他甚至把自己假扮成考古學(xué)家忿项，并在論文中加了一些希臘文字母和希臘人名蓉冈。 在幾次演講中，為了推廣自己的論文轩触，蘭伯特甚至真的戴上希臘小帽扮成考古學(xué)者寞酿。他自己寫(xiě)的很開(kāi)心，玩的很開(kāi)心脱柱，但在一般讀者看來(lái)伐弹，這篇文章有點(diǎn) “尬舞”，原本就難懂榨为，加上希臘考古的故事惨好，就更難懂了。

蘭伯特把稿子投給 TOCS随闺，編輯的回應(yīng)是：“嗯昧狮，有點(diǎn)意思。當(dāng)然板壮，不是啥重要玩意逗鸣。但值得發(fā)表，不過(guò)你得把希臘的那些內(nèi)容去掉绰精∪鲨担”

蘭伯特有點(diǎn)不爽，怪罪編輯沒(méi)有幽默感笨使。這是可以理解的卿樱，認(rèn)真的 “尬舞” 沒(méi)有逗笑觀眾，沒(méi)有迎來(lái)掌聲硫椰，卻引來(lái)了批評(píng)繁调，換誰(shuí)都要暴跳如雷萨蚕。蘭伯特就沒(méi)有搭理編輯，論文也就沒(méi)有發(fā)表蹄胰。

然而他的好朋友兼好同事?Butler Lampson 教授又站出來(lái)了岳遥，他看出了這個(gè)算法的高明之處，認(rèn)為這個(gè)算法可用在任意的分布式系統(tǒng)中裕寨。Lampson 便寫(xiě)了論文支持 Paxos 算法浩蓉。

就在此時(shí)，Barbara Liskov 和她的學(xué)生 Brian Oki 在論文中提出了一個(gè)概念?Timestamp Replication 與 Paxos 非常相近宾袜。Lampson 說(shuō)：“Timestamp Replication 就是 Paxos捻艳。” 一開(kāi)始庆猫，蘭伯特不信认轨，他讀了?Liskov 和?Oki 的論文，覺(jué)得不對(duì)月培，壓根不是一回事嘁字。可后來(lái)节视，他讀了?Oki 單獨(dú)寫(xiě)的論文拳锚，這下子相信了假栓，兩種算法是一回事寻行。但蘭伯特并沒(méi)有在 Paxos 中提及?Barbara Liskov 和 Brian Oki，而且之后人們稱呼這種算法為 Paxos匾荆。蘭伯特認(rèn)為?Barbara Liskov 和 Brian Oki 并沒(méi)有做出形式化的證明拌蜘，這不算數(shù)的。所以牙丽，蘭伯特并不愧疚简卧。

Barbara Liskov 是美國(guó)第一位拿到計(jì)算機(jī)博士學(xué)位的女士，她也是 2008 年圖靈獎(jiǎng)得主烤芦。

作為大神举娩，Barbara Liskov?也不是等閑之輩啊，很快构罗，她與學(xué)生?Miguel Castro 又設(shè)計(jì)了一個(gè)算法铜涉，這就是著名的 PBFT，號(hào)稱解決了拜占庭將軍問(wèn)題遂唧。要知道芙代，Paxos 解決的一致性問(wèn)題，只處理節(jié)點(diǎn)崩潰和信息延遲等問(wèn)題盖彭，并非真正的拜占庭將軍問(wèn)題纹烹，也就是節(jié)點(diǎn)不會(huì)篡改信息页滚，不存在奸細(xì)節(jié)點(diǎn)。而 PBFT 則在異步環(huán)境下铺呵，解決了真正的拜占庭將軍問(wèn)題裹驰。蘭伯特對(duì)此表示認(rèn)可，評(píng)論說(shuō)她提供了一個(gè) “拜占庭” 版本的 Paxos陪蜻。

說(shuō)回??“兼職議會(huì)” 這篇論文邦马。論文就這樣一直沒(méi)有發(fā)表，但在?Lampson 等大牛的支持下宴卖，也早已聞名遐邇了滋将。甚至在一些實(shí)際的生產(chǎn)系統(tǒng)中，人們已經(jīng)用上了 Paxos 算法症昏。

這時(shí)候 TOCS 的編輯 Ken Birman 一聲長(zhǎng)嘆随闽，說(shuō)：“唉，我們?cè)摪l(fā)表 Paxos 論文了肝谭【蛳埽” 但他沒(méi)有善罷甘休，還是要求蘭伯特做一點(diǎn)修改攘烛，加上些 TLA 證明魏滚。但蘭伯特認(rèn)為完全沒(méi)必要。于是蘭伯特請(qǐng)?Keith Marzullo 幫他來(lái)做坟漱。Keith Marzullo 在幽默上也并不是省油的燈鼠次，他在論文開(kāi)頭加了一段說(shuō)：“主要作者正在希臘野外作業(yè)，無(wú)法趕來(lái)芋齿，所以委托我來(lái)修改論文腥寇。” 下面就是?Marzullo 在論文開(kāi)頭加的注觅捆。

后來(lái)赦役，基于 Paxos 的研究越來(lái)越多，Lampson 就演繹了多種變形：AP：Abstract Paxos栅炒；BP：Byzantine Paxos掂摔；CP：Classic Paxos；DP：Disk Paxos赢赊。蘭伯特自己也寫(xiě)了 Simple Paxos 和 Cheap Paxos乙漓。?

工業(yè)界開(kāi)始應(yīng)用 Paxos，Google 的 Chubby域携，還有開(kāi)源的 Zookeeper 都應(yīng)用了 Paxos簇秒。Chubby 的開(kāi)發(fā)者 Mike Burrows 說(shuō)：“世上只有一種一致性算法，那就是Paxos秀鞭∏鞴郏” 另一位亞馬遜工程師曾經(jīng)說(shuō)：“世上有兩種方法構(gòu)造分布式系統(tǒng)扛禽。一種，你用 Paxos 即可皱坛。另一種编曼，干脆就不可靠吧∈１伲” 蘭伯特對(duì)這些評(píng)論感到非常開(kāi)心掐场。

Latex

80 年代初，蘭伯特計(jì)劃寫(xiě)一本 “美國(guó)并發(fā)系統(tǒng)大典”（很可能是開(kāi)玩笑）贩猎。蘭伯特用 Tex 做錄入和排版熊户。Tex 是一套用于科學(xué)論文的排版工具，由大神?Donald Knuth 開(kāi)發(fā)吭服。

插一句嚷堡，Donald Knuth 是 1972 年圖靈獎(jiǎng)得主，他的貢獻(xiàn)主要在算法分析和程序語(yǔ)言設(shè)計(jì)上艇棕。 他好像很喜歡中國(guó)蝌戒，請(qǐng)朋友姚期智幫他起了個(gè)中國(guó)名字 - 高德納。

蘭伯特用 Tex 覺(jué)得還缺點(diǎn)什么沼琉，就在 Tex 上自己寫(xiě)了一套“宏”北苟，于是就形成了自己的 LaTeX。他并沒(méi)想到會(huì)有人為 Latex 付錢(qián)打瘪， 83 年的時(shí)候 Addison-Wesley 找上門(mén)來(lái)友鼻，要采購(gòu) LaTeX，漸漸的瑟慈，?LaTeX 就成了全球科學(xué)領(lǐng)域最流行的排版系統(tǒng)桃移。而?“美國(guó)并發(fā)系統(tǒng)大典”屋匕，蘭伯特壓根就沒(méi)有動(dòng)筆葛碧。

Latex 是免費(fèi)軟件，在 LaTeX Project Public License 下發(fā)行过吻。

TLA

蘭伯特喜歡講故事不假进泼，但他是一個(gè)數(shù)學(xué)家，對(duì)于算法的證明是非常嚴(yán)肅的纤虽。從他的經(jīng)歷也可看到乳绕，他除了發(fā)現(xiàn)問(wèn)題，解決問(wèn)題的能力超群外逼纸，還以形式化證明能力聞名學(xué)界洋措。他自己也以此為豪，有一次他在演講時(shí)穿了一件體恤衫杰刽，上面印著一句話 “You want proof? I'll give you proof!” （你要證明菠发？我會(huì)給你證明Ｍ趼恕）這句話風(fēng)格近似東北人的 “你瞅啥？瞅你怎么地滓鸠！”

蘭伯特解決了眾多實(shí)際的問(wèn)題雁乡，在并發(fā)系統(tǒng)、分布式系統(tǒng)領(lǐng)域可謂有開(kāi)天辟地之功糜俗，這對(duì)于一位科學(xué)家來(lái)說(shuō)也足以自傲了踱稍。但蘭伯特并不滿足，具體問(wèn)題的解決怎么講都是一城一池之得失悠抹，蘭伯特還要更多珠月。他要構(gòu)建一個(gè)自己的世界，這件事他從90年代就開(kāi)始了楔敌，一直努力到今天桥温。他為科學(xué)家和學(xué)者們?cè)O(shè)計(jì)了一種語(yǔ)言，TLA梁丘，號(hào)稱專用于并發(fā)系統(tǒng)的證明侵浸。但在有些演講上他建議物理學(xué)家柒竞、數(shù)學(xué)家們也使用這種語(yǔ)言故觅。

這是他幾十年研究所總結(jié)的經(jīng)驗(yàn)，多年前他就領(lǐng)悟到：“如果你不準(zhǔn)備寫(xiě)程序榴鼎，那么論文中就別用程序語(yǔ)言值漫。”

傳統(tǒng)的學(xué)界習(xí)慣澳腹，寫(xiě)論文的時(shí)候，用語(yǔ)言文字來(lái)描述算法杨何。比如下面這一段話：

x 的平方加上x(chóng)的十倍等于39酱塔，那么求x等于多少。

完全可以用數(shù)學(xué)公式表示成:?

x^2 + x*10 = 39

x=?

用數(shù)學(xué)公式分明更好理解危虱。

而在計(jì)算機(jī)領(lǐng)域羊娃，研究者往往在證明的時(shí)候，用一些編程語(yǔ)言來(lái)表達(dá)思想和算法埃跷，比如下面的偽代碼：

initially x = 0 ;

loop forever x := x + 1 end loop

而蘭伯特非常反感用編程語(yǔ)言來(lái)表達(dá)算法蕊玷，他認(rèn)為一旦陷入編程語(yǔ)言，那么就陷入深坑弥雹，很難保證證明的嚴(yán)謹(jǐn)垃帅。上面的代碼若是用 TLA 來(lái)表達(dá)，則如下：

蘭伯特稱用文字來(lái)論證剪勿，是一種 17世紀(jì)的數(shù)學(xué)方法贸诚，今天已經(jīng) 21 世紀(jì)，學(xué)者們應(yīng)該學(xué)會(huì)用 21 世紀(jì)的證明方法。他大聲疾呼酱固，為 TLA 做推廣二鳄。

蘭伯特認(rèn)為，好的證明技巧媒怯，不僅對(duì)讀者有益订讼，讓讀者更容易讀懂論文，也對(duì)學(xué)者自身有幫助扇苞。學(xué)者用 TLA 這樣的語(yǔ)言欺殿，能夠在寫(xiě)論文的時(shí)候就發(fā)現(xiàn)自己思想中的問(wèn)題。他曾經(jīng)說(shuō)過(guò)：“寫(xiě)作是整理雜亂思想的最好方法鳖敷。”?

雖然缺乏確切的統(tǒng)計(jì)數(shù)據(jù)脖苏，但蘭伯特估計(jì)，所有發(fā)表并經(jīng)過(guò)同行評(píng)審的論文中定踱，約有三分之一存在證明錯(cuò)誤棍潘。有些錯(cuò)誤是因?yàn)檎撟C就錯(cuò)了，有些則因?yàn)樽C明建立在錯(cuò)誤的依據(jù)上崖媚。蘭伯特建議大家都用 TLA亦歉，這樣錯(cuò)誤會(huì)少一些。

加入微軟

2001 年蘭伯特加入微軟研究院畅哑，辦公室位于加州的山景城肴楷，他一直在那里工作到現(xiàn)在。他的職位是首席計(jì)算機(jī)科學(xué)家荠呐，級(jí)別非常高赛蔫，但他獨(dú)自工作，并不帶領(lǐng)團(tuán)隊(duì)泥张。他認(rèn)為自己一個(gè)人獨(dú)自工作的狀態(tài)最好呵恢。比爾蓋茨有時(shí)也會(huì)走進(jìn)他的辦公室，和他討論一些技術(shù)問(wèn)題媚创。

他的辦公室里有一雙輪滑鞋渗钉，每天他穿著輪滑作為交通工具上下班。

他的個(gè)人主頁(yè) www.lamport.org 上最新的文章標(biāo)題是一個(gè)反問(wèn)句：為什么計(jì)算機(jī)科學(xué)家不學(xué)數(shù)學(xué)筝野？? 而多年前晌姚，他就曾經(jīng)問(wèn)過(guò)同樣的問(wèn)題：“為什么計(jì)算機(jī)科學(xué)家不懂物理粤剧？” 雖然他在計(jì)算機(jī)領(lǐng)域有如此偉大的建樹(shù)歇竟，但他在心里也許還是以數(shù)學(xué)家身份為自豪，他最近的一次演講題目就是：“數(shù)學(xué)存在一切事物中”抵恋。

有時(shí)候焕议，圖靈獎(jiǎng)得主蘭伯特先生也會(huì)很謙虛，他在采訪中曾經(jīng)說(shuō)：“我只是善于提出問(wèn)題弧关≈寻玻”