注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

分布式理论系列译序  

2011-03-06 15:34:27|  分类: 搜索与分布式 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

作者:phylips@bmy 时间:2011-5-3

出处:http://duanple.blog.163.com/blog/static/70971767201133011171419/ 


       关于分布式理论的研究已经有数十年的历史。 

本系列论文的选择主要是参照文章<<a brief history of consensus,2pc and transaction commit>>中涉及的那些。同时也会参考该领域的重要的计算机科学家的重要著作,比如Lesslie Lamport。Lesslie Lamport就是著名软件Latex的作者,他在分布式领域的很多研究工作奠定了分布式系统的理论基础。其最重要的论文主要是如下几篇:“Time, Clocks, and the Ordering of Events in a Distributed System”,该论文获得了2000年度 the PODC最具影响力论文奖;“The Byzantine Generals Problem”;“Distributed Snapshots: Determining Global States of a Distributed System”;“Reaching agreement in the presence of faults“,该论文获得2005年度 Edsger W. Dijkstra奖;“The Part-Time Parliament”,该论文中描述了解决分布式一致性的Paxos算法。 同时分布式计算领域还有一个重要的奖项,Edsger W. Dijkstra奖,该奖项每年选择一些对分布式计算理论和实践重要意义的经典论文,它们通常都经过了至少十年的检验。 

本系列主要涉及分布式领域的经典问题比如拜占庭将军问题,重要结论比如FLP不可能性,重要机制replication,leases等,一致性问题算法比如2PC,3PC,Paxos的相关论文。该系列的论文都是很理论性的文章,因此内容相对复杂,有很多算法及证明性的内容。即使是专业的研究人员,大概也只是阅读而不一定会去翻译,因此很多论文网上很少会有翻译的版本。

 这些论文主要围绕着一个核心问题展开,即一致性(consensus)问题。一致性问题是指分布式系统中的节点如何在就某些东西达成一致,可能是一个值,一系列动作,也可能是一个决定。通常有如下应用场景:

1.      决定是否将一个事务提交到数据库

2.      对当前时间的界定达成一致以实现同步化时钟

3.      执行分布式算法的下一步

4.      选择一个leader节点。

这个问题听起来很简单,但是二十多年来它一直是分布式系统理论研究的核心问题。主要有三方面的原因:

 首先,一致性问题可以用来刻化不同强度的系统模型之间的差异。根据FLP结论,对于同步系统来说,它是可解的,但是对于异步系统,即使只有一个单元出错,它也是不可解的。

 其次,设计一个正确的一致性协议是很困难的。Google chubby服务的创建者Mike Burrows说过“世上只有一种一致性协议,那就是paxos”—所有其他的方法都只是paxos的一个特化版本。paxos协议由Leslie Lamport创造,十分精秒但又有些难理解。

 第三,一致性是一个重要的问题。分布式的数据库依赖于它,实际上大多数的分布式系统都是构建在它之上。Group membership systems, fault-tolerant replicated state machines, data stores –这些典型的分布式系统都在某种程度上依赖于一致性问题的解决。同时该问题与另一个经典问题(atomic broadcast,即能在一个网络内将消息可靠的完全有序的传递给其他节点)本质上是同构的。

 一个正确的分布式协议必须满足如下三个条件:

Agreement – all nodes in decide on the same value

Validity – the value that is decided upon must have been proposed by some node in

Termination – all nodes eventually decide

  

参考文献:

http://www.podc.org/dijkstra/

http://the-paper-trail.org/blog/?tag=consensus

http://duanple.blog.163.com/blog/static/70971767201103051639551/

  评论这张
 
阅读(5789)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017