Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding

摘要

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 point-to-point networks where the rate of transmission over each communication link is limited by its 'link capacity'. Given an algorithm A to solve BB in a network G, let us denote by t(G, L,A) the worst- case execution time of A without violating link capacity constraints in G, when L is the size of the input at the source node. Then, we define the capacity of BB in network G as the supremum of L/t(G, L,A) over all L and all possible BB algorithms A. We prove upper bounds on the capacity of Byzantine broadcast over arbitrary point-to-point networks. An algorithmis then given that solves BB at a rate of at least 1/2 or 1/3 of the capacity depending on different conditions the underlying network satisfies. This Byzantine Broadcast algorithm tolerates up to f faulty nodes as long as the total number of nodes is at least 3 f +1 and the connectivity is at least 2 f + 1. To the best of our knowledge, ours is the first algorithm that achieves a constant fraction of capacity of BB in general point-to-point networks.