Information dissemination in unstructured networks by self-repulsive random walks

Distributed consensus algorithms play a key role in several self-organized systems and are used, for instance, in ad-hoc 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 non-trivial 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 (neighbor-avoiding random walks). This sort of self-repulsion 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 ad-hoc 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 (memory-less 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 neighbor-avoiding 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 self-repulsion. We observe that the policy followed by a single walker can be made vary with time, enhancing or decreasing its self-repulsion. We argue furthermore that such random walk in the random geometrical network, would be analogous to the scattering in a random medium of a high-energy 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 long-leg 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.