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
Clementi, A., Monti, A., Pasquale, F., Silvestri, R. (2012). Optimal gossiping in geometric radio networks in the presence of dynamical faults. NETWORKS, 59, 289-298 [10.1002/net.21451].
Optimal gossiping in geometric radio networks in the presence of dynamical faults
CLEMENTI, ANDREA;PASQUALE, FRANCESCO;
2012-01-01
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. 2012I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.