Random walks in peer-to-peer networks

Christos Gkantsidis, Milena Mihail, Amin Saberi

2004 · 531 citations · 30 references

Concepts

TL;DR

Random walks in networks can sample nearly independently if the second eigenvalue of the transition matrix is bounded away from one, a property that underlies expander graphs and has been used to construct pseudorandom generators. The study quantifies the effectiveness of random walks for searching and constructing unstructured peer‑to‑peer networks. The authors evaluate random‑walk search and show that an expander can be maintained dynamically with constant operations per addition, enabling efficient construction. Random walks outperform flooding when the overlay is clustered or when a client re‑issues a query with little horizon change, and the authors demonstrate that savings in random bits translate into reduced processing overhead.

Abstract

We quantify the effectiveness of random walks for searching and construction of unstructured peer-to-peer (P2P) networks. We have identified two cases where the use of random walks for searching achieves better results than flooding: a) when the overlay topology is clustered, and h) when a client re-issues the same query while its horizon does not change much. For construction, we argue that an expander can he maintained dynamically with constant operations per addition. The key technical ingredient of our approach is a deep result of stochastic processes indicating that samples taken from consecutive steps of a random walk can achieve statistical properties similar to independent sampling (if the second eigenvalue of the transition matrix is hounded away from 1, which translates to good expansion of the network; such connectivity is desired, and believed to hold, in every reasonable network and network model). This property has been previously used in complexity theory for construction of pseudorandom number generators. We reveal another facet of this theory and translate savings in random bits to savings in processing overhead.

References

30