Peer to peer networks are self-organising communications networks formed from independent hosts. Their decentralised nature makes them massively scalable but complicates the task of global network coordination. How can such a network detect and repair topological damage in the absence of a a central authority? We present two classes of self-stabilising networks based on random regular graphs. Random regular graphs make excellent topologies for communications networks due to their small diameter, expansion properties, and extreme resilience to accumulated damage or attack. The networks presented here are self-stabilising in the sense that they automatically attempt to recover from illegal states. They are suitable for efficient search, peer discovery, or the construction of a Distributed Hash Table. In a random network, self-stabilisation does not imply the mainteriance of delicate structure, but the elimination of structure: self-randomisation. This work addresses small, individually fast randomising operations-the switch, the flip and the transposition-that occur spontaneously throughout the network without any form of coordination. These operations quickly randomise any connected network. Rigorous bounds exist that show they mix in time polynomial in the network size, and simulation results suggest an order of O( n log n) suffices. In studying the behaviour of these operations we give two novel extensions of the canonical path technique, a method to analyse the mixing rates of Markov chains. The first is a two-stage direct method to transfer mixing time bounds from one chain to another, similar to but distinct from Markov chain comparison. The directness of this approach allows for a much tighter bound than in previous work, especially when the two chains have distinct state spaces. The second is a method applicable when canonical path congestion is expected to be good but poor in the worst case. This bears a resemblance to Valiant's randomised routeing on the hypercube. Finally, we demonstrate a link between one of out network classes and Latin rectangles, a combinatorial object of independent interest. Our results on self-randomisation give the first fully polynomial randomised approximation schema for these objects.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:634444 |
| Date | January 2013 |
| Creators | Handley, Andrew Jobriath |
| Publisher | University of Leeds |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.0065 seconds