Name
Abstract | ||
|---|---|---|
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 hyper- graph), 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 ev- ery three processes in the network (i.e. a complete (2, 3)-uniform hyper- graph), n ≥ 2t + 1 is necessary and sufficient for Byzantine agreement. In this paper, we show that optimum tolerance of n ≥ 2t +1 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 =2 t +1 , 2 3 t3 + Θ(t2) 3-hyperedges are necessary and suffi- cient 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. |
Year | Venue | Field |
|---|---|---|
2004 | international symposium on distributed computing | Discrete mathematics,Computer science,Hypergraph,Constraint graph,Byzantine architecture,Initial value problem,Unicast,Binary Value,Synchronous network,Communications protocol |
DocType | Citations | PageRank |
Conference | 7 | 0.45 |
References | Authors | |
10 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| D. V. S. Ravikant | 1 | 8 | 1.16 |
| Muthuramakrishnan Venkitasubramaniam | 2 | 1442 | 73.06 |
| V. Srikanth | 3 | 8 | 0.82 |
| K. Srinathan | 4 | 270 | 19.17 |
| C. Pandu Rangan | 5 | 1434 | 149.57 |