Capacity of byzantine agreement with finite link capacity

Guanfeng Liang, Nitin Vaidya

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

Abstract

We consider the problem of maximizing the throughput of Byzantine agreement, when communication links have finite capacity. Byzantine agreement is a classical problem in distributed computing. In existing literature, the communication links are implicitly assumed to have infinite capacity. The problem changes significantly when the capacity of links is finite. We define the throughput and capacity of agreement, and identify necessary conditions of achievable agreement throughputs. We propose an algorithm structure for achieving agreement capacity in general networks. We also introduce capacity achieving algorithms for two classes of networks: (i) arbitrary four-node networks with at most 1 failure; and (ii) symmetric networks of arbitrary size.

Original languageEnglish (US)
Title of host publication2011 Proceedings IEEE INFOCOM
Pages739-747
Number of pages9
DOIs
StatePublished - 2011
Externally publishedYes
EventIEEE INFOCOM 2011 - Shanghai, China
Duration: Apr 10 2011Apr 15 2011

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherIEEE INFOCOM 2011
Country/TerritoryChina
CityShanghai
Period4/10/114/15/11

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Capacity of byzantine agreement with finite link capacity'. Together they form a unique fingerprint.

Cite this