Name
Abstract | ||
|---|---|---|
We study the completion time of broadcast operations on Static Ad-Hoc Wireless Networks in presence of unpredictable and dynamical faults. As for oblivious fault-tolerant distributed protocols, we provide an Ω(Dn) lower bound where n is the number of nodes of the network and D is the source eccentricity in the fault-free part of the network. Rather surprisingly, this lower bound implies that the
simple Round-Robin protocol, working in O(Dn) time, is an optimal fault-tolerant oblivious protocol. Then, we demonstrate that networks of o(n/ log n) maximum in-degree admit faster oblivious protocols. Indeed, we derive an oblivious protocol having O(D minn, Δ log n) completion time on any network of maximum in-degree Δ. Finally, we address the question whether adaptive protocols can be faster than oblivious ones. We show that the answer is negative at least in the general setting: we indeed
prove an Ω(Dn) lower bound when
D = Q</font
>( Ö</font
>n )
D = \Theta \left( {\sqrt n } \right)
. This clearly implies that no (adaptive) protocol can achieve, in general, o(Dn) completion time.
|
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/j.jpdc.2003.09.002 | Journal of Parallel and Distributed Computing |
Keywords | Field | DocType |
optimal fault-tolerant oblivious protocol,oblivious protocol,fault-tolerant broadcasting,general setting,round robin,static ad-hoc wireless networks,completion time,simple round-robin protocol,oblivious fault-tolerant,maximum in-degree,log n,adaptive protocol,wireless networks,fault tolerant,lower bound,ad hoc wireless network,wireless network,broadcast | Wireless network,Broadcasting,Binary logarithm,Fault tolerant broadcasting,Computer science,Upper and lower bounds,Eccentricity (behavior),Computer network,Distributed computing | Conference |
Volume | Issue | ISSN |
64 | 1 | 0743-7315 |
Citations | PageRank | References |
34 | 1.48 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea E. F. Clementi | 1 | 1168 | 85.30 |
| Angelo Monti | 2 | 671 | 46.93 |
| Riccardo Silvestri | 3 | 1324 | 90.84 |