| 000 | 09229nam a2200733 i 4500 | ||
|---|---|---|---|
| 001 | 6812814 | ||
| 003 | IEEE | ||
| 005 | 20200413152859.0 | ||
| 006 | m eo d | ||
| 007 | cr cn |||m|||a | ||
| 008 | 100914s2010 caua foab 001 0 eng d | ||
| 020 | _a9781608455263 (electronic bk.) | ||
| 020 | _z9781608455256 (pbk.) | ||
| 024 | 7 |
_a10.2200/S00294ED1V01Y201009DCT003 _2doi |
|
| 035 | _a(CaBNVSL)gtp00543526 | ||
| 035 | _a(OCoLC)707877271 | ||
| 040 |
_aCaBNVSL _cCaBNVSL _dCaBNVSL |
||
| 050 | 4 |
_aTK5102.5 _b.R294 2010 |
|
| 082 | 0 | 4 |
_a621.3822 _222 |
| 100 | 1 |
_aRaynal, M. _q(Michel) |
|
| 245 | 1 | 0 |
_aFault-tolerant agreement in synchronous message-passing systems _h[electronic resource] / _cMichel Raynal. |
| 260 |
_aSan Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA) : _bMorgan & Claypool, _cc2010. |
||
| 300 |
_a1 electronic text (xxi, 167 p. : ill.) : _bdigital file. |
||
| 490 | 1 |
_aSynthesis lectures on distributed computing theory, _x2155-1634 ; _v# 3 |
|
| 538 | _aMode of access: World Wide Web. | ||
| 538 | _aSystem requirements: Adobe Acrobat Reader. | ||
| 500 | _aPart of: Synthesis digital library of engineering and computer science. | ||
| 500 | _aSeries from website. | ||
| 504 | _aIncludes bibliographical references (p. 157-163) and index. | ||
| 505 | 0 | _aNotations -- List of figures -- Preface -- | |
| 505 | 8 | _aPart 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 -- | |
| 505 | 8 | _aPart 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 -- | |
| 505 | 8 | _a3. 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 -- | |
| 505 | 8 | _a4. 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 -- | |
| 505 | 8 | _a5. 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 -- | |
| 505 | 8 | _a6. 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 -- | |
| 505 | 8 | _aPart 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 -- | |
| 505 | 8 | _a8. 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 -- | |
| 505 | 8 | _a9. 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 -- | |
| 505 | 8 | _aBibliography -- Author's biography -- Index. | |
| 506 | 1 | _aAbstract freely available; full-text restricted to subscribers or individual document purchasers. | |
| 510 | 0 | _aCompendex | |
| 510 | 0 | _aINSPEC | |
| 510 | 0 | _aGoogle scholar | |
| 510 | 0 | _aGoogle book search | |
| 520 | 3 | _aUnderstanding 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. | |
| 530 | _aAlso available in print. | ||
| 588 | _aTitle from PDF t.p. (viewed on September 14, 2010). | ||
| 650 | 0 |
_aTelecommunication _xMessage processing. |
|
| 650 | 0 | _aFault-tolerant computing. | |
| 650 | 0 |
_aElectronic data processing _xDistributed processing. |
|
| 653 | _aagreement problem | ||
| 653 | _aByzantine failure | ||
| 653 | _aconsensus | ||
| 653 | _ainteractive consistency | ||
| 653 | _alower bound | ||
| 653 | _anon-blocking atomic commit | ||
| 653 | _aprocess crash | ||
| 653 | _aomission failure | ||
| 653 | _asynchronous message-passing system | ||
| 830 | 0 | _aSynthesis digital library of engineering and computer science. | |
| 830 | 0 |
_aSynthesis lectures on distributed computing theory, _x2155-1634 ; _v# 3. |
|
| 856 | 4 | 2 |
_3Abstract with links to resource _uhttp://ieeexplore.ieee.org/servlet/opac?bknumber=6812814 |
| 999 |
_c561777 _d561777 |
||