“Randomization can be a Healer: Consensus with Dynamic Omission Failures”

From Navigators

Jump to: navigation, search

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

in Proceedings of the 23rd International Symposium on Distributed Computing (DISC 2009), pages 63-77, Sept. 2009.

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 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 \le \lceil \frac{n}{2} \rceil (n-k)+k-2$, where $k$ is the number of processes required to decide, eventually assuring termination with probability 1.

Download paper

Download Randomization can be a Healer: Consensus with Dynamic Omission Failures

Export citation



Research line(s): Fault And Intrusion Tolerance in Open Distributed Systems (FIT)

Personal tools
Navigators toolbox