Byzantine Consensus under Local Broadcast Model: Tight Sufficient Condition

Abstract

In this work we consider Byzantine Consensus on undirected communication graphs under the local broadcast model. In the classical point-to-point communication model the messages exchanged between two nodes $u,v$ on an edge $uv$ of $G$ are private. This allows a faulty node to send conflicting information to its different neighbours, a property called equivocation. In contrast, in the local broadcast communication model considered here, a message sent by node $u$ is received identically by all of its neighbours. This restriction to broadcast messages provides non-equivocation even for faulty nodes. In prior results [10, 11] it was shown that in the local broadcast model the communication graph must be $(\lfloor 3f/2\rfloor +1)$-connected and have degree at least $2f$ to achieve Byzantine Consensus. In this work we show that this network condition is tight.

Some minor typos in arxiv abstract and the report. Also added an NSF grant