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 - Aug 20 2012
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
CountryPortugal
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