善于提出问题的人 - 图灵奖得主莱斯利兰伯特

初识计算机

2013 年莱斯利兰伯特获得图灵奖，此时他 72 岁，距离他 1978 年发表 “时间、时钟及分布式系统中事件的顺序” 一文，已过去 35 年。在此之前，人们便奇怪为何兰伯特无缘图灵奖，有人认为他批评别人过于尖锐，所以人缘不佳。这些讨论无疑佐证了他的图灵奖确乎名至实归。

获奖仪式上，他要做一个演讲，兰伯特身着体恤衫和短裤上台，他一头灰白长发，蓬蓬松松的和满腮的灰白胡须连在一起，看上去更像一个电影导演，而不像一个科学大师。图灵奖的授奖仪式，没有奥斯卡的珠光宝气，也没有诺贝尔奖那么严肃，就是一个简单的学术交流会。 兰伯特用 PPT 介绍了并发系统研究上的历史，他幽了一默：“你们表扬我发明了因果关系，难道在之前，因果关系不存在？”

兰伯特的获奖介绍是这样写的：“他对分布式和并发系统的理论及实践，做出了重大贡献，尤其是他提出了诸多的概念，例如 ‘因果关系和逻辑时钟’、‘安全性和活性’、‘复制状态机’，还有‘顺序一致性’。”

兰伯特是纽约人，1954 年他入学就读 “Bronx 科学高中”，这所学校非常厉害，学生们都是天才，每年从 2 万报考生中选取不到 1 千人入学。学校在全美高中的综合实力排名 30，但在另一个排名上这学校全球第一，那就是诺贝尔奖得主人数。该校共计有 8 名学生是诺贝尔奖得主，若将该校视作国家，也能在这个榜单上排名全球第 23。

高中毕业后，他进入麻省理工，读数学专业，并于 1960 年获得学士学位。麻省理工不必多说，工程和计算机学科排名全球一二，诺贝尔得奖人数 93。他的硕士学位和博士学位，分别获得于 1963 年和 1972 年，都是在一所叫布兰迪斯的大学，这所学校是犹太人社群在美国建的第一所大学，建校初期，爱因斯坦还曾为该校筹过款。

大约就在 “Bronx 科学高中”，兰伯特开始对计算机感兴趣，甚至曾尝试自己做一台计算机，为此他自己学习了布尔代数，并研究电脑电路。美国的科技界一贯对青少年很友好，HP 给了乔布斯电脑零件，而兰伯特则参观了 IBM 在纽约的实验室，还带走了一些真空管。兰伯特和一个小伙伴，就用这些真空管做了一个 4 位的计数器。

高中毕业后，兰伯特才有机会碰到真正的计算机。那是一个暑期社会活动，兰伯特得到了一个工作机会，到爱迪生联合电气在纽约的供电公司工作。那工作最初是很无聊的，后来兰伯特听说公司里有电脑，就跑去电脑中心，求人家给他转岗，他成功了。之后，他就在电脑中心给一台 IBM 705 装卸 “磁带” 和 “纸带”。 IBM 705 在当时可是最强大的计算机了，60 秒内可做 24 万次运算。兰伯特一边干粗活打杂，一边偷偷学艺。就是在这里，他学会了编程。他的第一个程序，是用 IBM 705 计算 “e” 为一个 125 位的十进制数字。等到他念了大学，放暑假了，他还到供电公司来工作，但他的岗位已经是程序员了。

兰伯特在高中时，数学就很优秀。但进入麻省理工大学后，他的专业最初是物理，当时他觉得学物理更好找工作，而学数学唯一的出路似乎就是当老师。然而，第二年，他从物理专业转到了数学专业，原因呢，据他说，是数学专业不需要写论文就能毕业。

在兰伯特早期的求学和工作生涯中，物理、数学和计算机都已涉及。但直到很久之后，兰伯特才意识到自己也许工作在一个叫做 “计算机科学” 的领域，毕竟，那时候计算机才刚刚出现，在人们的认知中，计算机只是算盘一样的工具，甚至在科学家眼中也是如此。压根就没有一个叫计算机的学科，这和没有吸尘器学科是一个道理。

早年间，兰伯特曾经研究哈希表技术，当他正在搞这个的时候，有人在 CACM 上发表了一篇针对哈希表的研究文章。兰伯特看出那篇文章中的成果还有改进的必要，他写了篇评论，发给了 CACM，告诉编辑，他发现了还有三种变形算法，而该文中并未提及。然而遗憾的是，编辑退了他的稿，认为他的主意没有价值。 更遗憾的是，过了几年，兰伯特发现，他所建议的三种变形算法中的两种，分别在 CACM 上发表。

这个退稿事件在兰伯特的心中产生了两个结果，一个是，他觉得也许自己真的是一位计算机科学家了；另一个是，科技期刊的编辑们，未必都靠谱。而兰伯特与期刊编辑们的争论，在兰伯特的学术生涯中，这并非最后一次.......

兰伯特在读博士期间，为了挣学费和生活费，在一位教授的推荐下，从 “马萨诸塞计算机联盟” 找到了一个职位。

