Lewin Tseng: Exact Byzantine Consensus under Local Broadcast Model

 

Consider the Byzantine consensus problem in a synchronous system where nodes are partially connected. In the classical point-to-point 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 (i.e., no equivocation). This allows such neighbors to detect a faulty node’s attempt to equivocate, effectively depriving the faulty nodes of the ability to send conflicting information to different neighbors. I will present the following two recent works which proved the tight conditions on undirected and directed graphs, respectively, so that Byzantine consensus is feasible under the local broadcast model:

1. PODC 2019: Exact Byzantine Consensus on Undirected Graphs under Local Broadcast Model
Muhammad Samir Khan, Syed Shalan Naqvi, Nitin H. Vaidya

2. OPODIS 2019: Exact Byzantine Consensus on Arbitrary Directed Graphs under Local Broadcast Model

Muhammad Samir Khan, Lewis Tseng and Nitin H. Vaidya