Randomization can be a healer: Consensus with dynamic omission failures

Henrique Moniz, Nuno Ferreira Neves, Miguel Correia, Paulo Veríssimo

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

11 Scopus citations


Wireless ad-hoc networks are being increasingly used in diverse contexts, ranging from casual meetings to disaster recovery operations. A promising approach is to model these networks as distributed systems prone to dynamic communication failures. This captures transitory disconnections in communication due to phenomena like interference and collisions, and permits an efficient use of the wireless broadcasting medium. This model, however, is bound by the impossibility result of Santoro and Widmayer, which states that, even with strong synchrony assumptions, there is no deterministic solution to any non-trivial form of agreement if n-1 or more messages can be lost per communication round in a system with n processes. In this paper we propose a novel way to circumvent this impossibility result by employing randomization. We present a consensus protocol that ensures safety in the presence of an unrestricted number of omission faults, and guarantees progress in rounds where such faults are bounded by f≤ ⌈ n/2 ⌉ (n-k)+k-2 , where k is the number of processes required to decide, eventually assuring termination with probability 1. © 2009 Springer Berlin Heidelberg.
Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number of pages15
StatePublished - Dec 1 2009
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Randomization can be a healer: Consensus with dynamic omission failures'. Together they form a unique fingerprint.

Cite this