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

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

2011-06-09

arxiv.org/abs/1106.1845v2

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-580650