Randomization can be a healer: Consensus with dynamic omission failures

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

Research output: Contribution to journalArticlepeer-review

Abstract

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 novelway 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 κ is the number of processes required to decide, eventually assuring termination with probability 1. © 2010 Springer-Verlag.
Original languageEnglish (US)
Pages (from-to)165-175
Number of pages11
JournalDistributed Computing
Volume24
Issue number3-4
DOIs
StatePublished - Nov 1 2011
Externally publishedYes

ASJC Scopus subject areas

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

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

Cite this