Accession Number:

ADA555091

Title:

Capacity of Byzantine Consensus with Capacity-Limited Point-to-Point Links

Descriptive Note:

Conference paper

Corporate Author:

ILLINOIS UNIV AT URBANA-CHAMPAIGN

Personal Author(s):

Report Date:

2011-03-31

Pagination or Media Count:

14.0

Abstract:

In our previous work 5, 4, 6,we investigated the capacity of the broadcast version of the Byzantine agreement problem3 in networks where communications links are capacity limited. In this report, we are going to study capacity of the consensus version of the Byzantine agreement problem. The Byzantine consensus problem considers n nodes, namely P1, ..., Pn, of which at most f nodes may be faulty and deviate from the algorithm in arbitrary fashion. Each node Pi is given an input value vi, and they want to agree on a value v such that the following properties are satisfied Termination every fault-free Pi eventually decides on an output value v i , Consistency the output values of all fault-free nodes are equal, i.e., for every fault-free node Pi, v i v for some v , Validity if every fault-free Pi holds the same input vi v for some v, then v v.

Subject Categories:

  • Computer Systems
  • Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE