000 -LEADER |
fixed length control field |
09229nam a2200733 i 4500 |
001 - CONTROL NUMBER |
control field |
6812814 |
003 - CONTROL NUMBER IDENTIFIER |
control field |
IEEE |
005 - DATE AND TIME OF LATEST TRANSACTION |
control field |
20200413152859.0 |
006 - FIXED-LENGTH DATA ELEMENTS--ADDITIONAL MATERIAL CHARACTERISTICS |
fixed length control field |
m eo d |
007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION |
fixed length control field |
cr cn |||m|||a |
008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION |
fixed length control field |
100914s2010 caua foab 001 0 eng d |
020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
International Standard Book Number |
9781608455263 (electronic bk.) |
020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
Canceled/invalid ISBN |
9781608455256 (pbk.) |
024 7# - OTHER STANDARD IDENTIFIER |
Standard number or code |
10.2200/S00294ED1V01Y201009DCT003 |
Source of number or code |
doi |
035 ## - SYSTEM CONTROL NUMBER |
System control number |
(CaBNVSL)gtp00543526 |
035 ## - SYSTEM CONTROL NUMBER |
System control number |
(OCoLC)707877271 |
040 ## - CATALOGING SOURCE |
Original cataloging agency |
CaBNVSL |
Transcribing agency |
CaBNVSL |
Modifying agency |
CaBNVSL |
050 #4 - LIBRARY OF CONGRESS CALL NUMBER |
Classification number |
TK5102.5 |
Item number |
.R294 2010 |
082 04 - DEWEY DECIMAL CLASSIFICATION NUMBER |
Classification number |
621.3822 |
Edition number |
22 |
100 1# - MAIN ENTRY--PERSONAL NAME |
Personal name |
Raynal, M. |
Fuller form of name |
(Michel) |
245 10 - TITLE STATEMENT |
Title |
Fault-tolerant agreement in synchronous message-passing systems |
Medium |
[electronic resource] / |
Statement of responsibility, etc. |
Michel Raynal. |
260 ## - PUBLICATION, DISTRIBUTION, ETC. |
Place of publication, distribution, etc. |
San Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA) : |
Name of publisher, distributor, etc. |
Morgan & Claypool, |
Date of publication, distribution, etc. |
c2010. |
300 ## - PHYSICAL DESCRIPTION |
Extent |
1 electronic text (xxi, 167 p. : ill.) : |
Other physical details |
digital file. |
490 1# - SERIES STATEMENT |
Series statement |
Synthesis lectures on distributed computing theory, |
International Standard Serial Number |
2155-1634 ; |
Volume/sequential designation |
# 3 |
538 ## - SYSTEM DETAILS NOTE |
System details note |
Mode of access: World Wide Web. |
538 ## - SYSTEM DETAILS NOTE |
System details note |
System requirements: Adobe Acrobat Reader. |
500 ## - GENERAL NOTE |
General note |
Part of: Synthesis digital library of engineering and computer science. |
500 ## - GENERAL NOTE |
General note |
Series from website. |
504 ## - BIBLIOGRAPHY, ETC. NOTE |
Bibliography, etc. note |
Includes bibliographical references (p. 157-163) and index. |
505 0# - FORMATTED CONTENTS NOTE |
Formatted contents note |
Notations -- List of figures -- Preface -- |
505 8# - FORMATTED CONTENTS NOTE |
Formatted contents note |
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 -- |
505 8# - FORMATTED CONTENTS NOTE |
Formatted contents note |
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 -- |
505 8# - FORMATTED CONTENTS NOTE |
Formatted contents note |
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 -- |
505 8# - FORMATTED CONTENTS NOTE |
Formatted contents note |
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 -- |
505 8# - FORMATTED CONTENTS NOTE |
Formatted contents note |
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 -- |
505 8# - FORMATTED CONTENTS NOTE |
Formatted contents note |
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 -- |
505 8# - FORMATTED CONTENTS NOTE |
Formatted contents note |
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 -- |
505 8# - FORMATTED CONTENTS NOTE |
Formatted contents note |
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 -- |
505 8# - FORMATTED CONTENTS NOTE |
Formatted contents note |
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 -- |
505 8# - FORMATTED CONTENTS NOTE |
Formatted contents note |
Bibliography -- Author's biography -- Index. |
506 1# - RESTRICTIONS ON ACCESS NOTE |
Terms governing access |
Abstract freely available; full-text restricted to subscribers or individual document purchasers. |
510 0# - CITATION/REFERENCES NOTE |
Name of source |
Compendex |
510 0# - CITATION/REFERENCES NOTE |
Name of source |
INSPEC |
510 0# - CITATION/REFERENCES NOTE |
Name of source |
Google scholar |
510 0# - CITATION/REFERENCES NOTE |
Name of source |
Google book search |
520 3# - SUMMARY, ETC. |
Summary, etc. |
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. |
530 ## - ADDITIONAL PHYSICAL FORM AVAILABLE NOTE |
Additional physical form available note |
Also available in print. |
588 ## - SOURCE OF DESCRIPTION NOTE |
Source of description note |
Title from PDF t.p. (viewed on September 14, 2010). |
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM |
Topical term or geographic name entry element |
Telecommunication |
General subdivision |
Message processing. |
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM |
Topical term or geographic name entry element |
Fault-tolerant computing. |
650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM |
Topical term or geographic name entry element |
Electronic data processing |
General subdivision |
Distributed processing. |
653 ## - INDEX TERM--UNCONTROLLED |
Uncontrolled term |
agreement problem |
653 ## - INDEX TERM--UNCONTROLLED |
Uncontrolled term |
Byzantine failure |
653 ## - INDEX TERM--UNCONTROLLED |
Uncontrolled term |
consensus |
653 ## - INDEX TERM--UNCONTROLLED |
Uncontrolled term |
interactive consistency |
653 ## - INDEX TERM--UNCONTROLLED |
Uncontrolled term |
lower bound |
653 ## - INDEX TERM--UNCONTROLLED |
Uncontrolled term |
non-blocking atomic commit |
653 ## - INDEX TERM--UNCONTROLLED |
Uncontrolled term |
process crash |
653 ## - INDEX TERM--UNCONTROLLED |
Uncontrolled term |
omission failure |
653 ## - INDEX TERM--UNCONTROLLED |
Uncontrolled term |
synchronous message-passing system |
830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE |
Uniform title |
Synthesis digital library of engineering and computer science. |
830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE |
Uniform title |
Synthesis lectures on distributed computing theory, |
International Standard Serial Number |
2155-1634 ; |
Volume/sequential designation |
# 3. |
856 42 - ELECTRONIC LOCATION AND ACCESS |
Materials specified |
Abstract with links to resource |
Uniform Resource Identifier |
http://ieeexplore.ieee.org/servlet/opac?bknumber=6812814 |