A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks

We study a switch Markov chain on regular graphs, where switches are allowed only between links that are at distance 2; we call this the flip. The motivation for studying the flip Markov chain arises in the context of unstructured peer-to-peer networks, which constantly perform such flips in an effo...

Full description

Saved in:
Bibliographic Details
Main Authors: Feder, T., Guetz, A., Mihail, M., Saberi, A.
Format: Conference Proceeding
Language:English
Subjects:
Analytical models
Bipartite graph
Computational modeling
Computer science
Network topology
Peer to peer computing
Sampling methods
Simulated annealing
State-space methods
Switches
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study a switch Markov chain on regular graphs, where switches are allowed only between links that are at distance 2; we call this the flip. The motivation for studying the flip Markov chain arises in the context of unstructured peer-to-peer networks, which constantly perform such flips in an effort to randomize. We show that the flip Markov chain on regular graphs is rapidly mixing, thus justifying this widely used peer-to-peer networking practice. Our mixing argument uses the Markov chain comparison technique. In particular, we extend this technique to embedding arguments where the compared Markov chains are defined on different state spaces. We give several conditions which generalize our results beyond regular graphs
ISSN:0272-5428
DOI:10.1109/FOCS.2006.5