  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.