“马萨诸塞计算机联盟” 又称之为 COMPASS，在当时相当有名气，该公司的雇员中颇多计算机大牛，包括另一位图灵奖获得者 - 罗伯特弗洛伊德，还有 Stephen Warshall 和 Michael J. Fischer，这两位虽然并非图灵奖得主，但都在计算机科学上做出了卓越贡献。Fischer 有众多学生后来都成了大牛，其中有一位女学生是华人，名叫姚储枫，她的丈夫就是图灵奖得主中唯一的华人姚期智教授。

兰伯特博士毕业后，原准备去科罗拉多大学教书的，这是中规中矩的道路，他本来以为学数学的出路就是教书。然而，COMPASS 公司问他：“我们正计划在加州搞个新办公室，要不你到加州去？ 继续为我们工作如何？” 兰伯特想了下，点头了。 正当兰伯特准备动身去加州，COMPASS 又找他，有点不好意思，问他：“加州新办公室的计划要黄，不过没事，你还是去加州，继续为我们工作如何？” 就是说，兰伯特可以不用去办公室上班了。兰伯特想了下，又点头了。之后的五年，兰伯特就在加州工作，自由自在，不用去办公室，当然也没有办公室，每年回一趟波士顿总部交差就行。

COMPASS 公司的主要产品是 FORTURN 编译器，偶尔也从国防部接一点外包合同。兰伯特在 COMPASS 的一个项目，是为 Foxboro 公司制造的电脑设计文件系统。这个项目，是兰伯特初次接触并发系统。兰伯特接到这个项目时，还在马萨诸塞，并未去加州。其时，他的一个朋友邀请他去新墨西哥呆上一两个月，度度假，这个朋友在那里有一个庄园。而 COMPASS 也就同意了。

当然兰伯特并非真的度假，他去了新墨西哥后，很快便写出了一本厚厚的“书”，完成了那个项目。兰伯特的这本“书”，之后就成了工程人员开发 “编译器” 的圣经。而 COMPASS 经此项目，对兰伯特彻底放心了，这是个不需要监控的员工，他去那里工作都一样。这才安排兰伯特只身去往加州。从此，兰伯特在 COMPASS 不仅拥有不去办公室的自由，还有了可以自己选题的自由，COMPASS 则不断从政府那里签一些合同交给兰伯特，也就罩住了他的费用，COMPASS一点都不亏。

兰伯特到了加州，仅仅 6 个月后，面包店算法面世。

面包店算法

兰伯特加入 COMPASS 的同时，也成为了 CACM 的会员。这里要先介绍下 ACM，ACM 翻译成中文是 “国际计算机协会”，这是计算机领域全球最权威，影响力最大的组织。图灵奖就是 ACM 设立的一个奖项。 CACM 则可以翻译成 “ACM 通讯”，是 ACM 旗下的一份期刊。兰伯特博士毕业于 1972 年，同年成为 CACM 会员。CACM 是月刊，每月都会寄送给所有会员。

兰伯特在 CACM 上读到一篇文章，介绍进程互斥（mutual exclusion）算法。他心想，咦，我可以发明更简单的算法啊。于是，他就写了篇文章，寄给了 CACM 的编辑，编辑很痛快的给他退了稿，并指出其中有个 Bug。这给了兰伯特一个打击，也给了他两个教训。第一个教训是，并发问题是很难的；第二个教训是，任何算法都要有严谨的证明。 兰伯特知耻后勇，发誓一定要解决这个问题，很快他就写出了新论文，顺利发表，且这篇论文折服了很多人，之前大家都不大相信不依赖底层互斥居然能实现多线程并发问题。

并发系统与互斥问题的提出，源自艾兹格·W·迪科斯彻（ Edsger W. Dijkstra），这是大神级的计算机科学家，早在1972 年便获得图灵奖。迪科斯彻是并发系统、分布式系统的鼻祖。1965 年他在 CACM 上发表的短文 “并行程序的控制”，拉开了一场关于并行系统研究的大幕，该文深刻影响了现代操作系统、程序语言的设计思路。

迪科斯彻提出“进程互斥”问题，所用的场景是哲学家聚餐。一群哲学家共 5 人凑一起围着圆桌吃饭，每位哲学家的左右各有一把叉子，拿起两把筷子就能用餐。但若是五位哲学家同时拿起自己左边的叉子，那么他们都没了右边的叉子，就此进入“死锁”状态。计算机中“死锁”这个词是迪科斯彻发明的。迪科斯彻的解决方案中引入了 “信号量” （semaphore）概念，如同一个服务生一样，协调这些哲学家们。

而兰伯特在街道上溜达的时候，观察到面包店里的生意很红火，收银员忙碌应付拥挤的顾客，他灵光一闪，设计出了面包店算法。 目的是设计一个规则，保证收银员一次只服务一个顾客，从而不至于在两位或多位顾客的七嘴八舌中晕死。兰伯特让每位顾客进入面包店后，自行取一个号码，然后根据这个号码的大小排队。这思想中的创新在于，兰伯特并不需要安排一个单独的店员负责发放号码，而是让新来顾客们打听其他顾客的号码，然后自己发一个号码给自己，只要这个号码大于其他人的即可。

面包店算法一出，给并行系统的设计，提供了一条崭新的思路，之后千树万树梨花开，涌现出很多并行算法来。兰伯特在计算机上成功硕硕，但他最骄傲的，还是面包店算法。按照他的解释，别的成果都有祖先，多少都要受他人的启发和影响，独有面包店算法是彻头彻尾的原创，仿佛是从空气中擒获的星星。

1977 年兰伯特离开了 COMPASS，原因很简单，COMPASS 突然要求他回到马萨诸塞，而兰伯特不想离开加州。兰伯特接受了来自 SRI 的职位，那时候，似乎只有 SRI 和施乐 PARC 两家才有计算机科学研究，但施乐不给兰伯特机会......

SRI 是 “斯坦福研究院” 的简写，由斯坦福大学发起并成立的研究机构，1977 年从斯坦福大学独立出来。据 2015 年数据， SRI 有 2100 名雇员，收入 5 亿多美元。

SRI 之所以雇佣兰伯特，是为了一个 NASA 的合同，NASA 委托 SRI 为飞机开发一个容错电脑系统。这个项目叫做 SIFT。其背景是 70 年代的石油危机，航空公司和飞机制造商都希望飞机更省油，而设计一套系统能够提升飞机的稳定性，减少摩擦力，更省油似乎是可能的。SIFT 就是用来控制飞机的稳定系统。SIFT 的另外一个目的是提高战斗机的操控性能。这个项目就引出了着名的“拜占庭将军问题”。

拜占庭吉将军问题

SIFT 项目所面临的一个难题是，要在多个不可靠的处理器之间达成协议上的一致。这个难题最终由兰伯特和 Rob Shostak、Marshall Pease 三人一起搞定，所以论文上，也就签署了三人之名。实情是，虽然兰伯特排名第一作者，但他是后来者，而 Rob Shostak 和 Marshall Pease 二人的研究更早，且已有了成果。 Shostak 提出最少必须有 4 个处理器，Pease 则从数学上论证了 3n+1 的逻辑，即失效处理器的个数，必须小于总数的三分之一。

在进入 SIFT 项目之前，兰伯特已经开始思考计算机上的 “任意失效” 问题。之前人们所应对的多是 “故障”，也就是设备奔溃宕机，无应答。而 “任意失效”，则意味着设备可能发出故意扰乱分布式计算的错误指令。“任意失效” 后来被称为 “拜占庭故障”，是计算机中所能发生的最坏的故障。用团队合作来比喻，队友死了或者偷懒不干活并非最坏的情况，猪队友拖后腿，捣乱，叛变才是最大的麻烦。1977 年，兰伯特就写过一篇文章，用状态机来克服 “任意失效” 类型的故障，在该文中，兰伯特使用了数字签名，也就是非对称加密算法的签名技术。

兰伯特专攻并发系统和分布式，而数字签名是密码学领域，原本二者并无关联。但无巧不成书，兰伯特居然有位好朋友名叫怀特菲尔德·迪菲！ 又一位图灵奖获得者，且是非对称加密算法的鼻祖。真是英雄风云际会啊！ 1974 年，兰伯特和迪菲在咖啡馆里闲坐，迪菲就絮叨自己的研究，说起了设计一个单向算法是多么困难。兰伯特听了，想了想，说这不难吧，随手在餐巾纸上写了一点子公式。兰伯特写的数学公式，后来就被迪菲与赫尔曼写入 “加密学的新方向” 一文 - 该文当是密码学领域开天辟地的文章 - 文中也就列出了兰伯特，算是兰伯特做出了贡献。当然到了 2009 年，非对称加密和分布式系统再次走到一起，亲密接触，生出了比特币和区块链，那是后话了。

迪菲在科技学术界一向以自由奔放的性情受人敬仰，迪菲自称 “离经叛道者”。兰伯特也是自由自在的散仙形象，这两位大师做朋友，只能说友谊的小船天注定。看看下面的照片，二人的面相气质是不是颇为相近那。

分布式系统与非对称加密算法的首次接触，就是 1977 年兰伯特的这篇论文。而在与 Rob Shostak、Marshall Pease 两人合作的 “拜占庭将军问题” 一文中，兰伯特的贡献是数字签名共识算法，在文中叫 “书面协议”。另外，Pease 设计的算法非常难懂，是兰伯特在最终版本中，改写成了现在这一版易懂的算法，也就是用了递归算法的 “口头协议”。

简单说说 “拜占庭将军问题”，10 位将军围城，只能通过信使送信，需要就进攻还是撤退达成一致，那么如何设计算法？ 其中还有一个大麻烦是，将军中可能存在奸细，这奸细将军就是前述的 “任意失效” 类型的故障，奸细将军会发出不一致的恶意消息，扰乱忠诚将军的决策。 兰伯特的论文中，给出了两种算法，在奸细数小于等于 n，将军总数大于等于 3n+1 的情况下，可以在忠诚将军之间达成一致。后来，人们围绕拜占庭将军问题，设计了众多算法，比如兰伯特自己的 PAXOS，Miguel Castro 和 Barbara Liskov 的 PBFT，Diego Ongaro 和 John Ousterhout 的 RAFT 算法。

