Iterative approximate byzantine consensus under a generalized fault model

Lewis Tseng, University of Illinois Urbana-Champaign
Nitin Vaidya, The Grainger College of Engineering

Abstract

In this work, we consider a generalized fault model [7,9,5] that can be used to represent a wide range of failure scenarios, including correlated failures and non-uniform node reliabilities. Under the generalized fault model, we explore iterative approximate Byzantine consensus (IABC) algorithms [15] in arbitrary directed networks. We prove a tight necessary and sufficient condition on the underlying communication graph for the existence of IABC algorithms. We propose a new IABC algorithm for the generalized fault model, and present a transition matrix-based proof to show the correctness of the proposed algorithm. While transition matrices have been used to prove correctness of non-fault-tolerant consensus [6], this paper is the first to extend the technique to Byzantine fault-tolerant algorithms. © Springer-Verlag 2013.