Decentralized search on spheres using small-world Markov chains: expected hitting times and structural properties

We build a family of Markov chains on a sphere using distance-based long-range connection probabilities to model the decentralized message-passing problem that has recently gained significant attention in the small-world literature. Starting at an arbitrary source point on the sphere, the expected message delivery time to an arbitrary target on the sphere is characterized by a particular expected hitting time of our Markov chains. We prove that, within this family, there is a unique efficient Markov chain whose expected hitting time is polylogarithmic in the relative size of the sphere. For all other chains, this expected hitting time is at least polynomial. We conclude by defining two structural properties, called scale invariance and steady improvement, of the probability density function of long-range connections and prove that they are sufficient and necessary for efficient decentralized message delivery.

Decentralized search on spheres using small-world Markov chains: expected hitting times and structural properties

We build a family of Markov chains on a sphere using distance-based long-range connection probabilities to model the decentralized message-passing problem that has recently gained significant attention in the small-world literature. Starting at an arbitrary source point on the sphere, the expected message delivery time to an arbitrary target on the sphere is characterized by a particular expected hitting time of our Markov chains. We prove that, within this family, there is a unique efficient Markov chain whose expected hitting time is polylogarithmic in the relative size of the sphere. For all other chains, this expected hitting time is at least polynomial. We conclude by defining two structural properties, called scale invariance and steady improvement, of the probability density function of long-range connections and prove that they are sufficient and necessary for efficient decentralized message delivery.

A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents

We address the question of understanding the effect of the underlying network topology on the spread of a virus and the dissemination of information when users are mobile performing independent random walks on a graph. To this end, we propose a simple model of infection that enables to study the coincidence time of two random walkers on an arbitrary graph. By studying the coincidence time of a susceptible and an infected individual both moving in the graph we obtain estimates of the infection probability. The main result of this paper is to pinpoint the impact of the network topology on the infection probability. More precisely, we prove that for homogeneous graphs including regular graphs and the classical Erdős-Rényi model, the coincidence time is inversely proportional to the number of nodes in the graph. We then study the model on power-law graphs, that exhibit heterogeneous connectivity patterns, and show the existence of a phase transition for the coincidence time depending on the parameter of the power-law of the degree distribution. We finally undertake a preliminary analysis for the case with k random walkers and provide upper bounds on the convergence time for both the complete graph and regular graphs.

Scaling laws for delay-sensitive traffic in Rayleigh fading networks

The throughput of delay-sensitive traffic in a Rayleigh fading network is studied by adopting a scaling limit approach. The case of the study is that of a pair of nodes establishing a data stream that has routing priority over all the remaining traffic in the network. For every delay constraint, upper and lower bounds on the achievable information rate between the two endpoints of the stream are obtained as the network size grows. The analysis concerns decentralized schemes , in the sense that all nodes make next-hop decisions based only on local information, namely their channel strength to other nodes in the network and the position of the destination node. This is particularly important in a fading scenario, where the channel strength varies with time and hence pre-computing routes can be of little help. Natural applications are remote surveillance using sensor networks and communication in emergency scenarios.