The Flip Markov Chain and a Randomising P2P Protocol

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 epsilon). Here, "rapidly" means in time polynomial in n and log epsilon(-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.