Distributed consensus algorithms play a key role in several selforganized systems and are used, for instance, in adhoc and sensor networks. In order to behave correctly they need to rely upon an efficient information dissemination mechanism, so as to make available, to each node in the network, a representative sample of the states of the other nodes. This is a nontrivial issue when agents communicate over an unstructured network, where each node has to rely only on local information to perform routing decisions. Often this issue is approached by having the information to be disseminated by gossiping i.e. by means of some kind of random walks. Recently we have proposed a self repulsive random walk policy which increases the speed of information propagation with respect to traditional policies, by avoiding to visit the neighbors of the current node which are also neighbors of the most recently visited node (neighboravoiding random walks). This sort of selfrepulsion of the path results in some extra stiffness in the walker's effective path, and as a consequence  due to the square root law of diffusion  results in a larger average geometrical path walked by the message in random geometrical networks (which are often used to model adhoc and wireless sensor networks). We generalize here this policy to a family of policies where walkers may carry the memory of the latest $m$ hops (memoryless random walk will correspond to $m=0$) and know their neighbors up to $n$ hop distances: normally nodes know just the first round of neighbors  n=1 i.e. their nearest neighbors  however by exchanging messages with those, they may gain knowledge of their $n=2$ neighbors, i.e. their neighbor's neighbors. The above mentioned neighboravoiding random walk corresponds to the case $(m=1,n=2)$. On the basis of the spectrum of possibilities corresponding to higher values of $m$ and $n$ one can formulate a rich range of different random walk policies, with different stiffness and average geometrical path. We notice that the mathematical description of the class of random walks with memory and neighbor repulsion parameters $(m,n)$ is reminiscent of that of polymeric chains of length $m$ with some sort of degree $n$ of selfrepulsion. We observe that the policy followed by a single walker can be made vary with time, enhancing or decreasing its selfrepulsion. We argue furthermore that such random walk in the random geometrical network, would be analogous to the scattering in a random medium of a highenergy particle, endowed with changing momentum: typically during the scattering in a medium a particle looses gradually momentum and eventually releases most of its energy in a localized area of specific depth (distance from the source), giving rise to a rather localized structure of the amount of energy deposition as a function of distance, known as Bragg peak (used for instance in radiation therapy). By analogy it may be useful also considering \"aging\" random walk policies, devised to weaken their longleg property with time, up to the simple random walk so as to spend  in average  more time in regions at a specified distance. We propose to use this property to gauge the distance at which a message undergoing a random walk can have higher density of node visits. An ensemble of messages produced by a single node and characterized by different momentum decay rates could be made advertise the state of the source node more uniformly than a single policy random walk.
Information dissemination in unstructured networks by selfrepulsive random walks / G. Gianini, E. Damiani, P. Ceravolo, O. Gregory Irhule.  In: Web science overlay journal.  (2009). ((Intervento presentato al 1. convegno WebSci: society online tenutosi a Athens nel 2009.
Information dissemination in unstructured networks by selfrepulsive random walks
G. Gianini^{Primo};E. Damiani^{Secondo};P. Ceravolo^{Penultimo};
2009
Abstract
Distributed consensus algorithms play a key role in several selforganized systems and are used, for instance, in adhoc and sensor networks. In order to behave correctly they need to rely upon an efficient information dissemination mechanism, so as to make available, to each node in the network, a representative sample of the states of the other nodes. This is a nontrivial issue when agents communicate over an unstructured network, where each node has to rely only on local information to perform routing decisions. Often this issue is approached by having the information to be disseminated by gossiping i.e. by means of some kind of random walks. Recently we have proposed a self repulsive random walk policy which increases the speed of information propagation with respect to traditional policies, by avoiding to visit the neighbors of the current node which are also neighbors of the most recently visited node (neighboravoiding random walks). This sort of selfrepulsion of the path results in some extra stiffness in the walker's effective path, and as a consequence  due to the square root law of diffusion  results in a larger average geometrical path walked by the message in random geometrical networks (which are often used to model adhoc and wireless sensor networks). We generalize here this policy to a family of policies where walkers may carry the memory of the latest $m$ hops (memoryless random walk will correspond to $m=0$) and know their neighbors up to $n$ hop distances: normally nodes know just the first round of neighbors  n=1 i.e. their nearest neighbors  however by exchanging messages with those, they may gain knowledge of their $n=2$ neighbors, i.e. their neighbor's neighbors. The above mentioned neighboravoiding random walk corresponds to the case $(m=1,n=2)$. On the basis of the spectrum of possibilities corresponding to higher values of $m$ and $n$ one can formulate a rich range of different random walk policies, with different stiffness and average geometrical path. We notice that the mathematical description of the class of random walks with memory and neighbor repulsion parameters $(m,n)$ is reminiscent of that of polymeric chains of length $m$ with some sort of degree $n$ of selfrepulsion. We observe that the policy followed by a single walker can be made vary with time, enhancing or decreasing its selfrepulsion. We argue furthermore that such random walk in the random geometrical network, would be analogous to the scattering in a random medium of a highenergy particle, endowed with changing momentum: typically during the scattering in a medium a particle looses gradually momentum and eventually releases most of its energy in a localized area of specific depth (distance from the source), giving rise to a rather localized structure of the amount of energy deposition as a function of distance, known as Bragg peak (used for instance in radiation therapy). By analogy it may be useful also considering \"aging\" random walk policies, devised to weaken their longleg property with time, up to the simple random walk so as to spend  in average  more time in regions at a specified distance. We propose to use this property to gauge the distance at which a message undergoing a random walk can have higher density of node visits. An ensemble of messages produced by a single node and characterized by different momentum decay rates could be made advertise the state of the source node more uniformly than a single policy random walk.File  Dimensione  Formato  

Gianini.pdf
accesso aperto
Tipologia:
Preprint (manoscritto inviato all'editore)
Dimensione
74.5 kB
Formato
Adobe PDF

74.5 kB  Adobe PDF  Visualizza/Apri 
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.