Low complexity Byzantine-resilient consensus

Miguel Correia, Nuno Ferreira Neves, Lau Cheuk Lung, Paulo Veríssimo

Research output: Contribution to journalArticlepeer-review

34 Scopus citations


The application of the tolerance paradigm to security - intrusion tolerance - has been raising a reasonable amount of attention in the dependability and security communities. In this paper we present a novel approach to intrusion tolerance. The idea is to use privileged components - generically designated by wormholes - to support the execution of intrusion-tolerant protocols, often called Byzantine-resilient in the literature. The paper introduces the design of wormhole-aware intrusion-tolerant protocols using a classical distributed systems problem: consensus. The system where the consensus protocol runs is mostly asynchronous and can fail in an arbitrary way, except for the wormhole, which is secure and synchronous. Using the wormhole to execute a few critical steps, the protocol manages to have a low time complexity: in the best case, it runs in two rounds, even if some processes are malicious. The protocol also shows how often theoretical partial synchrony assumptions can be substantiated in practical distributed systems. The paper shows the significance of the TTCB as an engineering paradigm, since the protocol manages to be simple when compared with other protocols in the literature. © Springer-Verlag 2005.
Original languageEnglish (US)
Pages (from-to)237-249
Number of pages13
JournalDistributed Computing
Issue number3
StatePublished - Mar 1 2005
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2021-03-16

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computational Theory and Mathematics
  • Theoretical Computer Science
  • Computer Networks and Communications


Dive into the research topics of 'Low complexity Byzantine-resilient consensus'. Together they form a unique fingerprint.

Cite this