Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding
ILLINOIS UNIV AT URBANA-CHAMPAIGN
Pagination or Media Count:
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 tG, 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 LtG, 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 12 or 13 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.
- Computer Systems
- Radio Communications