Fault-tolerant Agreement in Synchronous Message-passing Systems (Synthesis Lectures on Distributed Computing Theory)

Michel Raynal

  • 出版商: Morgan & Claypool
  • 出版日期: 2010-09-09
  • 售價: $1,690
  • 貴賓價: 9.5$1,606
  • 語言: 英文
  • 頁數: 190
  • 裝訂: Paperback
  • ISBN: 1608455254
  • ISBN-13: 9781608455256
  • 相關分類: 軟體工程
  • 海外代購書籍(需單獨結帳)



The present book focuses on the way to cope with the uncertainty created by process failures (crash, omission failures and Byzantine behavior) in synchronous message-passing systems (i.e., systems whose progress is governed by the passage of time). To that end, the book considers fundamental problems that distributed synchronous processes have to solve. These fundamental problems concern agreement among processes (if processes are unable to agree in one way or another in presence of failures, no non-trivial problem can be solved). They are consensus, interactive consistency, k-set agreement and non-blocking atomic commit. Being able to solve these basic problems efficiently with provable guarantees allows applications designers to give a precise meaning to the words "cooperate" and "agree" despite failures, and write distributed synchronous programs with properties that can be stated and proved. Hence, the aim of the book is to present a comprehensive view of agreement problems, algorithms that solve them and associated computability bounds in synchronous message-passing distributed systems. Table of Contents: List of Figures / Synchronous Model, Failure Models, and Agreement Problems / Consensus and Interactive Consistency in the Crash Failure Model / Expedite Decision in the Crash Failure Model / Simultaneous Consensus Despite Crash Failures / From Consensus to k-Set Agreement / Non-Blocking Atomic Commit in Presence of Crash Failures / k-Set Agreement Despite Omission Failures / Consensus Despite Byzantine Failures / Byzantine Consensus in Enriched Models


本書的重點在於應對同步消息傳遞系統中由於進程失敗(崩潰、遺漏失敗和拜占庭行為)所產生的不確定性。為此,本書考慮了分佈式同步進程必須解決的基本問題。這些基本問題涉及進程之間的一致性(如果進程在存在失敗的情況下無法以某種方式達成一致,則無法解決任何非平凡的問題)。這些問題包括共識、交互一致性、k-集合協議和非阻塞原子提交。能夠高效解決這些基本問題並提供可證明的保證,使應用程序設計人員能夠在失敗的情況下準確理解“合作”和“一致”這兩個詞的含義,並編寫具有可陳述和可證明性質的分佈式同步程序。因此,本書的目標是全面介紹同步消息傳遞分佈式系統中的一致性問題、解決這些問題的算法以及相關的可計算性界限。目錄:圖表清單 / 同步模型、失敗模型和一致性問題 / 崩潰失敗模型中的共識和交互一致性 / 崩潰失敗模型中的快速決策 / 儘管存在崩潰失敗,實現同時共識 / 從共識到k-集合協議 / 在崩潰失敗存在的情況下實現非阻塞原子提交 / 儘管存在遺漏失敗,實現k-集合協議 / 儘管存在拜占庭失敗,實現共識 / 在豐富模型中實現拜占庭共識。