loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks
Berkeley, California
October 21-October 24
ISBN: 0-7695-2720-5
ASCII Text
x 
 
Tomas Feder, Adam Guetz, Milena Mihail, Amin Saberi, "A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks," Foundations of Computer Science, IEEE Annual Symposium on, pp. 69-76, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2006.5,
author = {Tomas Feder and Adam Guetz and Milena Mihail and Amin Saberi},
title = {A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2006},
issn = {0272-5428},
pages = {69-76},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.5},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks
SN - 0272-5428
SP69
EP76
A1 - Tomas Feder,
A1 - Adam Guetz,
A1 - Milena Mihail,
A1 - Amin Saberi,
PY - 2006
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Tomas Feder, Stanford University, USA
Adam Guetz, Stanford University, USA
Milena Mihail, Georgia Tech, USA
Amin Saberi, Stanford University, USA
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-topeer 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.

Citation:
Tomas Feder, Adam Guetz, Milena Mihail, Amin Saberi, "A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks," focs, pp.69-76, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.