之所以叫 “拜占庭将军问题”，背后还有一段故事。Jim Gray，又一位图灵奖得主，提出过 “中国将军问题”，兰伯特就生了效仿的心。他做了点微创新，改成 “阿尔巴尼亚将军”。当时的阿尔巴尼亚是封闭的社会主义国家，与外界绝少交流，他觉得这很安全，不会触怒任何人。但他的同事不同意，说你还得考虑移民在外的阿尔巴尼亚人，人家的民族自尊心也要尊重啊。于是，兰伯特就干脆改成一个业已不存在的国家 “拜占庭”。

论文发表了，从此开启了分布式系统的一场大戏。然而，SIFT 项目却并不怎么样，最终他们交差了，代码也装在了模拟器上，但最终是否在飞机上实用，连兰伯特都不知道。没人知道他们做的工作是否真的有用。

但是多年后，兰伯特遇到波音的工程师，那工程师告诉兰伯特，当他读了 “拜占庭将军问题” 后，不由自主骂了句：“妈的，原来需要四个。”

兰伯特 1977 年加入 SRI，1985 年离开。兰伯特当时对 SRI 里设置太多非科研的管理职位，非常反感。恰好，Bob Taylor 刚刚离开施乐，加入 DEC 并创建了 SRC，SRC 是 DEC 系统研究中心的简写。兰伯特就高高兴兴去了 SRC。

比之 SRI，SRC 的研发就更正规了。在兰伯特看起来，SRI 只是因为有项目，才找到他。而 SRC 的目标则更大，要设计未来的计算机。SRI 内部的沟通很少，SRC 的社区气氛更浓。

兰伯特对 Bob Taylor 非常认可，高度评价 Taylor 的管理技巧，并说 Taylor 是自己的导师。

兰伯特一生都在企业的研究院中工作，从未在大学任教。他在修博士学位时，还以为自己会在大学中教书研究度过一生，然而走上了企业的路后，一切都变了。 在他刚刚工作的那个时代，计算机还算不上大学中的一个学科，没有人会跑到大学去学习编程，大学中也不会开一个专业叫计算机专业。兰伯特在刚开始研究计算机时，那还是一片荒地，他也并没把计算机当回事。即便他想回到大学教书，也没有什么计算机方面的内容值得传授。在他看来，直到90年代以后，计算机才可算是一个独立学科。

另外，兰伯特觉得在企业中混，有一大好处，就是能够从产业中抓获真正的问题。而在大学中，就没有那么好的机会，只能坐在实验中幻想问题。SIFT 是飞机制造中的真实问题；PAXOS 来自 SRC 设计系统中遇到的问题；面包店算法虽然不是实际的行业问题，但对编程非常重要；Disk Paxos 是 DEC 工程师要解决磁盘存储问题而设计的；兰伯特一直都在跟实际的问题做斗争。

“最有价值的问题，是产业中还未意识到，而你已经先人一步看到的问题。” 兰伯特说。

尽管他认识到这个道理，但兰伯特性情还是内向的，他自认交游甚少，更乐意于坐在家中研究，他也确实总有大把的问题去研究。而且他的论文，多数都是自己单独搞的。

时间与时钟

还在 COMPASS 工作的时候，大约是 1977 年，兰伯特收到了一篇论文，来自 Bob Thomas 和 Paul Johnson，论文内容是关于复制数据库的。兰伯特读了一下，心说，这算法有错误啊，其中的逻辑导致因果关系错乱。

因果关系是人们认知世界最为常用的一种逻辑，虽然有时候它并不那么清晰，也不那么可靠。而因果关系错乱，就好比儿子撮合父亲和母亲认识，这在计算机中肯定是不可以的。

兰伯特于是动手，为 Bob Thomas 和 Paul Johnson 修正错误，这就写出了他那篇最知名，引用数最多的论文 - “时间、时钟及分布式系统中事件的顺序”。此文对计算机科学贡献甚大，首次提出了逻辑时钟、偏序的概念，革新了人们的时间观念，尤其是在分布式系统中对时间的认识。

绝对时间是不存在的，也是不重要的，事件的因果关系才最重要

在对此问题的研究中，兰伯特展现了他的才华和研究特点，他并不仅仅从算法和计算机的角度出发看待问题，而是将研究的基础建筑在一般的物理世界。 要知道他曾经念过一阵子物理学，后来才转到数学专业。

不仅对 “时间、时钟” 一文，兰伯特绝大多数的研究，都以一般的物理问题为出发点。他不愿意将问题定义在计算机、特定算法等狭窄的领域。比如，兰伯特对 “互斥” 问题的定义，是怎样避免两个人同时做一件事。 “同时” 这个词，便是物理意义上的描述。 兰伯特认为，很多计算机科学家会陷入萨丕尔—沃尔夫假说。萨丕尔—沃尔夫假说认为，人们的思维是由语言定义的。这颠覆了 “语言是思维的载体” 这个传统而广为接受的认知。在萨丕尔—沃尔夫假说中，人们混淆了语言和现实。当人们观察到现实，则人们一定要发明语言去描述这个现实，进而将语言视为现实。而无法用语言描述的现实，并不存在。兰伯特认为这是一种病，他称之为萨丕尔—沃尔夫综合征。

兰伯特并不愿意浪费自己的时间，将解决的 “实际问题” 建基于某种特定的语言，那样的问题方案，一旦脱离了特定语言，就将一无用处。

兰伯特确实也从物理学中得到了养分，他设计的逻辑时钟，无疑受到了爱因斯坦狭义相对论，以及闵可夫斯基四维时空的启发。在他的论文中，将爱因斯坦和闵可夫斯基的论文列为引文。而物理学界也颇为欣赏兰伯特的研究，虽然兰伯特的思想，还是多应用在计算机领域。 不止一位物理学家告诉兰伯特，他的 “时间、时钟”一文对自己颇有价值。

兰伯特的研究风格，为其成果的传播带去了深刻的影响。一方面其论文的价值，仿若冰山，随着时间流逝，人们越发认识其重要性；另一方面其论文有各种解读，适用于各种问题，而各种误读也相伴而来。 对于 “时间、时钟” 一文，有人认为这是关于互斥的论文，有人认为这是关于事件排序的论文，兰伯特苦笑说，我这是关于状态机的论文啊。 人们听了，更加质疑，大喊你这不是关于状态机的。兰伯特自己都困惑了，赶紧翻出论文再检查一遍，文中确定无误提及了状态机，他才松了一口气，我这就是关于状态机的论文。

有人研究程序问题，有人研究数学问题，而兰伯特研究物理问题。 他是计算机科学家，专业是数学，自然用的数学方法，但研究的问题却是物理问题。

毛刺（Glitch）问题

14 世纪法国有位哲学家叫布里丹，他在观察驴的时候，发现了一个有趣的问题。假设有一头驴，它是绝对理性的，那么当它处在两堆干草之间，两堆一模一样的干草，且距离一样远，那么这头理性的驴会活活饿死。因为它的理性，让它无法选择去吃那一堆干草。

听上去荒谬，但该问题确实引出了很多哲学思考。 有人提出，为了解决吃草的问题，驴最好建立自己的信仰，用信仰来帮助决策。也有人据此提出问题，人们到底是否具有真正意义上的自由意志。

计算机发展了几十年，突然发现自己钢铁电磁之躯，也如驴一般优柔寡断，常常死在两堆干草之间。 因为计算机电路处理的都是 1 和 0 两种信号，看上去斩钉截铁，没什么可犹豫的。然而不幸的是，这两种信号在电路上是通过电压实现的，而电压的增减并非“不连续的”，而是“连续的”。这就带来了驴子的问题，在某个时间点上，电压很可能非1非0，而是一个类似 0.5的中间值，计算机怎么办？在当前大多数的同步电路中，有一个系统时钟，通过系统时钟来为所有的电路信号提供时钟频率，只要保证电压信号在约定的时钟时间是稳定的 1 或 0，便解决了这个问题。这是当前的主流方法，几乎所有的计算机都是这样设计的。

系统时钟起到了“仲裁人”的作用，这就意味着一旦遇到了布里丹之驴的困境，就需要引入“仲裁人”。兰伯特的解决思路则不需要仲裁人，他称这种算法为 “仲裁人问题”。

这篇论文的发表，可谓坎坷，被拒了一家又一家，被拒一次又一次，最终在 “物理学基础” 期刊上发表。

兰伯特提出的思路，在电脑电路和芯片上的实现，就是异步电路，至今没有进入主流应用。另一位图灵奖获得者 Ivan Sutherland，他比兰伯特获奖还要早，也在研究异步电路并为异步电路鼓吹。 Ivan Sutherland 还是电脑图形界面的发明人，不是他的慈悲，也许命令行的历史还要更长久，没准至今还在用。想想看，在 DOS 命令行里输入指令：ecommerce buy -taobao no 09898651，多么醉人的操作。感谢 Sutherland。

与迪科斯彻合作

艾兹格·W·迪科斯彻（ Edsger W. Dijkstra）是并发与分布式系统的鼻祖，比兰伯特更早。他是荷兰人，1952 年成为荷兰的“第一位”程序员。他在计算机领域的研究，几乎涉及了这个新领域的一切，他是计算机科学的真正奠基者，人们很难再找到一人在计算机领域的成就能够超越他。也是在他的推动下，计算机编程从一种莫名其妙的艺术，发展成为一门真正的学科。他获得 1972 的图灵奖，这一年兰伯特刚刚获得拿到博士学位。

在兰伯特眼中，迪科斯彻该是半师半友的地位，他在图灵奖演讲中，第一张 PPT 便提及是迪科斯彻开创了并发和分布式系统。

兰伯特与迪科斯彻合作过一篇论文，仅此一篇，那是一篇关于“并发系统垃圾收集”的论文。

此事缘起于迪科斯彻的 EWD 报告。EWD 即迪科斯彻名字的首字母。迪科斯彻喜欢用钢笔写作，从 1962 年开始，他把自己写的所有手稿称为 EWD，并为每个稿子加以编号。他会影印每份稿子，发送给同事和朋友们。同事和朋友们就继续影印，并在计算机学界散发，由此业内称之为 “EWD 报告”，若放在今天，就类似于个人博客或者个人公众号。最后一份 EWD 报告是2002 年 4 月 14 日的，而同年 8 月 6 日迪科斯彻病逝，可见他的勤奋。 EWD 报告现有约 1300 多份稿件。

