回到基本周末阅读——传染病

||评论()

我这周末要读的论文是艾伦·德默斯(Alan Demers)关于数据库复制的流行技术的重要论文。我意识到在2004年,在我还没有进入亚马逊之前,我已经写了一篇关于流行病领域的基本出版物的博客文章,所以现在似乎是一个更新链接的好时机。

流行的历史

在过去的6-8年里,我们一直在使用各种流行病技术来构建我们的可靠和可扩展的分布式系统,并取得了巨大的成功。既然行业开始处理几乎只能通过使用流行技术来解决的规模问题,那么产生一些关于分布式系统中流行使用起源的基本指针就变得很重要了。

简而言之:流行风格的通信或状态共享为分布式交互提供了高度健壮的媒介。主要优点是

  • 概率模型。这并不意味着它提供的保证比确定性模型少,但我们现在有了一个很好的框架来推理信息在系统中随时间的传播。
  • 同步通信模式。任何良好的传染病通信系统都允许您在“发完就忘”模式下操作,在这种模式下,即使初始发送方失败,所有幸存的节点都将接收到更新(或者没有一个)。
  • 自主和分散操作。流行病技术使你能够根据你收到的数据采取行动,而不需要与你的伙伴进行额外的沟通以达成协议;你可以自主地做决定。
  • 在消息丢失和节点故障方面的健壮性。一旦消息至少被您的一个同伴接收,那么几乎不可能阻止该信息通过系统传播。在我给的最流行的演示,系统仍然运行在90%以下的消息损失有限或没有功能损失。
  • 严谨的数学基础。最后我们有一个协议集,我们可以使用严格的数学技术来推理协议在各种条件下的操作

这些技术在科学领域有着悠久的历史,但主要是在生物学、流行病学和数学领域。流行病圣经从神学的观点来看是

传染病流行理论及其应用贝利·哈夫纳出版社第二版,1957年

这不是一个计算机科学的文本,但它解释了真正的基础。如果你对更多面向计算机科学的文章感兴趣,下面的列表中有一些关于流行传播或“八卦”的基本知识,是学习基础知识的好起点。

为了不显得太自私,我故意把康奈尔大学的论文从这个列表中删除。我相信康奈尔大学的工作在将技术带给更多的计算机科学观众,并将其应用于构建健壮且可扩展的分布式系统方面具有开拓性。我会在后续帖子中列出康奈尔大学的阅读书目。

  • B.贝克,R.肖斯塔克,流言蜚语和电话《离散数学》(1972),第191—193页。
  • 德默斯、格林、豪泽、爱尔兰、拉尔森、申克、斯特吉斯、斯文哈特和特里。用于复制数据库维护的流行算法。在程序ACM Symp。关于Distr计算的原理,第1- 12页,1987年8月。
  • R.戈尔丁和K.泰勒。按流行风格分组。技术报告UCSC-CRL-92-13,加利福尼亚大学,圣克鲁斯,1992年5月。
  • D. Agrawal, A. El-Abbadi和R. Steinke。复制数据库中的流行算法。在程序16 ACM sigac - sigmod Symp。普林西普。数据库系统(PODS),图森,亚利桑那州,1997年5月
  • R. Karp, C. Schindelhauer, S. Shenker, B. Vocking,随机的谣言传播IEEE Symp程序。计算机科学基础,2000。

评论

博客评论Disqus