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 GRN G of n nodes, completes gossiping in O(n Δ) time (where Δ is the maximal in-degree of G) and has message complexity O(n 2). 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).
Clementi, A., Monti, A., Pasquale, F., Silvestri, R. (2007). Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults. In Mathematical Foundations of Computer Science 2007, 32nd Intern. Symp. MFCS 2007, LNCS. Springer [10.1007/978-3-540-74456-6_39].
Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults
CLEMENTI, ANDREA;PASQUALE, FRANCESCO;
2007-01-01
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 GRN G of n nodes, completes gossiping in O(n Δ) time (where Δ is the maximal in-degree of G) and has message complexity O(n 2). 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).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.