Paper Info
Title
The flip markov chain and a randomising P2P protocol
Abstract
We define a network that relies on its protocol's emergent behaviour to maintain the useful properties of a random regular topology. It does this by spontaneously performing flips in an effort to randomise [15], allowing it to repair damage and to embed new peers without over-complicated joining schema. The main theoretical result of this paper is informed by the need to show that flips randomise the network quickly enough. Formally, we show that performing random flip operations on a regular graph of size n will rapidly sample from all such graphs almost uniformly at random (i.e. with error ε). Here, "rapidly" means in time polynomial in n and log ε−1. This is done by extending a similar result for random switches, obtained in [3], using a two-stage direct canonical path construction. The directness of our approach allows for a much tighter bound than obtained in previous work.
Year
DOI
Venue
2009
10.1145/1582716.1582742
PODC
Keywords
Field
DocType
similar result,embed new peer,random flip operation,flip markov chain,emergent behaviour,regular graph,random regular topology,previous work,size n,random switch,main theoretical result,p2p protocol,p2p,markov chain,network,asynchronous,protocol,mixing time
Asynchronous communication,Graph,Flip,Peer-to-peer,Polynomial,Computer science,Markov chain,Algorithm,Theoretical computer science,Regular graph,Distributed computing
Conference
Citations 
PageRank 
References 
11
0.73
14
Authors
3
Name
Order
Citations
PageRank
Colin Cooper128730.73
Martin Dyer239372.72
Andrew J. Handley3111.41