## On Byzantine Agreement over (2,3)-Uniform Hypergraphs

### Authors

- Ravikant D V S, Indian Institute of Technology, Madras
- Muthuramakrishnan Venkitasubramaniam, Indian Institute of Technology, Madras
- Srikanth Venkateswaran, Indian Institute of Technology, Madras
- Srinathan Kannan, Indian Institute of Technology, Madras
- Pandurangan Chandrashekaran, Indian Institute of Technology, Madras

### Abstract

Byzantine Agreement is possible
on a network consists of only unicast channels (i.e. a 2-uniform
hypergraph) if and only if n > 3t (Pease et. al. [PSL80]). However,
Fitzi and Maurer ([FM00]) show that if, in addition to all unicast
channels, there exists local broadcast among every three processes in
the network (i.e. a complete (2,3)-uniform hypergraph), n>2t is
necessary and sufficient for Byzantine agreement.
In this paper, we show that optimum tolerance of n>2t can be achieved
even if a substantial fraction of the local broadcast channels are not
available. Specifically, we model the network as a (2,3)-uniform
hypergraph H = (P,E), where P denotes the set of n processes and E is
a set of 2-tuples and/or 3-tuples of processes (edges or
3-hyperedges), wherein each 3-hyperedge represents a local broadcast
among the three processes; we obtain a characterization of the
hypergraphs on which Byzantine agreement is possible. Using this
characterization, we show that for n=2t+1, (2/3t^3 + Theta(t^2))
3-hyperedges are necessary and sufficient to enable Byzantine
agreement. This settles an open problem raised by Fitzi and Maurer in
[FM00]. An efficient protocol is also given whenever Byzantine
agreement is possible.