微软科学家Leslie Lamport荣获2013年图灵奖 

编者按：Leslie Lamport，新晋图灵奖得主，一个在计算机领域拥有辉煌成就的大师，他关于时间时钟、面包店算法、拜占庭将军等问题的思考令人乍舌。亲近他的人还会告诉你，他是个年愈古稀仍爱穿旱冰鞋上下班的幽默老头。全球无数人受益于他的成就，却很少听说他的名字。

Leslie Lamport在读高中时就已经开始涉足计算机科学。这乍一听没有什么了不起——但你要知道，那是20世纪50年代中期。当时Lamport正在就读纽约布朗士科学高中，他和一个朋友四处捡破烂，搜寻废弃真空管来搭建数字电路。

虽说“科学要从娃娃抓起”，但对于微软研究院首席研究员Lamport来说，青少年时代的好奇心至今也仍未泯灭。在随后的几十年间，他逐渐成为计算机学界名副其实的传奇人物。他的分布式计算理论奠定了这门学科的基础。他在1978年发表的论文《分布式系统内的时间、时钟事件顺序（Time, Clocks, and the Ordering of Events in a Distributed System）》成为计算机科学史上被引用最多的文献。他为“并发系统的规范与验证”研究贡献了核心原理。

3月18日，为表彰Lamport为这些宝贵的进步所作出的杰出贡献，美国计算机协会（ACM）将2013年度图灵奖颁发给了他，这一殊荣被广泛看作计算学界的诺贝尔奖。

在许多人心目中，没有人比他更有资格获得这个奖项：

Bill Gates

“作为一名伟大的科学家，这项荣誉他当之无愧。作为一名带头人，他界定了分布式计算的许多关键概念，并让今天执行关键任务的计算机系统成为可能，莱斯利的伟大不仅局限于计算机科学领域，而且还体现在努力让世界变得更加安全。世界各地无数人受益于他的工作，却从未听说过他的名字。在我看来，这个奖项也是对微软研究院非凡工作的认可，这里已经成为立志克服业内最难挑战的科学家和工程师们的理想家园。当我们鼓励全球最强大脑都来超越未知的可能时会发生什么？Lamport就是一个很好的例子。”

微软新英格兰研究院技术院士、1992年图灵奖得主Butler Lampson

“Lamport对并发系统理论和实践在质量、范围和重要性上的贡献都是难以超越的。它们完全可以和Dijkstra、Hoare、Milner和Pneuli等所有前辈图灵奖得主的成就相提并论。虽然他能像这些前辈一样做好理论研究，，但他最大的优点是作为一名应用数学家，十分了解如何利用数学工具来解决具有非凡现实意义的问题。”

微软公司技术和研究执行副总裁沈向洋

“我到必应团队工作时，才开始真正意识到他对我们所处行业，尤其是对云计算和分布式系统所做出的令人难以置信的贡献。在必应团队，我们研究了他有关Paxos的论文，并应用他的技术构建了分布式系统，直至今天我们仍在使用。”

麻省理工学院计算机科学和人工智能实验室分布式系统理论研究组负责人Nancy Lynch

“欣闻Lamport荣膺今年的图灵奖。其实，我觉得这个奖项已经姗姗来迟了。他从20世纪70年代起就对分布式计算领域做出了许多基础性贡献。”

华盛顿大学计算机科学与工程系教授Ed Lazowska

“谈及Lamport的影响，我首先想到的是他所设计的算法，当时从许多角度上看，它只是一种理论兴趣，而现在它已经成为我们Web规模系统构建方法的基石——也就是我们所有人每天都在使用的系统。如果没有莱斯利的创新，就不会有我们今天所使用的计算环境。”

施乐帕洛阿尔托研究中心创始人兼经理，以及此后的数字设备公司系统研究中心创始人兼经理Bob Taylor

“互联网建立在分布式系统技术的基础知识之上，而后者又建立在莱斯利所发明的理论基础之上。所以，如果你喜欢使用互联网，那么你就该感谢莱斯利。”

 

图灵奖得主Chuck Thacker（左）和Leslie Lamport最近小聚。

请注意在背景中的旱冰鞋。Lamport现在仍喜欢使用它作为上下班的交通工具。

Lamport现年73岁，他成为微软研究院第五位荣获图灵奖的科学家，此前的获奖者还有Tony Hoare（1980年）、Butler Lampson（1992年）、Jim Gray（1998年）和Chuck Thacker（2009年）。尽管坐拥40多年的绝伦成就，Lamport的自我评价却不是那么光辉夺目。

