Reaching approximate byzantine consensus with multi-hop communication

Lili Su, Nitin Vaidya

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

Abstract

We address the problem of reaching approximate consensus in the presence of Byzantine faults in a synchronous system. We analyze iterative algorithms that maintain minimal state, and impose the constraint that in each iteration the nodes may only communicate with other nodes that are up to l hops away. For a given l, we prove a necessary and sufficient condition on the network structure for the existence of correct iterative algorithms that achieve approximate Byzantine consensus. We prove sufficiency of the condition by designing a correct algorithm, which uses a trim function based on a minimal messages cover property introduced in this paper. Our necessary and sufficient condition generalizes the tight condition identified in prior work for l = 1. For l ≥ l, where l is the length of a longest cycle-free path in the given network, our condition is equivalent to the necessary and sufficient conditions for exact consensus in undirected and directed networks both.

Original languageEnglish (US)
Title of host publicationStabilization, Safety and Security of Distributed Systems - 17th International Symposium, SSS 2015, Proceedings
EditorsAndrzej Pelc, Alexander A. Schwarzmann
PublisherSpringer-Verlag Berlin Heidelberg
Pages21-35
Number of pages15
ISBN (Print)9783319217406
DOIs
StatePublished - 2015
Event17th International Symposium on Stabilization, Safety and Security of Distributed Systems, SSS 2015 - Edmonton, Canada
Duration: Aug 18 2015Aug 21 2015

Publication series

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

Other

Other17th International Symposium on Stabilization, Safety and Security of Distributed Systems, SSS 2015
CountryCanada
CityEdmonton
Period8/18/158/21/15

Keywords

  • Approximate byzantine consensus
  • Bounded length communication paths
  • Incomplete network
  • Iterative algorithm
  • Synchronous system

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Reaching approximate byzantine consensus with multi-hop communication'. Together they form a unique fingerprint.

Cite this