Capacity of Byzantine Agreement: Tight Bound for the Four Node Network

Abstract

In this report, we consider the problem of maximizing the throughput of Byzantine agreement. Byzantine agreement is a classical problem in distributed computing, with initial solutions presented in the seminal work of Pease, Shostak and Lamport. There has also been more recent work on designing multicast algorithms that can survive Byzantine attacks. 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 original definition of Byzantine agreement in our discussion. In particular, we consider a network with one node designated as the sender or source, and other nodes designated as the peers. The goal here is for all the fault-free nodes to "agree on" the value being sent by the sender.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 2010
Accession Number
ADA555086

Entities

People

  • Guanfeng Liang
  • Nitin H. Vaidya

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Agreements
  • Algorithms
  • Data Transmission
  • Demographic Cohorts
  • Detection
  • Distributed Computing
  • Equations
  • Error Detection Codes
  • False Alarms
  • Illinois
  • Information Operations
  • Military Research
  • Network Topology
  • Numbers
  • Rational Numbers
  • Throughput
  • Warning Systems

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Networking
  • Theoretical Analysis.