“我并不太善于寻找解决方案，”他说：“但我确实很善于提出问题。”

在了解他的人中，很少有人会同意这个说法。微软硅谷研究院的微软杰出工程师兼院长Roy Levin就是其中之一——Lamport目前就在那里工作。

“我们开始筹备实验室时，”Levin说：“Lamport就是最早加入的人之一。我们知道自己正在建立一个分布式系统实验室，还有什么比请到分布式计算原理之父更好的事情呢——而且Lamport最有资格。我们很高兴能够与他共事。”

微软的产品组也不例外——他们曾多次获益于Lamport的专业知识。他的Paxos研究成果已经在多个产品中使用，其中包括Windows Azure存储、Azure的REST可用性代理（Rest Availability Proxy）和Cosmos数据存储及查询系统。他还对Windows服务器会话协议（Transaction Protocol）的正确性做出了贡献，而且针对模型驱动应用的奥斯陆平台（Oslo platform）的构筑灵感也来自于他在动作时序逻辑（TLA）的研究。此外，微软公司的许多工作人员都曾受益于Lamport一手创建的LaTeX系统。

Lamport对微软的贡献是无法度量的，关于这一点， David Langworthy能够证明。

“Lamport教会了我如何思考，”作为微软首席开发主管之一的Langworthy说：“使用在高中时学到的简单数学，我竟然从自己的程序中发现了一旦用于在线服务器后就几乎不可能调试的缺陷——幸好提前几年就发现，给我们留出足够的时间来解决这些问题。”

辉煌履历

那样的影响力并不足为奇。Lamport的职业生涯充满了众多令人咋舌的荣誉，让他荣获图灵奖这件事显得“顺理成章”。

·1991年入选美国国家工程院院士。

·2000年凭借《时间、时钟》论文获得ACM分布式计算原理研讨会首届有影响力论文奖。

·2004年凭借与计算机科学有关的信息处理领域突出贡献荣获IEEE Emanuel R. Piore 奖。

·2005年荣获Edsger W. Dijkstra分布式计算奖。

·三次获得ACM SIGOPS荣誉大奖。该奖项旨在表彰发表至少10年、在操作系统领域最有影响力的论文。该奖项成立于2005年，而Lamport曾分别于2007年、2012年和2013年赢得这一殊荣。

·2008年荣获IEEE计算机科学逻辑研讨会（LICS）最经得起时间考验奖。该奖项每年颁发一次，旨在表彰20年以前发表并经得住时间考验的LICS论文。

·2008年荣获IEEE约翰·冯·诺依曼奖章。

·2011年当选美国国家科学院院士。

·2013年荣获Jean-Claude Laprie可信计算奖。

出版物

·《时间、时钟和分布式系统中的事件排序》

·《复制数据库的维护》

·《Dijkstra并行编程问题新解》

·《拜占庭将军问题》

·《兼职议会》

·《Paxos化繁为简》

·《规范系统：硬件和软件工程师的TLA+语言及工具》

Lamport于1972年获得布兰迪斯大学博士学位，2003年获得法国德雷恩大学荣誉博士学位，2003年获得德国基尔大学荣誉博士学位，2004年获得瑞士洛桑联邦高等理工学院荣誉博士学位，2006年获得瑞士提契诺大学荣誉博士学位，2007年获得法国亨利·庞加莱大学荣誉博士学位。

时间、时钟和相对论

这项重要的成果，最早发端于1978年他广有影响力的《时间、时钟》论文的发表，在一定程度上要归功于Lamport恶作剧式的幽默感。当时，Lamport正在马萨诸塞州计算机合伙人公司（又名Compass）任职，他为 Robert Thomas和Paul Johnson共同撰写的论文《复制数据库的维护（The Maintenance of Duplicate Databases）》作序。这篇论文认为，对于两个完全相同的数据库，如果其中之一发生改变，那么对它们更新时需要用到时间戳。

   

Lamport荣获2013年图灵奖

   Lamport的《LaTeX》一书已被翻译成多种语言。

“我意识到，”Lamport回忆说：“它没有保留因果关系。事件按照完成时间的顺序出现在系统中，但其在逻辑上并不与命令发出的顺序相一致。我意识到，如果改变时间戳的产生方法，这个问题可能会很容易得到纠正。”

