Complexity of Multi-Value Byzantine Agreement

Abstract

In this paper, we consider the problem of maximizing the throughput of Byzantine agreement, given that the sum capacity of all links in between nodes in the system is finite. Byzantine agreement (BA) is a classical problem in distributed computing, with initial solutions presented in the seminal work of Pease, Shostak and Lamport. Many variations on the Byzantine agreement problem have been introduced in the past, with some of the variations also called consensus. We will use the following definition of Byzantine agreement (Byzantine general problem): Consider a network with one node designated as the sender or source (S), and the other nodes designated as the peers. The goal of Byzantine agreement is for all the fault-free nodes to agree on the value being sent by the sender, despite the possibility that some of the nodes may be faulty. Our goal in this work is to design algorithms that can achieve optimal throughput of agreement.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 11, 2010
Accession Number
ADA555114

Entities

People

  • Guanfeng Liang
  • Nitin H. Vaidya

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Agreements
  • Algorithms
  • Communication Channels
  • Computer Programming
  • Damage Detection
  • Demographic Cohorts
  • Detection
  • Distributed Computing
  • Engineering
  • Fault Tolerance
  • Graph Theory
  • Illinois
  • Information Operations
  • Mesh Networks
  • Probability
  • Sequences
  • Throughput

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.