Title | ||
---|---|---|
Optimal gossiping in directed geometric radio networks in presence of dynamical faults |
Abstract | ||
---|---|---|
We study deterministic fault-tolerant gossiping protocols in directed Geometric Radio Networks (in short, directed GRN). Unpredictable node and link faults may happen during every time slot of the protocol's execution. We first consider the single-message model where every node can send at most one message per time slot. We provide a protocol that, in any directed GRNGof n nodes, completes gossiping in O(nΔ) time (where Δ is the maximal in-degree of G) and hasmessage complexity O(n2). Both bounds are then shown to be optimal. As for the combined-message model, we give a protocol working in optimal completion time O(DΔ) (where D is the maximal source eccentricity) and message complexity O(Dn). Finally, our protocol performs the (single) broadcast operation within the same optimal time and optimal message complexity O(n). |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-74456-6_39 | MFCS |
Keywords | Field | DocType |
time slot,dynamical fault,optimal message complexity,message complexity o,geometric radio network,maximal in-degree,maximal source eccentricity,combined-message model,optimal completion time,grngof n node,optimal time,hasmessage complexity,fault tolerant,gossip protocol | Broadcasting,Radio networks,Computer science,Eccentricity (behavior),Gossip,Computer network,Unit disk graph,Distributed computing | Conference |
Volume | ISSN | ISBN |
4708 | 0302-9743 | 3-540-74455-X |
Citations | PageRank | References |
3 | 0.40 | 26 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrea E. F. Clementi | 1 | 1168 | 85.30 |
Angelo Monti | 2 | 671 | 46.93 |
Francesco Pasquale | 3 | 421 | 28.22 |
Francesco Pasquale | 4 | 421 | 28.22 |