他的洞察力源自对物理学和狭义相对论的兴趣。他意识到，确定两个事件时间顺序的工作存在问题，除非两者之间有因果联系——也就是说，除非它们之间传递过信息。他由此认识到，如果这种讯息的时间戳可以用来确定事件的顺序，则该系统中发生的所有事件都可以按单一顺序排列。推而广之，一个计算系统内的任何事物都可以用状态机加以描述（状态机保持着特定状态，接收输入后产生一个输出，同时改变其自身的状态。Lamport推论，这个概念可以适用于更加复杂的系统，如银行或航空票务预订。

“最经典的当数他有关时钟的论文，”Levin说：“里面介绍了有关分布式计算、同步和异步实体（asynchronous entities）之间沟通的原理思维新途径，它在当时令人耳目一新，后来成为各种并发系统行为推理的基础。它是一篇开山之作。”

在Lamport的回忆中，所收到的反馈在性质上略有不同。

“《时间、时钟》论文发表后不久，”Lamport回忆道：“Jim Gray告诉我，他曾听到对这篇文章的两种反应：有些人认为它很有见地，也有人认为它微不足道。

“我认为他们可能都是对的，但我不愿意否定那些夸我的人。”

面包店算法

Lamport在Compass工作期间的另一个成果是面包店算法，见于《Dijkstra并行编程问题新解》一文，旨在解决互斥问题：排除多个线程试图对相同存储位置写入时发生数据损坏的现象，以及一个线程完成对特定位置写入之前另一个线程无法读取该位置的现象。其名称暗指到面包店常用的排序系统：客户在进入店面时需要选择一张有编号的票。

“我还在Compass工作时，在《ACM通讯》上读到一篇关于互斥算法的论文，”Lamport回忆道。“这是我第一次接触互斥问题，我看了文章，觉得这似乎并不十分困难。”

于是，他撰写了一个快速算法和简短论文，并将它们寄给刊物编辑，后者立即回复并解释了为什么Lamport的算法行不通。

“这给了我一个教训，”他回忆道：“我不应该编写并行算法而不验证其正确性。”

这件事激励他回过头去，彻底解决这个问题，时至今日，他仍然对自己在面包店算法上的成就感到自豪。

他说：“我感觉自己发现了一种算法，而不是发明了它。”

拜占庭将军

1972年，Lamport搬到湾区，充当Compass西海岸计划前哨基地的先锋，但这个分支机构最终未能落实。另外，在长达五年的时间内，他曾是Compass总部派驻加州的唯一员工。最后，他收到撤回东海岸的指令。但是，他决定加入斯坦福国际研究院（SRI），其前身是斯坦福研究所。

SRI有一个项目，旨在美国航空航天局建立容错型航电计算机系统（fault-tolerant avionics computer system）。考虑到系统的工作性质，故障是不允许发生的。这段经历孕育了两篇旨在解决拜占庭故障的论文，由Lamport和SRI同事Marshall Pease 及Robert Shostak合作完成。

用计算学术语说，“普通”故障可能会导致信息丢失或过程停止，但它们不会遭到损坏——即便如此，也能通过冗余的使用来丢弃损坏的讯息。过程可能会停止，但它们不会给出错误答案。

然而，拜占庭故障却可能犯错误，或给出错误讯息。

当时常用的技术被称为“三重模块冗余（ triple modular redundancy）”，使用三个独立的计算机按照某种少数服从多数的原则“投票”，即使其中一台机器提供了错误结果，其他两台仍然会提供正确答案。但是为了证明其有效，必须拿出证据，而在编写证据过程中，研究人员遇到了一个问题：“错误”计算机可能给其他两台机器发送互不相同的错误值，而后者却不会知道。这就需要使用第四台计算机来应对这个故障。

“如果你使用数字签名，”Lamport说：“就可以用三台机器达成目的，因为如果‘坏’计算机向一台计算机发送了带签名的错误值，并向另一台发送了不同的带签名错误值，另外两台计算机就能够交换消息，以检查究竟发生了什么情况，因为两个不同的值都是签名发送的。”

Lamport还听Jim Gray谈论过另一个性质大体相同的问题，人们称之为“中国将军问题”。这引起了Lamport有关司令将军和叛徒将军的联想，于是他将这个问题及其解决方案命名为“拜占庭将军问题”。

“我记得，与我的朋友Whit Diffie坐在伯克利的一间咖啡馆里，当时他描述了一个构建数字签名的问题，”Lamport回忆说：“他说：‘如果能办到的话，会非常有用。’我说：‘这听起来并不很困难，’于是在一张餐巾纸上，我为他勾画出了第一种数字签名算法。虽然当时并不很实用，但目前已经变得切实可行。”

