2019/11/13 by Muhammad Samir Khan, Khan, Muhammad Samir, Lewis Tseng +3
Computer Science · #Cooperative Communication and Network Coding #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Opportunistic and Delay-Tolerant Networks #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1911.07298
openalex publication_date 2019/11/13 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
We consider Byzantine consensus in a synchronous system where nodes are\nconnected by a network modeled as a directed graph, i.e., communication links\nbetween neighboring nodes are not necessarily bi-directional. The directed\ngraph model is motivated by wireless networks wherein asymmetric communication\nlinks can occur. In the classical point-to-point communication model, a message\nsent on a communication link is private between the two nodes on the link. This\nallows a Byzantine faulty node to equivocate, i.e., send inconsistent\ninformation to its neighbors. This paper considers the local broadcast model of\ncommunication, wherein transmission by a node is received identically by all of\nits outgoing neighbors. This allows such neighbors to detect a faulty node's\nattempt to equivocate, effectively depriving the faulty nodes of the ability to\nsend conflicting information to different neighbors.\n Prior work has obtained sufficient and necessary conditions on undirected\ngraphs to be able to achieve Byzantine consensus under the local broadcast\nmodel. In this paper, we obtain tight conditions on directed graphs to be able\nto achieve Byzantine consensus with binary inputs under the local broadcast\nmodel. The results obtained in the paper provide insights into the trade-off\nbetween directionality of communication and the ability to achieve consensus.\n