Byzantine Consensus under Local Broadcast Model: Tight Sufficient Condition
share
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 NaqviMaster, NaqviBroadcast it was shown that in the local broadcast model the communication graph must be (3f/2+1)-connected and have degree at least 2f to achieve Byzantine Consensus. In this work we show that this network condition is tight.
READ FULL TEXT