只可惜那张餐巾纸已经消逝在时间的流沙中。

希腊喜剧

“Lamport应对故障的计划是分布式计算研究的一个重要领域，”Levin说：“他的工作是基础性的。后来，又延伸至约定协议的工作，这是‘让过程收敛于一个共同答案’这个概念的关键部分之一。它就是人们后来所说的Paxos算法。”

无独有偶，2008年图灵奖获得者Barbara Liskov和她的学生布Brian Oki也独立发明了这项技术。

Levin补充说：“Lamport的论文《The Part-Time Parliament》通过希腊神话中一个岛屿及其立法机构的类比来加以解释。或许在一定程度上由于他所选择的这个比喻，这篇论文的实际内容在相当长一段时间没有得到重视。

对此，Lamport有一个不太注重外交辞令的评价。

“随着拜占庭将军问题的成功，我觉得我们需要一个故事来加以说明。我杜撰了一个故事，而那是一次彻底的灾难。“

“我尝试添加一些幽默气氛。还是老问题：借助状态机（state machine）来处理存在的故障。在这种情况下，状态机像是需要通过一系列法律的议会。所不同的是，我们的目的不是处理拜占庭故障，而是处理普通、简单的故障，只不过在异步环境下进行。我们并非处理恶意失败。有些是单纯的工程问题，所以我懒得去探究，就简单地说：‘考古记录并未说明他们究竟如何做到这一点的。’在另一个案例中，为了说明如何进行特定优化，我引用了一个奶酪 商人的故事，说明如何可以使之更有效率。在所有的故事中，我都给人物取了希腊人的名字，以伪希腊语写作，并借用计算机科学家的音译姓名。案例中的奶酪商人名为Gouda ，实际上是一位计算机科学家Mohamed Gouda。”

 

2006年，Lamport（左）和他的妻子（右二）与来自瑞士提契诺大学的学生合影。

Lamport也因此有机会调侃数字设备公司（DEC）的一位好友，Lamport自1985年起就在该公司的系统研究中心工作，一直到2001年加入微软研究院。

“论文的结论是，可能会发生一些导致系统崩溃——也就是完全瓦解的事件。你可以利用系统来重新自我配置，但是如果你稍有疏忽，就可能会遇到一种情况：议会无法再通过更多的法律。在故事中恰恰发生了这种情况，而一个名叫Lampson的将军便接管政权，成为独裁者。

“原来，计算机科学家们并不像数学家那样熟悉希腊字母。Butler Lampson是唯一读懂了故事的人，并意识到这是一篇讨论如何构建分布式系统的论文。”

论文最终发表，但已经是十年之后的事情，而且经过增补，纳入了对干预方法进步的思考。Lamport后来写了一篇题为《Paxos Made Simple》的文章来解释算法的简洁性——而且没有借用希腊文字游戏。随着时间的推移，人们逐渐认识到这项工作是一个真正的进步。

“Paxos算法已经成为现代分布式系统中的一项重要技术，”Levin说：“如果没有Paxos或非常类似的技术为核心，就不会有人想着去建立一个鲁棒、可靠的大型分布式系统。”

抽象的正确性

Lamport还引入了安全和活跃度这两种属性，并作为对并发系统的部分正确性和终止加以推广的最佳途径。“安全”是指一个系统中没有发生任何不好的事情，而“活跃度”则是指有好事发生。

“我认为，你所需要的就是安全和活跃度，”Lamport说。“大约十年后，Fred Schneide和他的学生Bowen Alpern正式界定了这些概念，并证明了我的预感是正确的。

“我引入了安全和活跃度概念后不久，Amir Pnueli（1996年图灵奖获得者）展示了如何使用时序逻辑（temporal logic ）对程序进行推理。你可以用相同的逻辑来表述程序及其属性。对正确性的检验被简化成观察一个程序是否在逻辑上暗合其规范。”

Lamport和Susan Owicki证明，时序逻辑很适用于对活跃度的推理。但是，以时序逻辑来表述程序的想法并未奏效。

“这是一个绝妙的主意，”Lamport说：“只可惜它在实践中行不通。”

一些人认为，解决的办法是增加更多的复杂时序逻辑运算符，但Lamport却另辟蹊径。

