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

Guanfeng Liang, Nitin H. Vaidya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationPODC'12 - Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing
Pages319-328
Number of pages10
DOIs
StatePublished - 2012
Externally publishedYes
Event2012 ACM Symposium on Principles of Distributed Computing, PODC'12 - Madeira, Portugal
Duration: Jul 16 2012Jul 18 2012

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other2012 ACM Symposium on Principles of Distributed Computing, PODC'12
Country/TerritoryPortugal
CityMadeira
Period7/16/127/18/12

Keywords

  • broadcast
  • byzantine faults
  • capacity
  • directed graph

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Byzantine broadcast in point-to-point networks using local linear coding'. Together they form a unique fingerprint.

Cite this