cs.DC
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 point to point communication model, it is well known 7 that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among n nodes in the presence of up to f Byzantine faulty nodes n ge 3f 1 and vertex connectivity at least 2f 1 . In the classical point to point 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 point to point 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 least lfloor 3f 2 rfloor 1 and minimum node degree at least 2f . Observe that the local broadcast model results in a lower requirement for connectivity and the number of nodes n , as compared to the point to point communication model. We extend the above results to a hybrid model that allows some of the Byzantine faulty nodes to equivocate. The hybrid model bridges the gap between the point to point and local broadcast models, and helps to precisely characterize the trade off between equivocation and network requirements.