國立虎尾科技大學 |

Network topology and fault-tolerant consensus /

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Network topology and fault-tolerant consensus // Dimitris Sakavalas, Lewis Tseng.
Author:	Sakavalas, Dimitris,
other author:	Tseng, Lewis,
Description:	1 PDF (xxi, 129 pages) :illustrations. :
Notes:	Part of: Synthesis digital library of engineering and computer science.
Subject:	Computer networks. -
Online resource:	https://doi.org/10.2200/S00918ED1V01Y201904DCT016
Online resource:	https://ieeexplore.ieee.org/servlet/opac?bknumber=8715843
ISBN:	9781681735672

Network topology and fault-tolerant consensus /
Sakavalas, Dimitris,

Network topology and fault-tolerant consensus /Dimitris Sakavalas, Lewis Tseng. - 1 PDF (xxi, 129 pages) :illustrations. - Synthesis lectures on distributed computing theory,#162155-1634 ;. - Synthesis digital library of engineering and computer science..

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

Includes bibliographical references (pages 119-128).

8. General adversary -- 8.1. Approximate byzantine consensus under a general adversary -- 8.2. Reliable communication under partial topology knowledge.

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

As 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.

Mode of access: World Wide Web.

ISBN: 9781681735672

Standard No.: 10.2200/S00918ED1V01Y201904DCT016doiSubjects--Topical Terms:

528577
Computer networks.
Subjects--Index Terms:

consensus

LC Class. No.: QA76.9.D5 / S256 2019eb

Dewey Class. No.: 004/.36

Network topology and fault-tolerant consensus /
LDR:05849nam a2200685 i 4500 001 959761
003 IEEE
005 20190606190106.0
006 m eo d
007 cr bn |||m|||a
008 201209s2019 caua fob 000 0 eng d
020 $a 9781681735672 $q electronic
020 $z 9781681735689 $q hardcover
020 $z 9781681735665 $q paperback
024 7 $a 10.2200/S00918ED1V01Y201904DCT016 $2 doi
035 $a (CaBNVSL)thg00979010
035 $a (OCoLC)1102472365
035 $a 8715843
040 $a CaBNVSL $b eng $e rda $c CaBNVSL $d CaBNVSL
050 4 $a QA76.9.D5 $b S256 2019eb
082 0 4 $a 004/.36 $2 23
100 1 $a Sakavalas, Dimitris, $e author. $3 1253099
245 1 0 $a Network topology and fault-tolerant consensus / $c Dimitris Sakavalas, Lewis Tseng.
264 1 $a [San Rafael, California] : $b Morgan & Claypool, $c [2019]
300 $a 1 PDF (xxi, 129 pages) : $b illustrations.
336 $a text $2 rdacontent
337 $a electronic $2 isbdmedia
338 $a online resource $2 rdacarrier
490 1 $a Synthesis lectures on distributed computing theory, $x 2155-1634 ; $v #16
500 $a Part of: Synthesis digital library of engineering and computer science.
504 $a Includes bibliographical references (pages 119-128).
505 8 $a 8. General adversary -- 8.1. Approximate byzantine consensus under a general adversary -- 8.2. Reliable communication under partial topology knowledge.
505 0 $a part I. Network topology and fault-tolerance. 1. Introduction -- 1.1. Computational model -- 1.2. Adversary model -- 1.3. Consensus problems -- 1.4. Algorithm constraints -- 1.5. Summary of results -- 1.6. Related work
505 8 $a 2. Consensus and network topology -- 2.1. The undirected network case -- 2.2. The directed network case -- 2.3. Network preliminaries -- 2.4. Network topology and consensus -- 2.5. Relations among tight conditions
505 8 $a part II. Consensus with a global adversary. 3. Synchronous crash fault tolerance -- 3.1. Topological conditions and implications -- 3.2. Necessity of conditions ccs-i and ccs-g -- 3.3. Approximate consensus algorithm -- 3.4. Exact consensus algorithm
505 8 $a 4. Asynchronous crash fault tolerance -- 4.1. Conditions relations and implications -- 4.2. Iterative approximate consensus -- 4.3. General approximate consensus
505 8 $a 5. Byzantine fault tolerance -- 5.1. Implications of conditions BCS-I and BCS-G -- 5.2. Reduced graph -- 5.3. Iterative approximate consensus -- 5.4. general algorithms
505 8 $a 6. relay depth and approximate consensus -- 6.1. Iterative k-hop algorithm -- 6.2. Asynchronous crash fault tolerance -- 6.3. Synchronous byzantine fault tolerance
505 8 $a part III. Other adversarial models. 7. Broadcast under local adversaries -- 7.1. Preliminaries and topological conditions -- 7.2. Necessity of condition plc for ad hoc broadcast -- 7.3. Feasibility of ad hoc broadcast -- 7.4. Relation with consensus feasibility -- 7.5. Model extensions -- 7.6. Maximum tolerable number of local faults
506 $a Abstract freely available; full-text restricted to subscribers or individual document purchasers.
510 0 $a Compendex
510 0 $a INSPEC
510 0 $a Google scholar
510 0 $a Google book search
520 3 $a As 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.
530 $a Also available in print.
538 $a Mode of access: World Wide Web.
538 $a System requirements: Adobe Acrobat Reader.
588 $a Title from PDF title page (viewed on May 29, 2019).
650 0 $a Computer networks. $3 528577
650 0 $a Electronic data processing $x Distributed processing. $3 528325
650 0 $a Computer algorithms. $3 528448
650 0 $a Fault-tolerant computing $v Congresses. $3 674932 $3 733607
653 $a consensus
653 $a network topology
653 $a message-passing systems
653 $a asynchronous systems
653 $a synchronous systems
653 $a topological conditions
653 $a broadcast
653 $a reliable message transmission
653 $a local adversary
653 $a general adversary
700 1 $a Tseng, Lewis, $e author. $3 1253100
776 0 8 $i Print version: $z 9781681735689 $z 9781681735665
830 0 $a Synthesis digital library of engineering and computer science. $3 598254
830 0 $a Synthesis lectures on distributed computing theory ; $v $ 11. $x 2155-1634 $3 974998
856 4 0 $3 Abstract with links to full text $u https://doi.org/10.2200/S00918ED1V01Y201904DCT016
856 4 2 $3 Abstract with links to resource $u https://ieeexplore.ieee.org/servlet/opac?bknumber=8715843