Reaching approximate Byzantine consensus with multi-hop communication

Lili Su, Nitin H. Vaidya

Research output: Contribution to journalArticlepeer-review


We are interested in approximate Byzantine consensus problem, wherein all the fault-free processes reach consensus asymptotically (approximately in finite time). In particular, we focus on the algorithms under which each process communicates with other processes that are up to l hops away and maintains minimal states across iterations. For a given l, we identify a necessary and sufficient condition on the network structure for the existence of iterative algorithms of interest. 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)
Pages (from-to)352-368
Number of pages17
JournalInformation and Computation
StatePublished - Aug 2017


  • Approximate agreement
  • Bounded length communication paths
  • Byzantine protocols
  • Synchronous systems

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


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

Cite this