Iterative approximate byzantine consensus under a generalized fault model

Lewis Tseng, Nitin Vaidya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationDistributed Computing and Networking - 14th International Conference, ICDCN 2013, Proceedings
Pages72-86
Number of pages15
DOIs
StatePublished - Dec 1 2013
Event14th International Conference on Distributed Computing and Networking, ICDCN 2013 - Mumbai, India
Duration: Jan 3 2013Jan 6 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7730 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th International Conference on Distributed Computing and Networking, ICDCN 2013
CountryIndia
CityMumbai
Period1/3/131/6/13

Keywords

  • Generalized fault model
  • Graph property
  • Iterative consensus

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Iterative approximate byzantine consensus under a generalized fault model'. Together they form a unique fingerprint.

Cite this