We consider Byzantine consensus in a synchronous system where nodes are connected by a network modeled as a directed graph, i.e., communication links between neighboring nodes are not necessarily bidirectional. The directed graph model is motivated by wireless networks wherein asymmetric communication links can occur. In the classical pointtopoint communication model, a message sent on a communication link is private between the two nodes on the link. This allows a Byzantine faulty node to equivocate, i.e., send inconsistent information to its neighbors. This paper considers the local broadcast model of communication, wherein transmission by a node is received identically by all of its outgoing neighbors, effectively depriving the faulty nodes of the ability to equivocate. Prior work has obtained sufficient and necessary conditions on undirected graphs to be able to achieve Byzantine consensus under the local broadcast model. In this paper, we obtain tight conditions on directed graphs to be able to achieve Byzantine consensus with binary inputs under the local broadcast model. The results obtained in the paper provide insights into the tradeoff between directionality of communication links and the ability to achieve consensus.
Exact Byzantine Consensus on Undirected Graphs under Local Broadcast Model
This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous. Under the classical pointtopoint communication model, it is wellknown that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among n nodes in the presence of up to ƒ Byzantine faulty nodes: n & 3 #8805; 3 ≥ ƒ+ 1 and vertex connectivity at least 2 ƒ + 1. In the classical pointtopoint communication model, it is possible for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors.
This paper considers the local broadcast model. In contrast to the pointtopoint communication model, in the local broadcast model, messages sent by a node are received identically by all of its neighbors. Thus, under the local broadcast model, attempts by a node to send conflicting information can be detected by its neighbors. Under this model, we show that the following two conditions are both necessary and sufficient for Byzantine consensus: vertex connectivity at more »
 Award ID(s):
 1733872
 Publication Date:
 NSFPAR ID:
 10184837
 Journal Name:
 ACM Symposium on Principles in Distributed Computing
 Page Range or eLocationID:
 327 to 336
 Sponsoring Org:
 National Science Foundation
More Like this


Jurdziński, T ; Schmid, S (Ed.)In the multiparty equality problem, each of the n nodes starts with a kbit input. If there is a mismatch between the inputs, then at least one node must be able to detect it. The cost of a multiparty equality protocol is the total number of bits sent in the protocol. We consider the problem of minimizing this communication cost under the local broadcast model for the case where the underlying communication graph is undirected. In the local broadcast model of communication, a message sent by a node is received identically by all of its neighbors. This is in contrast to the classical pointtopoint communication model, where a message sent by a node to one of its neighbors is received only by its intended recipient. Under pointtopoint communication, there exists a simple protocol which is competitive within a factor 2 of the lower bound [1]. In this protocol, a rooted spanning tree is fixed and each node sends its entire input to its parent in the tree. On receiving a value from its child, a node compares it against its own input to check if the two values match. Ignoring lower order additive terms, a more complicated protocol comes withinmore »

Gilbert, Seth (Ed.)Byzantine consensus is a classical problem in distributed computing. Each node in a synchronous system starts with a binary input. The goal is to reach agreement in the presence of Byzantine faulty nodes. We consider the setting where communication between nodes is modelled via an undirected communication graph. In the classical pointtopoint communication model all messages sent on an edge are private between the two endpoints of the edge. This allows a faulty node to equivocate, i.e., lie differently to its different neighbors. Different models have been proposed in the literature that weaken equivocation. In the local broadcast model, every message transmitted by a node is received identically and correctly by all of its neighbors. In the hypergraph model, every message transmitted by a node on a hyperedge is received identically and correctly by all nodes on the hyperedge. Tight network conditions are known for each of the three cases. We introduce a more general model that encompasses all three of these models. In the local multicast model, each node u has one or more local multicast channels. Each channel consists of multiple neighbors of u in the communication graph. When node u sends a message on a channel, itmore »

Byzantine Fault Tolerant (BFT) protocols are designed to ensure correctness and eventual progress in the face of misbehaving nodes [1]. However, this does not prevent negative effects an adversary may have on performance: a faulty node may significantly affect the latency and throughput of the system without being detected. This is especially true in speculative protocols optimized for the bestcase where a single leader can force the protocol into the worst case [3]. Systems like Aardvark [2] that are designed to maximize worstcase performance tolerate byzantine behavior without necessarily detecting who the perpetrator is. By forcing regular view changes, for example, they mitigate the effects of leaders who deliberately delay dissemination of messages, even if this behavior would be difficult to prove to a third party. Byzantine faults, by definition, can be difficult to detect. An error of 'commission', such as a message with a mismatching digest, can be proven. Errors of 'omission', such as delaying or failing to relay a message, as a rule cannot be proven, and the node responsible for these types of omission faults may not appear faulty to all observers. Nevertheless, we observe that they can reliably be detected. Designing protocols that detect and ejectmore »

This paper focuses on showing timemessage tradeoffs in distributed algorithms for fundamental problems such as leader election, broadcast, spanning tree (ST), minimum spanning tree (MST), minimum cut, and many graph verification problems. We consider the synchronous CONGEST distributed computing model and assume that each node has initial knowledge of itself and the identifiers of its neighbors  the socalled KT_1 model  a wellstudied model that also naturally arises in many applications. Recently, it has been established that one can obtain (almost) singularly optimal algorithms, i.e., algorithms that have simultaneously optimal time and message complexity (up to polylogarithmic factors), for many fundamental problems in the standard KT_0 model (where nodes have only local knowledge of themselves and not their neighbors). The situation is less clear in the KT_1 model. In this paper, we present several new distributed algorithms in the KT_1 model that trade off between time and message complexity. Our distributed algorithms are based on a uniform and general approach which involves constructing a sparsified spanning subgraph of the original graph  called a danner  that trades off the number of edges with the diameter of the sparsifier. In particular, a key ingredient of our approach is amore »