Byzantine broadcast in point-to-point networks using local linear coding

ABSTRACT

The goal of Byzantine Broadcast (BB) is to allow a set of fault-free nodes to agree on information that a source node wants to broadcast to them, in the presence of Byzantine faulty nodes. We consider design of efficient algorithms for BB in synchronous point-to-point networks, where the rate of transmission over each communication link is limited by its "link capacity". The throughput of a particular BB algorithm is defined as the average number of bits that can be reliably broadcast to all fault-free nodes per unit time using the algorithm without violating the link capacity constraints. The capacity of BB in a given network is then defined as the supremum of all achievable BB throughputs in the given network, over all possible BB algorithms.

We develop NAB - a Network-Aware BB algorithm - for tolerating f faults in arbitrary point-to-point networks consisting of f ≥ 3f+1 nodes and having ≥ 2f+1 directed node disjoint paths from each node i to each node j. We also prove an upper bound on the capacity of BB, and conclude that NAB can achieve throughput at least 1/3 of the capacity. When the network satisfies an additional condition, NAB can achieve throughput at least 1/2 of the capacity. To the best of our knowledge, NAB is the first algorithm that can achieve a constant fraction of capacity of Byzantine Broadcast (BB) in general point-to-point networks.

References

1. Z. Beerliova-Trubiniova and M. Hirt. Efficient multi-party computation with dispute control. In IACR Theory of Cryptography Conference (TCC), 2006.
2. Z. Beerliova-Trubiniova and M. Hirt. Perfectly-secure mpc with linear communication complexity. In IACR Theory of Cryptography Conference (TCC), 2008.
3. P. Berman, J. A. Garay, and K. J. Perry. Bit optimal distributed consensus. In Computer science. Plenum Press, 1992.
4. N. Cai and R. W. Yeung. Network error correction, part II: Lower bounds. Communications in Information and Systems, 2006.
5. M. Castro and B. Liskov. Practical Byzantine fault tolerance. In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 1999.
6. B. A. Coan and J. L. Welch. Modular construction of a Byzantine agreement protocol with optimal message bit complexity. Journal of Information and Computation, 1992.
7. M. J. Fischer, N. A. Lynch, and M. Merritt. Easy impossibility proofs for distributed consensus problems. In ACM symposium on Principles of Distributed Computing (PODC), 1985.
8. T. Ho, B. Leong, R. Koetter, M. Medard, M. Effros, and D. Karger. Byzantine modification detection in multicast networks using randomized network coding (extended version). Technical report, (http://www.its.caltech.edu/tho/multicast.ps), 2004.
9. S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. Medard. Resilient network coding in the presence of Byzantine adversaries. In IEEE International Conference on Computer Communications (INFOCOM), 2007.
10. V. King and J. Saia. Breaking the O(n²) bit barrier: Scalable Byzantine agreement with an adaptive adversary. In ACM symposium on Principles of Distributed Computing (PODC), 2010.
11. L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Transaction on Programming Languages and Systems, 1982.
12. S.-Y. Li, R. Yeung, and N. Cai. Linear network coding. IEEE Transactions on Information Theory, 2003.
13. G. Liang and N. Vaidya. Capacity of Byzantine agreement with finite link capacity. In IEEE International Conference on Computer Communications (INFOCOM), 2011.
14. G. Liang and N. Vaidya. Error-free multi-valued consensus with Byzantine failures. In ACM Symposium on Principles of Distributed Computing (PODC), 2011.
15. G. Liang and N. Vaidya. Byzantine broadcast in point-to-point networks using local linear coding. Technical report, arXiv (http://arxiv.org/abs/1106.1845), June 2011 (revised May 2012).
16. E. M. Palmer. On the spanning tree packing number of a graph: a survey. Journal of Discrete Mathematics, 2001.
17. C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Courier Dover Publications, 1998.
18. A. Patra and C. P. Rangan. Communication optimal multi-valued asynchronous Byzantine agreement with optimal resilience. Cryptology ePrint Archive, 2009.
19. M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM (JACM), 1980.
20. A. Silberschatz, P. B. Galvin, and G. Gagne. Operating System Concepts, chapter 17 Distributed File Systems. Addison-Wesley, 1994.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications