Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Part of: Synthesis digital library of engineering and computer science.

Series from website.

Includes bibliographical references (p. 157-163) and index.

Notations -- List of figures -- Preface --

Part I. Definitions -- 1. Synchronous model, failure models, and agreement problems -- Computation model: definitions -- Synchronous message-passing model -- The synchronous round-based model -- Failure models -- The consensus problem -- Consensus in the crash failure model -- The simultaneous consensus problem -- The k-set agreement problem -- Consensus in the omission failure model -- Consensus in the Byzantine failure model -- The interactive consistency problem -- Definition in the crash failure model -- Definition in the Byzantine model -- The non-blocking atomic commit problem -- Bibliographic notes --

Part II. Agreement in presence of crash failures -- 2. Consensus and Interactive Consistency in the Crash Failure Model -- Consensus despite crash failures -- A simple consensus algorithm -- A fair consensus algorithm -- Interactive consistency despite crash failures -- Simulating atomic failures -- An interactive consistency algorithm -- A convergence point of view -- Lower bound on the number of rounds -- Preliminaries -- The (t + 1) lower bound -- Proof of the lemmas -- Bibliographic notes --

3. Expedite Decision in the Crash Failure Model -- Early deciding and stopping in interactive consistency -- Early deciding and early stopping -- A predicate to early decide -- An early deciding algorithm -- Correctness proof -- On early decision predicates -- Early-deciding and stopping consensus -- The synchronous condition-based approach -- The condition-based approach in synchronous systems -- A predicate for early decision -- A synchronous condition-based consensus algorithm -- Proof of the algorithm -- Using fast failure detectors -- The class of fast perfect failure detectors -- Adapting the synchronous model to benefit from a fast failure detector -- A simple consensus algorithm based on a fast failure detector -- An early-deciding and stopping algorithm -- Bibliographic notes --

4. Simultaneous Consensus Despite Crash Failures -- Why it is difficult to decide simultaneously before t + 1 rounds -- Preliminary definitions -- Failure pattern, failure discovery, and waste -- Notion of clean round and horizon -- An optimal simultaneous consensus algorithm -- An optimal algorithm -- Proof of the algorithm -- Condition-based simultaneity -- Condition-based simultaneous consensus algorithm -- Optimal condition-based simultaneous consensus -- Bibliographic notes --

5. From Consensus to k-Set Agreement -- A simple k-set agreement problem -- Early-deciding and stopping k-set agreement -- An early-deciding and stopping algorithm -- Proof of the algorithm -- Remark on the early decision predicate -- An enriched synchronous system to expedite k-set agreement -- Enriching the model with additional objects -- A general [m,l]-SA-based k-set agreement algorithm -- Proof of the algorithm -- Lower bound -- Bibliographic notes --

6. Non-Blocking Atomic Commit in Presence of Crash Failures -- A simple non-blocking atomic commit algorithm -- NBAC: short reminder -- A simple algorithm -- Fast commit and fast abort -- Looking for efficient algorithms -- An impossibility theorem -- Weak fast commit and weak fast abort -- Fast commit and weak fast abort are compatible -- A fast commit and weak fast abort algorithm -- Correctness proof -- Other algorithms -- Fast abort and weak fast commit -- The case t < 2 -- Bibliographic notes --

Part III. Agreement Despite Omission or Byzantine Failures -- 7. K-Set Agreement Despite Omission Failures -- The case of send omission failures -- A lower bound for general omission failures -- The case of consensus -- The case of k-set agreement -- General omission failures when t < n/2 -- A simple consensus algorithm -- A k-set algorithm where all good processes decide in t/k + 1 rounds -- Proof of the k-set algorithm: preliminaries lemmas -- Proof of the k-set algorithm: theorem -- General omission failures when t < k/k+1 n -- A k-set algorithm for t < k/k+1 n -- Proof for the case K = 1 (consensus) -- Proof of the algorithm: general case -- Bibliographic notes -- Appendix: Proof of the lemmas -- Proof of the lemmas for the case t < n/2 -- Proofs of the lemmas for the case t < k/k+1 n --

8. Consensus Despite Byzantine Failures -- Interactive consistency for 4 processes despite one Byzantine process -- An algorithm for n = 4 and t =1 -- Proof of the algorithm -- An upper bound on the number of Byzantine processes -- A Byzantine interactive consistency algorithm for n > 3t -- From the Byzantine Generals problem to interactive consistency -- Presenting the algorithm with an example -- A recursive formulation of the algorithm -- Proof of the algorithm -- Complexity measures -- A simple consensus algorithm with constant size messages -- Features of the algorithm -- Presentation of the algorithm -- Proof and properties of the algorithm -- Bibliographic notes --

9. Byzantine Consensus in Enriched Models -- From binary to multivalued Byzantine consensus -- Motivation -- A construction -- Correctness proof -- An interesting property of the construction -- Enriching the synchronous model with message authentication -- Synchronous model with signed messages -- What is the gain obtained from signatures -- Signatures vs error detecting codes -- A consensus algorithm based on signatures -- The algorithm and its cost -- Proof of the algorithm -- A Byzantine generals (BG) algorithm based on signatures -- A Byzantine generals algorithm -- From Byzantine Generals (BG) to consensus -- Bibliographic notes --

Bibliography -- Author's biography -- Index.

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

INSPEC

Google scholar

Google book search

Understanding distributed computing is not an easy task. This is due to the many facets of uncertainty one has to cope with and master in order to produce correct distributed software. A previous book Communication and Agreement Abstraction for Fault-tolerant Asynchronous Distributed Systems (published by Morgan & Claypool, 2010) was devoted to the problems created by crash failures in asynchronous message-passing systems. 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.

Also available in print.

Title from PDF t.p. (viewed on September 14, 2010).