We study the completion time of broadcast operations on static ad hoc wireless networks in presence of unpredictable and dynamical faults. Concerning oblivious fault-tolerant distributed protocols, we provide an Omega(Dn) lower bound where n is the number of nodes of the network and D is the source eccentricity in the fault-free part of the network. Rather surprisingly, this lower bound implies that the simple Round Robin protocol, working in O(Dn) time, is an optimal fault-tolerant oblivious protocol. Then, we demonstrate that networks of o(n'/log n) maximum in-degree admit faster oblivious protocols. Indeed, we derive an oblivious protocol having O(D min{n, Delta log n}) completion time on any network of maximum in-degree Delta. Finally, we address the question whether adaptive protocols can be faster than oblivious ones. We show that the answer is negative at least in the general setting: we indeed prove an Omega(Dn) lower bound when D = Theta(rootn). This clearly implies that no (adaptive) protocol can achieve, in general, o(Dn) completion time. (C) 2003 Elsevier Inc. All rights reserved.
Round Robin is optimal for fault-tolerant broadcasting on wireless networks / Andrea E. F., Clementi; Monti, Angelo; Silvestri, Riccardo. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - STAMPA. - 64:1(2004), pp. 89-96. [10.1016/j.jpdc.2003.09.002]
Round Robin is optimal for fault-tolerant broadcasting on wireless networks
MONTI, Angelo;SILVESTRI, RICCARDO
2004
Abstract
We study the completion time of broadcast operations on static ad hoc wireless networks in presence of unpredictable and dynamical faults. Concerning oblivious fault-tolerant distributed protocols, we provide an Omega(Dn) lower bound where n is the number of nodes of the network and D is the source eccentricity in the fault-free part of the network. Rather surprisingly, this lower bound implies that the simple Round Robin protocol, working in O(Dn) time, is an optimal fault-tolerant oblivious protocol. Then, we demonstrate that networks of o(n'/log n) maximum in-degree admit faster oblivious protocols. Indeed, we derive an oblivious protocol having O(D min{n, Delta log n}) completion time on any network of maximum in-degree Delta. Finally, we address the question whether adaptive protocols can be faster than oblivious ones. We show that the answer is negative at least in the general setting: we indeed prove an Omega(Dn) lower bound when D = Theta(rootn). This clearly implies that no (adaptive) protocol can achieve, in general, o(Dn) completion time. (C) 2003 Elsevier Inc. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.