| 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 +
|
