On byzantine agreement over (2, 3)-uniform Hypergraphs

In a Byzantine agreement protocol, a synchronous network of n interconnected processes of which t may be faulty, starts with an initial binary value associated with each process; after exchanging messages, all correct processes must agree on one of the initial values of the non-faulty processes. If the network consists of only unicast channels (i.e. a 2-uniform hypergraph), then Byzantine agreement is possible if and only if n≥ 3t + 1 (Pease et. al. [11]). However, Fitzi and Maurer ([7]) 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 + 1 is necessary and sufficient for Byzantine agreement. In this paper, we show that optimum tolerance of n≥ 2t + l 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/3t3 +θ(t2)) 3-hyperedges are necessary and sufficient to enable Byzantine agreement. This settles an open problem raised by Fitzi and Maurer in [7]. An efficient protocol is also given whenever Byzantine agreement is possible. © Springer-Verlag 2004.