Browse wiki

From Navigators

Jump to: navigation, search
Publication:Moniz09healer
Abstract Wireless ad-hoc networks are being increas … 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. y assuring termination with probability 1.
Author Henrique Moniz + , Nuno Ferreira Neves + , Miguel Correia + , Paulo Verissimo +
Booktitle Proceedings of the 23rd International Symposium on Distributed Computing (DISC 2009), pages 63-77  +
Key Moniz09healer  +
Month sep  +
NumPubDate 2,009.09  +
ResearchLine Fault And Intrusion Tolerance in Open Distributed Systems (FIT) +
Title Randomization can be a Healer: Consensus with Dynamic Omission Failures  +
Type inproceedings  +
Url http://www.navigators.di.fc.ul.pt/archive/papers/moniz09healer.pdf  +
Year 2009  +
Categories Publication  +
Modification¬†dateThis property is a special property in this wiki. 14 January 2013 14:41:01  +
hide properties that link here 
  No properties link to this page.
 

 

Enter the name of the page to start browsing from.
Views
Personal tools
Toolbox
Navigators toolbox