| 查看: 392 | 回复: 1 | |||
[交流]
【转帖】古往今来的分布式计算理论 已有1人参与
|
|
古往今来的分布式计算理论 闵应骅 今年的可信系统与网络国际会议（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的技术报告。所以，并不是只有权威杂志的文章才上档次，权威大学的技术报告也可以有历史意义。 原文的意思是说，对于多进程的分布式系统，如果是异步的，而且某些进程不可靠，对所有可靠的进程，是否可以保持二值的一致性，就像“进攻”、“撤退“是一个二值的决定，但要保持一致。她证明了这个问题，不管用什么算法，都可能导致无穷的等待，即使只有一个进程故障也是如此。这里所说的同步是非常广义的，譬如说握手就是一种同步。当一个进程故障，别的进程无从知晓，系统就得无限的等下去。而在同步的情况下，这个问题是有解的，那就是拜占庭将军问题。 闵应骅教授博文原址：http://blog.51xuewen.com/ymin/article_35223.htm |
回复此楼» 猜你喜欢
274求调剂
已经有14人回复
-
北京林业大学硕导招生广告
已经有3人回复
-
309求调剂
已经有5人回复
-
292求调剂
已经有8人回复
-
求调剂
已经有4人回复
-
一志愿 西北大学 总分282 英语一62 求调剂
已经有3人回复
-
调剂310
已经有4人回复
-
北科281学硕材料求调剂
已经有16人回复
-
一志愿上海交大生物与医药专硕324分，求调剂
已经有6人回复
-
一志愿哈工大，085400，320，求调剂
已经有4人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- ATK分子器件电子输运理论计算(电荷转移经典文献推荐)
已经有91人回复
- ATK分子器件电子输运理论计算，结果分析的经典文献推荐
已经有126人回复
- 2012年理论与高性能计算化学国际会议
已经有60人回复
- 全国第二届理论与计算化学软件Molpro Molcas培训班
已经有19人回复
- 理论计算比较：配体的质子化稳定还是 和碱金属作用稳定
已经有12人回复
- 【求助】理论计算新手，求帮忙解决带隙及DOS的问题
已经有21人回复
- 同济大学物理系柯三黄教授招聘理论计算方面的博后
已经有4人回复
- 【求助】NBO方法计算的结果与理论的竟然完全相反是怎么回事呢？
已经有12人回复
- 重奖征集国内国外做理论计算课题组的信息
已经有44人回复
lhfx_313
至尊木虫 (文坛精英)
- 应助: 1 (幼儿园)
- 贵宾: 0.155
- 金币: 29747.1
- 散金: 2852
- 红花: 20
- 沙发: 102
- 帖子: 11130
- 在线: 1568.7小时
- 虫号: 550265
- 注册: 2008-04-23
- 专业: 通信理论与系统
2楼2010-08-25 10:29:59
