Accession Number:

ADA555090

Title:

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

Descriptive Note:

Conference paper

Corporate Author:

ILLINOIS UNIV AT URBANA-CHAMPAIGN

Personal Author(s):

Report Date:

2011-11-03

Pagination or Media Count:

24.0

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 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.

Subject Categories:

  • Computer Systems
  • Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE