Optimal Gossiping in Geometric Radio Networks in the Presence of Dynamical Faults
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 Delta) time (where n is the number of nodes and Delta is the maximal in-degree) and has message complexity O(n(2)). 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 Delta) (where D is the maximal source eccentricity) and message complexity O(Dn). (c) 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 59(3), 289-298 2012
gossiping ad-hoc radio networks fault-tolerant protocols distributed protocols