000 | 04242nam a22005415i 4500 | ||
---|---|---|---|
001 | 978-3-031-02014-8 | ||
003 | DE-He213 | ||
005 | 20240730163754.0 | ||
007 | cr nn 008mamaa | ||
008 | 220601s2019 sz | s |||| 0|eng d | ||
020 |
_a9783031020148 _9978-3-031-02014-8 |
||
024 | 7 |
_a10.1007/978-3-031-02014-8 _2doi |
|
050 | 4 | _aQA75.5-76.95 | |
072 | 7 |
_aUY _2bicssc |
|
072 | 7 |
_aCOM000000 _2bisacsh |
|
072 | 7 |
_aUY _2thema |
|
082 | 0 | 4 |
_a004 _223 |
100 | 1 |
_aSakavalas, Dimitris. _eauthor. _4aut _4http://id.loc.gov/vocabulary/relators/aut _980499 |
|
245 | 1 | 0 |
_aNetwork Topology and Fault-Tolerant Consensus _h[electronic resource] / _cby Dimitris Sakavalas, Lewis Tseng. |
250 | _a1st ed. 2019. | ||
264 | 1 |
_aCham : _bSpringer International Publishing : _bImprint: Springer, _c2019. |
|
300 |
_aXXI, 129 p. _bonline resource. |
||
336 |
_atext _btxt _2rdacontent |
||
337 |
_acomputer _bc _2rdamedia |
||
338 |
_aonline resource _bcr _2rdacarrier |
||
347 |
_atext file _bPDF _2rda |
||
490 | 1 |
_aSynthesis Lectures on Distributed Computing Theory, _x2155-1634 |
|
505 | 0 | _aList of Figures -- List of Tables -- List of Algorithms -- Preface -- Acknowledgments -- Introduction -- Consensus and Network Topology -- Synchronous Crash Fault Tolerance -- Asynchronous Crash Fault Tolerance -- Byzantine Fault Tolerance -- Relay Depth and Approximate Consensus -- Broadcast Under Local Adversaries -- General Adversary -- Bibliography -- Authors' Biographies . | |
520 | _aAs the structure of contemporary communication networks grows more complex, practical networked distributed systems become prone to component failures. Fault-tolerant consensus in message-passing systems allows participants in the system to agree on a common value despite the malfunction or misbehavior of some components. It is a task of fundamental importance for distributed computing, due to its numerous applications. We summarize studies on the topological conditions that determine the feasibility of consensus, mainly focusing on directed networks and the case of restricted topology knowledge at each participant. Recently, significant efforts have been devoted to fully characterize the underlying communication networks in which variations of fault-tolerant consensus can be achieved. Although the deduction of analogous topological conditions for undirected networks of known topology had shortly followed the introduction of the problem, their extension to the directed network case has been proven a highly non-trivial task. Moreover, global knowledge restrictions, inherent in modern large-scale networks, require more elaborate arguments concerning the locality of distributed computations. In this work, we present the techniques and ideas used to resolve these issues. Recent studies indicate a number of parameters that affect the topological conditions under which consensus can be achieved, namely, the fault model, the degree of system synchrony (synchronous vs. asynchronous), the type of agreement (exact vs. approximate), the level of topology knowledge, and the algorithm class used (general vs. iterative). We outline the feasibility and impossibility results for various combinations of the above parameters, extensively illustrating the relation between network topology and consensus. | ||
650 | 0 |
_aComputer science. _99832 |
|
650 | 0 |
_aCoding theory. _94154 |
|
650 | 0 |
_aInformation theory. _914256 |
|
650 | 0 |
_aData structures (Computer science). _98188 |
|
650 | 1 | 4 |
_aComputer Science. _99832 |
650 | 2 | 4 |
_aCoding and Information Theory. _980500 |
650 | 2 | 4 |
_aData Structures and Information Theory. _931923 |
700 | 1 |
_aTseng, Lewis. _eauthor. _4aut _4http://id.loc.gov/vocabulary/relators/aut _980501 |
|
710 | 2 |
_aSpringerLink (Online service) _980502 |
|
773 | 0 | _tSpringer Nature eBook | |
776 | 0 | 8 |
_iPrinted edition: _z9783031001321 |
776 | 0 | 8 |
_iPrinted edition: _z9783031008863 |
776 | 0 | 8 |
_iPrinted edition: _z9783031031427 |
830 | 0 |
_aSynthesis Lectures on Distributed Computing Theory, _x2155-1634 _980503 |
|
856 | 4 | 0 | _uhttps://doi.org/10.1007/978-3-031-02014-8 |
912 | _aZDB-2-SXSC | ||
942 | _cEBK | ||
999 |
_c84971 _d84971 |