Abstract | ||
---|---|---|
We study deterministic fault-tolerant gossiping protocols in geometric radio networks. Node and link faults may happen during every time-slot of the protocol's execution. We first consider the model where every node can send at most one message per time-slot. We provide a protocol that completes gossiping in O(nΔ) time (where n is the number of nodes and Δ is the maximal in-degree) and has message complexity O(n2). Both bounds are then shown to be optimal. Second, we consider the model where messages can be arbitrarily combined and sent in one time-slot. We give a protocol working in optimal completion time O(DΔ) (where D is the maximal source eccentricity) and message complexity O(Dn). © 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 2012 © 2012 Wiley Periodicals, Inc. (The results of this work have been presented at the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS'07).) |
Year | DOI | Venue |
---|---|---|
2012 | 10.1002/net.21451 | Networks |
Keywords | Field | DocType |
dynamical fault,international symposium,message complexity o,geometric radio network,maximal in-degree,wiley periodicals,computer science,maximal source eccentricity,inc. networks,optimal completion time,deterministic fault-tolerant,mathematical foundations,gossiping | Radio networks,Eccentricity (behavior),Computer science,Computer network,Gossip | Journal |
Volume | Issue | ISSN |
59 | 3 | 0028-3045 |
Citations | PageRank | References |
2 | 0.36 | 23 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrea Clementi | 1 | 59 | 3.54 |
Angelo Monti | 2 | 671 | 46.93 |
Francesco Pasquale | 3 | 421 | 28.22 |
Riccardo Silvestri | 4 | 1324 | 90.84 |