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