In order to behave correctly, distributed consensus algorithms – which play a key role in several self-organized systems - require an efficient information dissemination mechanism. This is a non-trivial issue when agents communicate over an unstructured network, where each node has to rely only on local information to perform packet forwarding. Often this issue is approached by having the message to be disseminated by gossiping, i.e. by means of some kind of random walk. However, in many networks, topological bottlenecks can hinder information propagation from one network region to another, thus allowing distinct regions to settle on a consensus state on their own. In this work we study the performance of neighbor-avoiding random walks for information dissemination and show – using random 2D geometric networks as reference networks – that such walks have a higher probability of crossing topological bottlenecks and lower hitting time with respect to other random walk policies.

Gianini, G., Damiani, E. (2009). Neighbor-avoiding random walks for information dissemination. COMMUNICATIONS OF SIWN, 7, 113-118.

Neighbor-avoiding random walks for information dissemination

Gianini, G;
2009

Abstract

In order to behave correctly, distributed consensus algorithms – which play a key role in several self-organized systems - require an efficient information dissemination mechanism. This is a non-trivial issue when agents communicate over an unstructured network, where each node has to rely only on local information to perform packet forwarding. Often this issue is approached by having the message to be disseminated by gossiping, i.e. by means of some kind of random walk. However, in many networks, topological bottlenecks can hinder information propagation from one network region to another, thus allowing distinct regions to settle on a consensus state on their own. In this work we study the performance of neighbor-avoiding random walks for information dissemination and show – using random 2D geometric networks as reference networks – that such walks have a higher probability of crossing topological bottlenecks and lower hitting time with respect to other random walk policies.
Articolo in rivista - Articolo scientifico
information dissemination; memoryless random walks; self-avoiding random walks; neighbor-avoiding random walks; unstructured networks; bridges; hitting time
English
2009
7
113
118
none
Gianini, G., Damiani, E. (2009). Neighbor-avoiding random walks for information dissemination. COMMUNICATIONS OF SIWN, 7, 113-118.
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/10281/455186
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
Social impact