古往今来的分布式计算理论(100824）
闵应骅
    今年的可信系统与网络国际会议（DSN2010）在美国芝加哥举行，会上请麻省理工学院（MIT）电气工程和计算机科学系教授Nancy Lynch做了一个特邀报告。她报告的题目就是“古往今来的分布式计算理论”。她在这次会上被授予2010 IEEE Emanuel R. Plore奖。这个奖是由1976年开始，由IEEE董事会授予在与计算机科学有关的信息处理领域，对学科发展和社会改良有杰出贡献的人。Emenuel Plore是一位很有见地的美国科学家，他理解基础研究的价值，以及应用研究的意义。
    我查了一下，Nancy Lynch 1948年生，现在应该是62岁，相貌庒重而美丽（见下面的照片）。1972年拿到MIT数学博士学位。在南加州大学和乔治亚理工大学工作之后，1982年回到MIT。她是ACM院士，美国工程院院士。
    她的主要贡献是奠定了分布式计算的理论基础，而且对该领域的各方面不断产生影响，特别是和M.Fischer，M.Paterson1982年共同完成的不可能性结果。她证明了：即使只有一个进程故障，分布式计算系统就不可能达成一致。它表明了分布式系统的能力很有限，因为没有部件能够知道其他部件在做什么。为此，她研究了应用中一系列的算法，从时钟同步，到资源定位、数据管理、机器人运动调整。她提出了用“输入输出自动机”，验证算法的正确性。
    我对她提出的不可能性很感兴趣，因为，按她这么说，拜占庭将军问题（参见本人博客“基于Web系统的容错”2009/7/12）岂不是没有解了吗？我特为查了一下她的原文（见附件），那是一篇1982年MIT的技术报告。所以，并不是只有权威杂志的文章才上档次，权威大学的技术报告也可以有历史意义。
    原文的意思是说，对于多进程的分布式系统，如果是异步的，而且某些进程不可靠，对所有可靠的进程，是否可以保持二值的一致性，就像“进攻”、“撤退“是一个二值的决定，但要保持一致。她证明了这个问题，不管用什么算法，都可能导致无穷的等待，即使只有一个进程故障也是如此。这里所说的同步是非常广义的，譬如说握手就是一种同步。当一个进程故障，别的进程无从知晓，系统就得无限的等下去。而在同步的情况下，这个问题是有解的，那就是拜占庭将军问题。



附件： MIT-LCS-TR-282

转载本文请联系原作者获取授权，同时请注明本文来自闵应骅科学网博客。
链接地址：https://wap.sciencenet.cn/blog-290937-355923.html

上一篇：谁的无线电话最便宜？(100821）
下一篇： 灾难应对中的信息“尖兵”