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 ε⁻¹. 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.

REFERENCES

• 1: Bittorrent. http://www.bittorrent.org.
• 2: V. Bourassa and F. Holt. Swan: Small-world wide area networks. In Proceedings of International Conference on Advances in Infrastructure (SSGRR 2003w), L'Aquila, Italy, 2003. Paper #64.
• 3: Colin Cooper , Martin Dyer , Catherine Greenhill, Sampling Regular Graphs and a Peer-to-Peer Network, Combinatorics, Probability and Computing, v.16 n.4, p.557-593, July 2007 [doi>10.1017/S0963548306007978]
• 4: Colin Cooper , Ralf Klasing , Tomasz Radzik, A randomized algorithm for the joining protocol in dynamic distributed networks, Theoretical Computer Science, v.406 n.3, p.248-262, October, 2008 [doi>10.1016/j.tcs.2008.06.049]
• 5: P. Diaconis and L. Saloff-Coste. Comparison theorems for reversible Markov chains. Annals of Applied Probability, 3:696--730, 1993.
• 6: P. Diaconis and D. Stroock. Geometric bounds for eigenvalues of Markov chains. Annals of Applied Probability, 1:36--61, 1991.
• 7: M. Dyer, L. Goldberg, M. Jerrum, and R. Martin. Markov chain comparison. Probability Surveys, 3:89--111, 2006.
• 8: 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, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.69-76, October 21-24, 2006 [doi>10.1109/FOCS.2006.5]
• 9: C. P. Fry and M. K. Reiter. Really truly trackerless bittorrent. Technical report, Carnegie Mellon University, 2006.
• 10: Gnutella. http://en.wikipedia.org/wiki/Gnutella.
• 11: S. Janson, T. Luczak, and A. Rucinski. Random Graphs. Wiley, 2000.
• 12: M. Jerrum. Counting, Sampling and Integrating: Algorithms and Complexity. Birkhaeuser, 2003.
• 13: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 14: Ravi Kannan , Prasad Tetali , Santosh Vempala, Simple Markov-chain algorithms for generating bipartite graphs and tournaments, Random Structures & Algorithms, v.14 n.4, p.293-308, July 1999 [doi>10.1002/(SICI)1098-2418(199907)14:4<293::AID-RSA1>3.0.CO;2-G]
• 15: Peter Mahlmann , Christian Schindelhauer, Peer-to-peer networks based on random transformations of connected regular undirected graphs, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073992]
• 16: G. Pandurangan, P. Raghavan, and E. Upfal. Building low-diameter peer-to-peer networks. Selected Areas in Communications, IEEE Journal on, 21(6):995--1002, 2003.
• 17: D. Randall and P. Tetali. Analyzing Glauber dynamics by comparison of Markov chains. Journal of Mathematical Physics, 41(3):1598--1615, 2000.
• 18: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 19: S. Saroiu, P. Krishna Gummadi, and S. D. Gribble. Measuring and analyzing the characteristics of napster and gnutella hosts. Multimedia Systems Journal, 8(5), November 2002.
• 20: A. Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing, 1:351--370, 1992.
• 21: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 22: N. Wormald and V. Sanwalani. The diameter of random regular graphs. Incomplete paper.
• 23: N. C. Wormald. Models of random regular graphs. In J.D. Lamb and D.A. Preece, editors, Survey in Combinatorics, London Mathematical Society Lecture Notes 276. Cambridge University Press, Cambridge, 1999.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Algorithms, Performance, Reliability

Keywords:
P2P, asynchronous, canonical paths, distributed, mixing time, network, peer-to-peer, protocol, randomisation