Accession Number:

ADA558910

Title:

Matrix Representation of Iterative Approximate Byzantine Consensus in Directed Graphs

Descriptive Note:

Technical rept.

Corporate Author:

ILLINOIS UNIV AT URBANA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

Personal Author(s):

Report Date:

2012-03-08

Pagination or Media Count:

18.0

Abstract:

This paper presents a proof of correctness of an iterative approximate Byzantine consensus IABC algorithm for directed graphs. The iterative algorithm allows fault- free nodes to reach approximate consensus despite the presence of up to f Byzantine faults. Necessary conditions on the underlying network graph for the existence of a correct IABC algorithm were shown in our recent work 15, 16. 15 also analyzed a specific IABC algorithm and showed that it performs correctly in any network graph that satisfies the necessary condition, proving that the necessary condition is also sufficient. In this paper, we present an alternate proof of correctness of the IABC algorithm using a familiar technique based on transition matrices 9, 3, 17, 19. The key contribution of this paper is to exploit the following observation for a given evolution of the state vector corresponding to the state of the fault-free nodes many alternate state transition matrices may be chosen to model that evolution correctly. For a given state evolution, we identify one approach to suitably design the transition matrices so that the standard tools for proving convergence can be applied to the Byzantine fault-tolerant algorithm as well. In particular, the transition matrix for each iteration is designed such that each row of the matrix contains a large enough number of elements that are bounded away from 0.

Subject Categories:

  • Numerical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE