Matrix Representation of Iterative Approximate Byzantine Consensus in Directed Graphs
Nitin H. Vaidya · 2012
This paper presents a proof of correctness of an iterative approximate Byzantine consensus (IABC) algorithm for directed graphs.The iterative algorithm allows faultfree nodes to reach approximate conensus 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].