说回他们的合作。兰伯特读了迪科斯彻的 EWD 报告，觉得对这篇文章，自己可以提出更简单的算法，于是他写信给迪科斯彻。迪科斯彻看后，很欣赏，便要将兰伯特列为论文的合作者。同时，迪科斯彻寄了一份详细的原稿给兰伯特，兰伯特读了后，也惺惺相惜，但遗憾的发现，迪科斯彻的证明非常严谨可靠。兰伯特起了点好强之心，暗下决心一定要找出点小错误来，肯定会有小错误的，他告诉自己。当时兰伯特刚刚设计了一种针对并发系统算法的逻辑证明方法，兰伯特打定主意，要用自己的方法，认真的完成证明，帮助迪科斯彻修正那个还没发现的小错误。然而，兰伯特刚开始工作 15 分钟，就发现算法里有个错误，并不是小错误，而是严重的错误，算法是错的。兰伯特用掉了整个周末，一方面解决了那个错误，另一方面用自己的方法给出了严谨的证明。后来他才发现，实际上迪科斯彻也解决了那个错误。但迪科斯彻认为无需兰伯特那严谨的方法，他认为没必要嘛。最终发表论文的时候，二人做了妥协，在两种方法上折中处理了一下。 后来，另外两位学者 Susan Owicki 和 David Gries 也采用类似兰伯特那严谨的方法，写出了证明的论文。但令兰伯特想笑的是，之后迪科斯彻提及他的方法，却总是说 Owicki-Gries 算法。兰伯特心说，这明明是我先给你看的啊。 多年之后，兰伯特回首往事，觉得自己当时有点倾向于用程序语言或者类程序语言的方法解决问题。后来兰伯特意识到，若你不打算写程序，那就不要用程序语言。算法不是程序。

上面提及的 Susan Owicki 是一位女性计算机学家，她是很有建树的计算机学者，但在 2002 年竟然转行，做起了心理医生。

兰伯特在研究中，一向关注对算法的严谨证明，这种风格伴随了他的所有工作，他认为比较起来，70年代的欧洲学者还是比较老派，看待数学证明比美国人更严肃。

顺序一致性

在面包店算法中，兰伯特用到了计数器，由于可能需要多个计数器，就需要解决计数器的一致性问题。这是兰伯特研究的一个重要领域：顺序一致性问题（Sequential consistency）。兰伯特在这个问题上的成果，深刻影响了计算机软件访问共享内存的方式。他为共享内存定义了三种寄存器，安全寄存器、 规则寄存器、原子寄存器。

现代编程语言 Java 和 C++ 在实现内存一致性上，均采用了顺序一致性理论。今天占据主流的多核处理器，也要感谢兰伯特在 1979 年所做出的研究。

兰伯特从 75 年便开始对这个问题感兴趣，他作了一些演讲交流，但应者寥寥，他就将研究搁置了。84年，另外一位学者 Jay Misra 发表了论文，兰伯特一看，与自己的方向相近。于是兰伯特重新开始写自己的论文，完成后寄给了 CACM，当时的编辑恰好是 Fred Schneider。 Schneider 看到论文，给兰伯特打电话，说自己看不懂。兰伯特就在电话里给他解释，解释来解释去，兰伯特把自己给解释晕了，他大吃一惊，原来算法是错的。他赶紧重新改论文。由此他对 Schneider 非常感谢，因此若不是 Schneider 的 “不懂”，自己就要摆个大乌龙了，在期刊上发表一篇错误论文，惹天下英雄嘲笑，那可真是蒙羞。在他的一次演讲 PPT 上，曾经出现过 Bug，这都让兰伯特耿耿于怀。所以，兰伯特真是松了一口气。

兰伯特说过一句话：永远不要说 “显然正确”，一切都需要证明。

PAXOS 算法

Paxos 算法是兰伯特非常重要的成果，至今在分布式系统中广为应用。Paxos 算法的论文，名为 “兼职议会”，完成于 1989 年，但正式发表在 TOCS 上，却是 1998 年，9 年过去了。其中的故事非常曲折。

在拜占庭将军问题提出后，兰伯特看到过一本书，介绍如何做数据库容错系统。兰伯特认为该书的描述是错的，因为在分布式情况下，书中引入了一个 Leader，而要选出 Leader，其实又回到了拜占庭将军问题上来。兰伯特开始思考如何构造一个可实用的算法，解决拜占庭将军问题。

要知道，在拜占庭将军问题的论文中，虽然提出了 “口头协议” 和 “书面协议” 两种方案，但其前提是在一个同步系统中应用。

问题是，现实世界中我们要应对的，都是异步系统。在计算机和网络领域，更是如此。另外，这两种方案的计算非常复杂，并不实用。

但兰伯特早已开始疑心，在异步系统中，拜占庭将军问题是无解的。道理很简单，人们无法判断一个异步系统中的节点到底是死掉了，还是未死，也许节点只是响应速度慢。兰伯特在一次演讲中提出了这个意见，然而，另一位大牛 Butler Lampson 劝兰伯特说：“虽然有这么个障碍在，但应该可以设计一个算法，在故障节点不多的情况下，保证有效节点达成一致性。” 这给了兰伯特信心，他开始认真思考。

Butler Lampson 的姓与兰伯特相近，兰伯特曾经就这个梗开过玩笑。Butler Lampson 于 1992 年获得图灵奖，而且他俩都在微软工作过。第一台计算机 Xerox Alto 就是在 Lampson 的主持下研发出来的。

1985 年 MICHAEL J. FISCHER、NANCY A. LYNCH、MICHAEL S. PATERSON 三人的着名论文 “存在故障进程时分布式共识之不可能” 发表，从形式上严谨论证了异步环境下，分布式系统无法达成共识，这就是着名的 FLP 不可能原理。兰伯特对此大加赞赏，评论该论文是分布式系统研究中最重要的论文。兰伯特认为 FLP 论文比自己的思考更高明。

兰伯特在思考过程中，设计了 Paxos 算法。虽然 FLP 不可能原理指出，你无法保证在异步环境下在分布式系统中达成一致，但兰伯特认为，我们可以提高达成一致性的概率。

Paxos 是为了达成一致性的算法，在一点运气的帮助下，系统可以得到一个一致结果。即便运气不好，系统的一致性也不会被破坏。

兰伯特完成算法，写成名为 “兼职议会” 的论文。在之前，他的拜占庭将军的故事很受欢迎，于是兰伯特就决定也构造一个故事来写论文。他把场景搞到了希腊的一个小岛 Paxos 上，Paxos 的议会中，议员都是兼职的，他们进进出出，如何在这样的混乱秩序下，就法律条文达成一致性的投票？ 兰伯特写这个故事很可能非常过瘾，他甚至把自己假扮成考古学家，并在论文中加了一些希腊文字母和希腊人名。 在几次演讲中，为了推广自己的论文，兰伯特甚至真的戴上希腊小帽扮成考古学者。他自己写的很开心，玩的很开心，但在一般读者看来，这篇文章有点 “尬舞”，原本就难懂，加上希腊考古的故事，就更难懂了。

兰伯特把稿子投给 TOCS，编辑的回应是：“嗯，有点意思。当然，不是啥重要玩意。但值得发表，不过你得把希腊的那些内容去掉。”

兰伯特有点不爽，怪罪编辑没有幽默感。这是可以理解的，认真的 “尬舞” 没有逗笑观众，没有迎来掌声，却引来了批评，换谁都要暴跳如雷。兰伯特就没有搭理编辑，论文也就没有发表。

然而他的好朋友兼好同事 Butler Lampson 教授又站出来了，他看出了这个算法的高明之处，认为这个算法可用在任意的分布式系统中。Lampson 便写了论文支持 Paxos 算法。

就在此时，Barbara Liskov 和她的学生 Brian Oki 在论文中提出了一个概念 Timestamp Replication 与 Paxos 非常相近。Lampson 说：“Timestamp Replication 就是 Paxos。” 一开始，兰伯特不信，他读了 Liskov 和 Oki 的论文，觉得不对，压根不是一回事。可后来，他读了 Oki 单独写的论文，这下子相信了，两种算法是一回事。但兰伯特并没有在 Paxos 中提及 Barbara Liskov 和 Brian Oki，而且之后人们称呼这种算法为 Paxos。兰伯特认为 Barbara Liskov 和 Brian Oki 并没有做出形式化的证明，这不算数的。所以，兰伯特并不愧疚。

Barbara Liskov 是美国第一位拿到计算机博士学位的女士，她也是 2008 年图灵奖得主。

作为大神，Barbara Liskov 也不是等闲之辈啊，很快，她与学生 Miguel Castro 又设计了一个算法，这就是着名的 PBFT，号称解决了拜占庭将军问题。要知道，Paxos 解决的一致性问题，只处理节点崩溃和信息延迟等问题，并非真正的拜占庭将军问题，也就是节点不会篡改信息，不存在奸细节点。而 PBFT 则在异步环境下，解决了真正的拜占庭将军问题。兰伯特对此表示认可，评论说她提供了一个 “拜占庭” 版本的 Paxos。

说回 “兼职议会” 这篇论文。论文就这样一直没有发表，但在 Lampson 等大牛的支持下，也早已闻名遐迩了。甚至在一些实际的生产系统中，人们已经用上了 Paxos 算法。

这时候 TOCS 的编辑 Ken Birman 一声长叹，说：“唉，我们该发表 Paxos 论文了。” 但他没有善罢甘休，还是要求兰伯特做一点修改，加上些 TLA 证明。但兰伯特认为完全没必要。于是兰伯特请 Keith Marzullo 帮他来做。Keith Marzullo 在幽默上也并不是省油的灯，他在论文开头加了一段说：“主要作者正在希腊野外作业，无法赶来，所以委托我来修改论文。” 下面就是 Marzullo 在论文开头加的注。

