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. 2012
2012
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
English
Information Spreading, Fault-Tolerant Protocols, Radio Networks
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].
Clementi, A; Monti, A; Pasquale, F; Silvestri, R
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/89829
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact