Name
Abstract | ||
|---|---|---|
We present a family of peer-to-peer network protocols that yield regular graph topologies having known Hamilton cycles. These topologies are equivalent, in a well-defined sense, to the random regular graph. As a consequence, we have connectivity deterministically, and logarithmic diameter and expansion properties with high probability. We study the efficacy of certain simple topology-altering operations, designed to introduce randomness. These operations enable the network to self-stabilise when damaged. They resemble the operations used by Cooper, Dyer and Greenhill (2007) for a similar purpose in the case of random regular graphs. There is a link between our protocols and certain combinatorial structures which have been studied previously, in particular discordant permutations and Latin rectangles. We give the first rigorous polynomial mixing-time bounds for natural Markov chains that sample these objects at random. We do so by developing a novel extension to the canonical path technique for bounding mixing times: routing via a random destination. This resembles a technique used by Valiant (1982) for low-congestion routing in hypercubes. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.5555/2133036.2133108 | Symposium on Discrete Algorithms |
Keywords | DocType | ISBN |
canonical path technique,low-congestion routing,random regular graph,certain simple topology-altering operation,regular graph,hamilton cycle,peer-to-peer network protocol,certain combinatorial structure,random cycle,latin rectangle,random destination,markov chain,mixing time,randomized algorithms,distributed computing,leader election | Conference | 978-1-61197-251-1 |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 287 | 30.73 |
| Martin E. Dyer | 2 | 529 | 116.66 |
| Andrew J. Handley | 3 | 11 | 1.41 |