Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

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.

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

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

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

4. Asynchronous crash fault tolerance -- 4.1. Conditions relations and implications -- 4.2. Iterative approximate consensus -- 4.3. General approximate consensus

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

6. relay depth and approximate consensus -- 6.1. Iterative k-hop algorithm -- 6.2. Asynchronous crash fault tolerance -- 6.3. Synchronous byzantine fault tolerance

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

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

Compendex

INSPEC

Google scholar

Google book search

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.

Also available in print.

Title from PDF title page (viewed on May 29, 2019).