Plexus: a scalable peer-to-peer protocol enabling efficient subset search

ABSTRACT

Efficient discovery of information, based on partial knowledge, is a challenging problem faced by many large scale dis-tributed systems. This paper presents Plexus, a peer-to-peer search protocol that provides an efficient mechanism for advertising a bit-sequence (pattern), and discovering it using any subset of its 1-bits. A pattern (e.g., Bloom filter) summarizes the properties (e.g., key-words, service description) associated with a shared object (e.g., document, service).

Plexus has a partially decentralized architecture involving super-peers. It adopts a novel structured routing mechanism derived from the theory of Error Correcting Codes (ECC). Plexus achieves better resilience to peer failure by utilizing replication and redundant routing paths. Routing efficiency in Plexus scales logarithmically with the number of superpeers. The concept presented in this paper is supported with theoretical analysis, and simulation results ob-tained from the application of Plexus to partial keyword search utilizing the extended Golay code.

REFERENCES

• 1: Gnutella website. [Online]. Available: http://www.gnutella.com
• 2: PeerSim Peer-to-Peer Simulator. [Online]. Available: http://www. peersim.sourceforge.net/
• 3: Alex Fabrikant , Elias Koutsoupias , Christos H. Papadimitriou, Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.110-122, July 08-13, 2002
• 4: R. Ahmed and R. Boutaba, "Distributed pattern matching: A key to flexible and efficient P2P search," IEEE J. Sel. Areas Commun., vol. 25, no. 1, pp. 73-83, Jan. 2007.
• 5: Amihood Amir , Ely Porat , Moshe Lewenstein, Approximate subset matching with Don't Cares, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.305-306, January 07-09, 2001, Washington, D.C., United States
• 6: Stephanos Androutsellis-Theotokis , Diomidis Spinellis, A survey of peer-to-peer content distribution technologies, ACM Computing Surveys (CSUR), v.36 n.4, p.335-371, December 2004 [doi>10.1145/1041680.1041681]
• 7: Magdalena Balazinska , Hari Balakrishnan , David Karger, INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery, Proceedings of the First International Conference on Pervasive Computing, p.195-210, August 26-28, 2002
• 8: Mayank Bawa , Tyson Condie , Prasanna Ganesan, LSH forest: self-tuning indexes for similarity search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060840]
• 9: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 10: Angela Bonifati , Ugo Matrangolo , Alfredo Cuzzocrea , Mayank Jain, XPath lookup queries in P2P networks, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA [doi>10.1145/1031453.1031464]
• 11: Min Cai , Martin Frank, RDFPeers: a scalable distributed RDF repository based on a structured peer-to-peer network, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988760]
• 12: Yatin Chawathe , Sylvia Ratnasamy , Lee Breslau , Nick Lanham , Scott Shenker, Making gnutella-like P2P systems scalable, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.864000]
• 13: V. Chvtal, "A greedy heuristic for the set covering problem," Math. Oper. Res., vol. 4, pp. 233-235, 1979.
• 14: E. Cohen, A. Fiat, and H. Kaplan, "Associative search in peer to peer networks: Harnessing latent semantics," in Proc. IEEE INFOCOM, 2003, electronic edition, 11 pp.
• 15: Richard Cole , Ramesh Hariharan, Tree pattern matching and subset matching in randomized O(nlog3m) time, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.66-75, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258553]
• 16: J. Conway and N. Sloane, "Orbit and coset analysis of the Golay and related codes," IEEE Trans. Inf. Theory, vol. 36, no. 5, pp. 1038-1050, Sep. 1990.
• 17: Steven E. Czerwinski , Ben Y. Zhao , Todd D. Hodes , Anthony D. Joseph , Randy H. Katz, An architecture for a secure service discovery service, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.24-35, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313462]
• 18: E. Franconi, G. Kuper, A. Lopatenko, and I. Zaihrayeu, "The coDB robust peer-to-peer database system," in Proc. WWW Conf., New York City, May 2004, pp. 382-393.
• 19: Leonidas Galanis , Yuan Wang , Shawn R. Jeffery , David J. DeWitt, Locating data sources in large distributed systems, Proceedings of the 29th international conference on Very large data bases, p.874-885, September 09-12, 2003, Berlin, Germany
• 20: J. Gao and P. Steenkiste, "Design and evaluation of a distributed scal-able content discovery system," IEEE J. Sel. Areas Commun., vol. 22, no. 1, pp. 54-66, Jan. 2004.
• 21: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 22: M. J. E. Golay, "Notes on digital coding," Proc. IRE, vol. 37, no. 657, 1949.
• 23: V. Guruswami and M. Sudan, "Extensions to the Johnson Bound," MIT, 2001 [Online]. Available: http://theory.lcs.mit.edu/~madhu/pa-pers/johnson.ps
• 24: Matthew Harren , Joseph M. Hellerstein , Ryan Huebsch , Boon Thau Loo , Scott Shenker , Ion Stoica, Complex Queries in DHT-based Peer-to-Peer Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.242-259, March 07-08, 2002
• 25: 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
• 26: Y. Joung, L. Yang, and C. Fang, "Keyword search in DHT-based peer-to-peer networks," IEEE J. Sel. Areas Commun., vol. 25, no. 1, pp. 46-61, Jan. 2007.
• 27: Xue Kaiping , Hong Peilin , Li Jinsheng, FS-Chord: A New P2P Model with Fractional Steps Joining, Proceedings of the Advanced Int'l Conference on Telecommunications and Int'l Conference on Internet and Web Applications and Services, p.98, February 19-25, 2006
• 28: J. Kim and G. Fox, "A hybrid keyword search across peer-to-peer fed-erated databases," in Proc. ADBIS 2004-Local Proc., Budapest, Hun-gary, Sep. 2004, electronic edition, 13 pp.
• 29: M. Li, W. Lee, and A. Sivasubramaniam, "Neighborhood signatures for searching P2P networks," in Proc. IDEAS, 2003, pp. 149-159.
• 30: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 31: Petar Maymounkov , David Mazières, Kademlia: A Peer-to-Peer Information System Based on the XOR Metric, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.53-65, March 07-08, 2002
• 32: W. S. Ng, B. C. Ooi, K. L. Tan, and A. Zhou, "PeerDB: A P2P-based system for distributed data sharing," in Proc. ICDE, 2003, pp. 633-644.
• 33: 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
• 34: Mario Schlosser , Michael Sintek , Stefan Decker , Wolfgang Nejdl, A Scalable and Ontology-Based P2P Infrastructure for Semantic Web Services, Proceedings of the Second International Conference on Peer-to-Peer Computing, p.104, September 05-07, 2002
• 35: Cristina Schmidt , Manish Parashar, Enabling Flexible Queries with Guarantees in P2P Systems, IEEE Internet Computing, v.8 n.3, p.19-26, May 2004 [doi>10.1109/MIC.2004.1297269]
• 36: Ion Stoica , Robert Morris , David Liben-Nowell , David R. Karger , M. Frans Kaashoek , Frank Dabek , Hari Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.17-32, February 2003 [doi>10.1109/TNET.2002.808407]
• 37: Daniel Stutzbach , Reza Rejaie , Subhabrata Sen, Characterizing unstructured overlay topologies in modern P2P file-sharing systems, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.5-5, October 19-21, 2005, Berkeley, CA
• 38: C. Tang, Z. Xu, and M. Mahalingam, "pSearch: Information retrieval in structured overlays," presented at the First Workshop on Hot Topics in Networks (HotNets-I), Princeton, NJ, Oct. 2002.
• 39: Dimitrios Tsoumakos , Nick Roussopoulos, Adaptive Probabilistic Search for Peer-to-Peer Networks, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.102, September 01-03, 2003
• 40: S. Voulgaris, M. Jelasity, and M. van Steen, "A robust and scalable peer-to-peer gossiping protocol," in Proc. AP2PC, 2003, pp. 47-58.
• 41: Beverly Yang , Hector Garcia-Molina, Improving Search in Peer-to-Peer Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.5, July 02-05, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
bloom filter, distributed pattern matching, error correcting codes, peer-to-peer search, structured overlay network