“Amir Pneuli原先的逻辑只使用一个时间运算符：始终（always），”Lamport说：“有些事情“始终”是真的。人们加入了不同的复杂时序运算符，例如‘直到某些事情为真’，或‘直到其他一些事情为真’。”

事情变得尾大不掉，也由此不易理解。

“我有一个很好的点子，坚持使用单一的运算符，但是对运用于该运算符的基本非时序方程式加以变革，”他说：“我没有使用只关注单一状态的基本方程，而是加入了关注一对状态——当前状态和未来状态的方程。通过加入那些关注两种状态的方程，我就能够描述一台在这个逻辑下工作的状态机。如果我能够描述这个逻辑下的状态机，就可以把活动度属性描述成为时序方程式，进而就可以把整个程序或整个规范描述成为一个单一方程式——一个真正能够工作的方程式。这就是TLA。”

TLA是TLA+规范语言、PlusCal算法以及与之相关工具的基础。Lamport在2002年出版的专著中对TLA和TLA+做出了解释：《规范系统：硬件和软件工程师的TLA +语言及工具（Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers）》。其基本原则是，正式描述事物的最好办法就是用简单的数学，其推论是：一个规范语言除了精确编写简单数学算式所需的工具外，应尽可能少地包含的其他内容。

从DEC到微软

Lamport在DEC任职期间，他曾有机会与计算机行业内许多其他巨匠合作——而其中不少都曾服务于施乐公司富有传奇色彩的帕洛阿尔托研究中心（Palo Alto Research Center）。Lamport在DEC任职期间的同事包括Levin、 Thacker、 Luca Cardelli、Gray和Lampson。DEC公司卖给康柏之后，研究实验室逐渐萎缩，几乎所有上述人士最后都从DEC转到了微软，但Lamport仍然很怀念他在DEC的经理Bob Taylor。

         

过去30年间，Leslie Lamport曾经为两位经理工作：Bob Taylor（左）和Roy Levin。

“我觉得Bob最突出的特点是他不太为自己考虑”，Lamport说：“他是这样教导Roy Levin的——他的工作就在于让我们保持快乐和高效。从某种意义上说，他在为我们工作，而不是我们为他工作。

“在我为Bob工作的10年里，，他的办公室门总是敞开的，我会经常闲逛到那里和他聊天。有段时间，他却拒绝我说：‘我现在很忙，能不能待会再来？’我至今仍然记得，因为这种情况实在是很少出现。”

但是，Lamport的传奇生涯并没有让他为加入微软之后的情况做好准备。

“微软整个企业上下对研究的态度与我曾任职的其他任何地方都不一样，”他说：“微软意识到，是研究人员贡献了那些研究理念。

“公司能做的就是在研究人员和工程师之间架设沟通渠道，让工程师知道研究人员正在做什么，而研究人员也能知道工程师面临的问题是什么。微软建立了项目经理系统，并且将其作为一种常设机制来实现这一点。”

Lamport的杰出职业生涯也让他体会到微软研究方法的长处。

“我喜欢在一个企业研究院里工作，正是因为我能跟不同的人在一起，充分地接触到各类现实的问题，”他说：“法国电影导演Jean Renoir在自传中写道，有人问他的父亲（印象派画家）Pierre-Auguste为什么取材于生活，并且把他的画架拿到户外而不是在工作室内创作，他说：‘如果我在工作室里画一棵树，我会画出五到六个不同种类的树叶。我能想到的只有这么多。但是，当我走进大自然时，发现了成千上万种不同的叶子。我需要大自然给我灵感。’

“对我而言也是一样。如果我靠自己提出问题，我只能拿出很少的东西，但如果我去外面的世界，那里的人们正在努力打造真正的计算机系统，会有100万个问题等着我。我回顾自己的大部分工作——拜占庭将军、Paxos等——他们都是来自现实世界的问题。”

2月13日，Lamport再次发现自己身处现实世界之中——进行LampsonFest的闭幕演说，这是微软新英格兰研究院为庆祝另一位计算机业界传奇人物、Lamport的同事和朋友Butler Lampson的70岁生日而举办的活动。

在他的演讲的开端，Lamport通过幻灯展示了自己的照片，紧跟着是一张Lampson照片。

“这就是我，”Lamport说：“而这是Butler。

“有人给我发电子邮件询问我有关图灵奖演讲的事宜，我觉得其中可能存在混淆。所以，你应该学会分辨我们。我是这个长胡子的。Butler是拿图灵奖的。”

细细品味这个玩笑吧。我们没有机会再听到它了。