Descript 
1 electronic text (xxi, 167 p. : ill.) : digital file 
Series 
Synthesis lectures on distributed computing theory, 21551634 ; # 3


Synthesis digital library of engineering and computer science


Synthesis lectures on distributed computing theory, 21551634 ; # 3

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

Series from website 

Includes bibliographical references (p. 157163) and index 

Notations  List of figures  Preface  

Part I. Definitions  1. Synchronous model, failure models, and agreement problems  Computation model: definitions  Synchronous messagepassing model  The synchronous roundbased model  Failure models  The consensus problem  Consensus in the crash failure model  The simultaneous consensus problem  The kset 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 nonblocking 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  Earlydeciding and stopping consensus  The synchronous conditionbased approach  The conditionbased approach in synchronous systems  A predicate for early decision  A synchronous conditionbased 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 earlydeciding 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  Conditionbased simultaneity  Conditionbased simultaneous consensus algorithm  Optimal conditionbased simultaneous consensus  Bibliographic notes  

5. From Consensus to kSet Agreement  A simple kset agreement problem  Earlydeciding and stopping kset agreement  An earlydeciding and stopping algorithm  Proof of the algorithm  Remark on the early decision predicate  An enriched synchronous system to expedite kset agreement  Enriching the model with additional objects  A general [m,l]SAbased kset agreement algorithm  Proof of the algorithm  Lower bound  Bibliographic notes  

6. NonBlocking Atomic Commit in Presence of Crash Failures  A simple nonblocking 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. KSet Agreement Despite Omission Failures  The case of send omission failures  A lower bound for general omission failures  The case of consensus  The case of kset agreement  General omission failures when t < n/2  A simple consensus algorithm  A kset algorithm where all good processes decide in t/k + 1 rounds  Proof of the kset algorithm: preliminaries lemmas  Proof of the kset algorithm: theorem  General omission failures when t < k/k+1 n  A kset 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; fulltext restricted to subscribers or individual document purchasers 

Compendex 

INSPEC 

Google scholar 

Google book search 

Mode of access: World Wide Web 

System requirements: Adobe Acrobat Reader 

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 Faulttolerant Asynchronous Distributed Systems (published by Morgan & Claypool, 2010) was devoted to the problems created by crash failures in asynchronous messagepassing 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 messagepassing 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 nontrivial problem can be solved). They are consensus, interactive consistency, kset agreement and nonblocking atomic commit 

Also available in print 

MorganIISLIB 
Subject 
Telecommunication  Message processing


Faulttolerant computing


Electronic data processing  Distributed processing


agreement problem


Byzantine failure


consensus


interactive consistency


lower bound


nonblocking atomic commit


process crash


omission failure


synchronous messagepassing system
