Paths to stardom: calibrating the potential of a peer-based data management system

ABSTRACT

As peer-to-peer (P2P) networks become more familiar to the database community, intense interest has built up in using their scalability and resilience properties to scale database applications. Indexing methods are adapted on top of P2P networks and querying methods are developed to handle the data distribution on different nodes. These procedures largely depend on how nodes are connected to each other. So far, limited attempts have been made to compare all these systems in a generalized framework. This is because the systems are quite different from each other, and there are so many of them that brute force comparison is practically impossible. Fortunately, it has recently been observed that a large subset of the most important P2P networks share a common algebraic and combinatorial base, in the form of Cayley graphs.

The specific requirements of Peer-based Data Management Systems (PDMS), such as query completeness, range queries, load balancing, communication overhead, and scalability are strongly related to the properties of the underlying graphs, and naturally, some graphs are better than others. We conduct a comprehensive graph-theoretic analysis from the point of view of PDMS and identify the necessary conditions for a graph to be considered a potential network structure for a PDMS. In so doing, we provide a basis for the future development of such networks. We complement our analytical study with extensive experimental results and identify three measures that provide significant information about the potential of a [Cayley] graph to support the requirements of a PDMS.

REFERENCES

• 1: Karl Aberer, P-Grid: A Self-Organizing Access Structure for P2P Information Systems, Proceedings of the 9th International Conference on Cooperative Information Systems, p.179-194, September 05-07, 2001
• 2: Karl Aberer , Luc Onana Alima , Ali Ghodsi , Sarunas Girdzijauskas , Seif Haridi , Manfred Hauswirth, The Essence of P2P: A Reference Architecture for Overlay Networks, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.11-20, August 31-September 02, 2005 [doi>10.1109/P2P.2005.38]
• 3: S. B. Akers , B. Krishnamurthy, On group graphs and their fault tolerance, IEEE Transactions on Computers, v.36 n.7, p.885-888, July 1987 [doi>10.1109/TC.1987.1676983]
• 4: Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007627]
• 5: J.-C. Bermond , E. Darrot , O. Delmas , S. Perennes, Hamilton circuits in the directed wrapped Butterfly network, Discrete Applied Mathematics, v.84 n.1-3, p.21-42, May 15, 1998 [doi>10.1016/S0166-218X(97)00095-4]
• 6: S. R. Blackburn. Node Bisectors of Cayley Graphs. Theory of Computing Systems, 29(6), 1996.
• 7: Gao Cong , Wenfei Fan , Anastasios Kementsietsidis, Distributed query evaluation with performance guarantees, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247537]
• 8: Adina Crainiceanu , Prakash Linga , Ashwin Machanavajjhala , Johannes Gehrke , Jayavel Shanmugasundaram, P-ring: an efficient and robust P2P range index structure, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247507]
• 9: F. Dabek, B. Zhao, P. Druschel, J. Kubiatowicz, and I. Stoica. Towards a Common API for Structured Peer-to-Peer Overlays. In Proc. of IPTPS, 2003.
• 10: C. D. Godsil. Connectivity of Minimal Cayley Graphs. Archiv der Mathematik, 37(1), 1981.
• 11: K. Gummadi , R. Gummadi , S. Gribble , S. Ratnasamy , S. Shenker , I. Stoica, The impact of DHT routing geometry on resilience and proximity, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863998]
• 12: Nicholas J. A. Harvey , Michael B. Jones , Stefan Saroiu , Marvin Theimer , Alec Wolman, SkipNet: a scalable overlay network with practical locality properties, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.9-9, March 26-28, 2003, Seattle, WA
• 13: D. F. Hsu. On Container Width and Length in Graphs, Groups and Networks. IEICE TFECCS, E77-A(4), 1994.
• 14: R. Huebsch, B. Chun, J. M. Hellerstein, B. T. Loo, P. Maniatis, T. Roscoe, S. Shenker, I. Stoica, and A. R. Yumerefendi. The Architecture of PIER: an Internet-Scale Query Processor. In Proc. of CIDR, 2005.
• 15: H. V. Jagadish , Beng Chin Ooi , Quang Hieu Vu, BATON: a balanced tree structure for peer-to-peer networks, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 16: H. V. Jagadish , Beng Chin Ooi , Kian-Lee Tan , Quang Hieu Vu , Rong Zhang, Speeding up search in peer-to-peer networks with a multi-way tree structure, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142475]
• 17: John Jannotti , David K. Gifford , Kirk L. Johnson , M. Frans Kaashoek , James W. O'Toole, Jr., Overcast: reliable multicasting with on overlay network, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.14-14, October 22-25, 2000, San Diego, California
• 18: J.-S. Jwo, S. Lakshmivarahan, and S.K. Dhall. Embedding of Cycles and Grids in Star Graphs. In Proc. of SPDP, 1990.
• 19: Anastasios Kementsietsidis , Marcelo Arenas , Renée J. Miller, Mapping data in peer-to-peer systems: semantics and algorithmic issues, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872798]
• 20: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 21: J. Li, J. Stribling, R. Morris, M.F. Kaashoek, and T.M. Gil. A Performance vs. Cost Framework for Evaluating DHT Design Tradeoff Under Churn. In Proc. of INFOCOM, 2005.
• 22: Prakash Linga , Adina Crainiceanu , Johannes Gehrke , Jayavel Shanmugasudaram, Guaranteeing correctness and availability in P2P range indices, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066195]
• 23: Boon Thau Loo , Tyson Condie , Minos Garofalakis , David E. Gay , Joseph M. Hellerstein , Petros Maniatis , Raghu Ramakrishnan , Timothy Roscoe , Ion Stoica, Declarative networking: language, execution and optimization, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142485]
• 24: E. K. Lua, J. Crowcroft, M. Pias, S. Ravi, and S. Lim. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes. IEEE Comm. Surveys and Tutorials, 7(2), 2005.
• 25: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 26: I. Pak and R. Radoicic. Hamiltonian paths in Cayley Graphs. Preprint, http://www-math.mit.edu/~pak/hamcayley8.pdf.
• 27: Evaggelia Pitoura , Serge Abiteboul , Dieter Pfoser , George Samaras , Michalis Vazirgiannis, DBGlobe: a service-oriented P2P system for global computing, ACM SIGMOD Record, v.32 n.3, September 2003 [doi>10.1145/945721.945737]
• 28: C. Qu, W. Nejdl, and M. Kriesell. Cayley DHTs - A Group-Theoretic Framework for Analyzing DHTs Based on Cayley Graphs. In Proc. of ISPA, 2004.
• 29: D. Ratajczak and J. M. Hellerstein. Deconstructing DHTs. Technical Report IRB-TR-04-042, Intel Research Berkeley, Nov. 2003.
• 30: 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
• 31: M. Schlosser, M. Sintek, S. Decker, and W. Nejdl. HyperCup - Hypercubes, Ontologies, and Efficient Search in Peer-to-Peer Networks, volume 2530 of LNCS. Springer Berlin / Heidelberg, 2003.
• 32: Haiying Shen , Cheng-Zhong Xu , Guihai Chen, Cycloid: a constant-degree and lookup-efficient P2P overlay network, Performance Evaluation, v.63 n.3, p.195-216, March 2006 [doi>10.1016/j.peva.2005.01.004]
• 33: 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

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Performance, Reliability, Theory

Keywords:
cayley graph, peer to peer, query completeness