Computer Science

Iterative approximate byzantine consensus under a generalized fault model

Document Type

Conference Paper

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.

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Publication Date

2013

Volume

7730 LNCS

First Page

72

Last Page

86

ISSN

0302-9743

ISBN

9783642356674

DOI

10.1007/978-3-642-35668-1_6

Keywords

generalized fault model, graph property, iterative consensus

APA Citation

Tseng, L., & Vaidya, N. (2013). Iterative approximate byzantine consensus under a generalized fault model. In Distributed Computing and Networking: 14th International Conference, ICDCN 2013, Mumbai, India, January 3-6, 2013. Proceedings 14 (pp. 72-86). Springer Berlin Heidelberg.

Link to Full Text

Share

COinS