Consider a synchronous point-to-point network of n nodes connected by directed links, wherein each node has a binary input. This paper proves a tight necessary and sucient condition on the underlying communication topology for achieving Byzantine consensus among these nodes in the presence of up to f Byzantine faults. We derive a necessary condition, and then we provide a constructive proof of suciency by presenting a Byzantine consensus algorithm for directed graphs that satisfy the necessary condition.
This work addresses Byzantine vector consensus, wherein the input at each process is a d-dimensional vector of reals, and each process is required to decide on a decision vector that is in the convex hull of the input vectors at the fault-free processes [9,12]. The input vector at each process may also be viewed as a point in the d-dimensional Euclidean space R d , where di¾?>i¾?0 is a finite integer. Recent work [9,12] has addressed Byzantine vector consensus, and presented algorithms with optimal fault tolerance in complete graphs. This paper considers Byzantine vector consensus in incomplete graphs using a restricted class of iterative algorithms that maintain only a small amount of memory across iterations. For such algorithms, we prove a necessary condition, and a sufficient condition, for the graphs to be able to solve the vector consensus problem iteratively. We present an iterative Byzantine vector consensus algorithm, and prove it correct under the sufficient condition. The necessary condition presented in this paper for vector consensus does not match with the sufficient condition for di¾?>i¾?1; thus, a weaker condition may potentially suffice for Byzantine vector consensus. We study a graph-theoretic property known as robustness, which plays a key role in the behavior of certain classes of dynamics on networks (such as resilient consensus and contagion). This property is much stronger than other graph properties such as connectivity and minimum degree, in that one can construct graphs with high connectivity and minimum degree but low robustness. In this paper, we investigate the robustness of common random graph models for complex networks (Erdős-Renyi, geometric random, and preferential attachment graphs). We show that the notions of connectivity and robustness coincide on these random graph models: the properties share the same threshold function in the Erdős-Renyi model, cannot be very different in the geometric random graph model, and are equivalent in the preferential attachment model. This indicates that a variety of purely local diffusion dynamics will be effective at spreading information in such networks. In this work, we consider a generalized fault model [7,9,5] that can be used to represent a wide range of failure scenarios, including correlated failures and non-uniform node reliabilities. Under the generalized fault model, we explore iterative approximate Byzantine consensus (IABC) algorithms [15] in arbitrary directed networks. We prove a tight necessary and sufficient condition on the underlying communication graph for the existence of IABC algorithms. This paper proves a necessary and sufficient condition for the existence of iterative, algorithms that achieve approximate Byzantine consensus in arbitrary directed graphs, where each directed edge represents a communication channel between a pair of nodes. The class of iterative algorithms considered in this paper ensures that, after each iteration of the algorithm, the state of each fault-free node remains in the convex hull of the states of the fault-free nodes at the end of the previous iteration. The following convergence requirement is imposed: for any e > 0, after a sufficiently large number of iterations, the states of the fault-free nodes are guaranteed to be within e of each other. To the best of our knowledge, tight necessary and sufficient conditions for the existence of such iterative consensus algorithms in synchronous arbitrary point-to-point networks in presence of Byzantine faults, have not been developed previously. The methodology and results presented in this paper can also be extended to asynchronous systems. This paper addresses the problem of resilient consensus in the presence of misbehaving nodes. Although it is typical to assume knowledge of at least some nonlocal information when studying secure and fault-tolerant consensus algorithms, this assumption is not suitable for large-scale dynamic networks. To remedy this, we emphasize the use of local strategies to deal with resilience to security breaches. We study a consensus protocol that uses only local information and we consider worst-case security breaches, where the compromised nodes have full knowledge of the network and the intentions of the other nodes. We provide necessary and sufficient conditions for the normal nodes to reach consensus despite the influence of the malicious nodes under different threat assumptions. These conditions are stated in terms of a novel graph-theoretic property referred to as network robustness. This paper addresses the problem of resilient in-network consensus in the presence of misbehaving nodes. Secure and fault-tolerant consensus algorithms typically assume knowledge of nonlocal information; however, this assumption is not suitable for large-scale dynamic networks. To remedy this, we focus on local strategies that provide resilience to faults and compromised nodes. We design a consensus protocol based on local information that is resilient to worst-case security breaches, assuming the compromised nodes have full knowledge of the network and the intentions of the other nodes. We provide necessary and sufficient conditions for the normal nodes to reach asymptotic consensus despite the influence of the misbehaving nodes under different threat assumptions. We show that traditional metrics such as connectivity are not adequate to characterize the behavior of such algorithms, and develop a novel graph-theoretic property referred to as network robustness. Network robustness formalizes the notion of redundancy of direct information exchange between subsets of nodes in the network, and is a fundamental property for analyzing the behavior of certain distributed algorithms that use only local information. 