后来，基于 Paxos 的研究越来越多，Lampson 就演绎了多种变形：AP：Abstract Paxos；BP：Byzantine Paxos；CP：Classic Paxos；DP：Disk Paxos。兰伯特自己也写了 Simple Paxos 和 Cheap Paxos。

工业界开始应用 Paxos，Google 的 Chubby，还有开源的 Zookeeper 都应用了 Paxos。Chubby 的开发者 Mike Burrows 说：“世上只有一种一致性算法，那就是Paxos。” 另一位亚马逊工程师曾经说：“世上有两种方法构造分布式系统。一种，你用 Paxos 即可。另一种，干脆就不可靠吧。” 兰伯特对这些评论感到非常开心。

Latex

80 年代初，兰伯特计划写一本 “美国并发系统大典”（很可能是开玩笑）。兰伯特用 Tex 做录入和排版。Tex 是一套用于科学论文的排版工具，由大神 Donald Knuth 开发。

插一句，Donald Knuth 是 1972 年图灵奖得主，他的贡献主要在算法分析和程序语言设计上。 他好像很喜欢中国，请朋友姚期智帮他起了个中国名字 - 高德纳。

兰伯特用 Tex 觉得还缺点什么，就在 Tex 上自己写了一套“宏”，于是就形成了自己的 LaTeX。他并没想到会有人为 Latex 付钱， 83 年的时候 Addison-Wesley 找上门来，要采购 LaTeX，渐渐的， LaTeX 就成了全球科学领域最流行的排版系统。而 “美国并发系统大典”，兰伯特压根就没有动笔。

Latex 是免费软件，在 LaTeX Project Public License 下发行。

TLA

兰伯特喜欢讲故事不假，但他是一个数学家，对于算法的证明是非常严肃的。从他的经历也可看到，他除了发现问题，解决问题的能力超群外，还以形式化证明能力闻名学界。他自己也以此为豪，有一次他在演讲时穿了一件体恤衫，上面印着一句话 “You want proof? I'll give you proof!” （你要证明？我会给你证明！）这句话风格近似东北人的 “你瞅啥？瞅你怎么地！”

兰伯特解决了众多实际的问题，在并发系统、分布式系统领域可谓有开天辟地之功，这对于一位科学家来说也足以自傲了。但兰伯特并不满足，具体问题的解决怎么讲都是一城一池之得失，兰伯特还要更多。他要构建一个自己的世界，这件事他从90年代就开始了，一直努力到今天。他为科学家和学者们设计了一种语言，TLA，号称专用于并发系统的证明。但在有些演讲上他建议物理学家、数学家们也使用这种语言。

这是他几十年研究所总结的经验，多年前他就领悟到：“如果你不准备写程序，那么论文中就别用程序语言。”

传统的学界习惯，写论文的时候，用语言文字来描述算法。比如下面这一段话：

x 的平方加上x的十倍等于39，那么求x等于多少。

完全可以用数学公式表示成:

x^2 + x*10 = 39

x=?

用数学公式分明更好理解。

而在计算机领域，研究者往往在证明的时候，用一些编程语言来表达思想和算法，比如下面的伪代码：

initially x = 0 ;

loop forever x := x + 1 end loop

而兰伯特非常反感用编程语言来表达算法，他认为一旦陷入编程语言，那么就陷入深坑，很难保证证明的严谨。上面的代码若是用 TLA 来表达，则如下：

兰伯特称用文字来论证，是一种 17世纪的数学方法，今天已经 21 世纪，学者们应该学会用 21 世纪的证明方法。他大声疾呼，为 TLA 做推广。

兰伯特认为，好的证明技巧，不仅对读者有益，让读者更容易读懂论文，也对学者自身有帮助。学者用 TLA 这样的语言，能够在写论文的时候就发现自己思想中的问题。他曾经说过：“写作是整理杂乱思想的最好方法。”

虽然缺乏确切的统计数据，但兰伯特估计，所有发表并经过同行评审的论文中，约有三分之一存在证明错误。有些错误是因为论证就错了，有些则因为证明建立在错误的依据上。兰伯特建议大家都用 TLA，这样错误会少一些。

加入微软

2001 年兰伯特加入微软研究院，办公室位于加州的山景城，他一直在那里工作到现在。他的职位是首席计算机科学家，级别非常高，但他独自工作，并不带领团队。他认为自己一个人独自工作的状态最好。比尔盖茨有时也会走进他的办公室，和他讨论一些技术问题。

他的办公室里有一双轮滑鞋，每天他穿着轮滑作为交通工具上下班。

他的个人主页 www.lamport.org 上最新的文章标题是一个反问句：为什么计算机科学家不学数学？ 而多年前，他就曾经问过同样的问题：“为什么计算机科学家不懂物理？” 虽然他在计算机领域有如此伟大的建树，但他在心里也许还是以数学家身份为自豪，他最近的一次演讲题目就是：“数学存在一切事物中”。

有时候，图灵奖得主兰伯特先生也会很谦虚，他在采访中曾经说：“我只是善于提出问题。”

本文来源：William朱玮
原文标题：善于提出问题的人 - 图灵奖得主莱斯利兰伯特

—-

编译者/作者：William朱玮

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。