Brief announcement: Capacity of Byzantine agreement with finite link capacity - Complete characterization of four-node networks

Guanfeng Liang, Nitin Vaidya

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

Abstract

In this paper, 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, with initial solutions presented in the seminal work of Pease, Shostak and Lamport. The notion of throughput here is similar to that used in the networking/ communications literature on unicast or multicast traffic. We identify necessary conditions for an agreement throughput of R to be achievable. We also provide tight sufficient conditions by construction for agreement throughput R in four-node networks.

Original languageEnglish (US)
Title of host publicationPODC'10 - Proceedings of the 2010 ACM Symposium on Principles of Distributed Computing
Pages396-397
Number of pages2
DOIs
StatePublished - 2010
Externally publishedYes
Event29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010 - Zurich, Switzerland
Duration: Jul 25 2010Jul 28 2010

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2010
Country/TerritorySwitzerland
CityZurich
Period7/25/107/28/10

Keywords

  • Byzantine agreement

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Brief announcement: Capacity of Byzantine agreement with finite link capacity - Complete characterization of four-node networks'. Together they form a unique fingerprint.

Cite this