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Δ) time (where n is the number of nodes and Δ 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Δ) (where D is the maximal source eccentricity) and message complexity O(Dn). © 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 2012 Copyright © 2012 Wiley Periodicals, Inc.