skip to main content
article

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

Published: 01 February 2009 Publication History

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]
A. Fabrikant, E. Koutsoupias, and C. Papadimitriou, "Heuristically op-timized trade-offs: A new paradigm for power laws in the internet," in Proc. ICALP, 2002, pp. 110-122.
[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]
A. Amir, E. Porat, and M. Lewenstein, "Approximate subset matching with don't cares," in Proc. SODA, 2001, pp. 305-306.
[6]
S. Androutsellis-Theotokis and D. Spinellis, "A survey of peer-to-peer content distribution technologies," ACM Computing Surveys, vol. 45, no. 2, pp. 195-205, Dec. 2004.
[7]
M. Balazinska, H. Balakrishnan, and D. Karger, "INS/Twine: A scal-able peer-to-peer architecture for intentional resource discovery," in Proc. Pervasive Computing, 2002, pp. 195-210.
[8]
M. Bawa, T. Condie, and P. Ganesan, "LSH Forest: Self-tuning in-dexes for similarity search," in Proc. 14th Int. World Wide Web Conf. (WWW2005), May 2005, pp. 651-660.
[9]
B. H. Bloom, "Space/time trade-offs in hash coding with allowable errors," Commun. ACM, vol. 13, no. 7, pp. 422-426, 1970.
[10]
A. Bonifati, U. Matrangolo, A. Cuzzocrea, and M. Jain, "XPath lookup queries in P2P networks," in Proc. WIDM, 2004, pp. 48-55.
[11]
M. Cai and M. Frank, "RDFPeers: A scalable distributed RDF reposi-tory based on a structured peer-to-peer network," in Proc. WWW Conf., 2004, pp. 650-657.
[12]
Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, "Making Gnutella-like P2P systems scalable," in Proc. ACM SIG-COMM, 2003, pp. 407-418.
[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]
R. Cole and R. Harihan, "Tree pattern matching and subset matching in randomized O(n log3 m) time," in Proc. ACM STOC, 1997, pp. 66-75.
[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]
S. E. Czerwinski, B. Y. Zhao, T. D. Hodes, A. D. Joseph, and R. H. Katz, "An architecture for a secure service discovery service," in Proc. ACM MOBICOM, 1999, pp. 24-35.
[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]
L. Galanis, Y. Wang, S. Jeffery, and D. DeWitt, "Locating data sources in large distributed systems," in Proc. Very Large Data Bases (VLDB) Conf., 2003, pp. 874-885.
[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]
D. K. Gifford, "Weighted voting for replicated data," in Proc. Symp. OS Principles, 1979, pp. 150-162.
[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]
M. Harren, J. M. Hellerstein, R. Huebsch, B. T. Loo, S. Shenker, and I. Stoica, "Complex queries in DHT-based peer-to-peer networks," in Proc. IPTPS, 2002, pp. 242-259.
[25]
N. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman, "Skipnet: A scalable overlay network with practical locality proper-ties," in Proc. USITS, Mar. 2003, electronic edition, 14 pp.
[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]
X. Kaiping, H. Peilin, and L. Jinsheng, "FS-chord: A new P2P model with fractional steps joining," in Proc. AICT/ICIW, 2006, p. 98.
[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]
C. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, "Search and replication in unstructured peer-to-peer networks," in Proc. ICS, 2002, pp. 84-95.
[31]
P. Maymounkov and D. Mazières, "Kademlia: A peer-to-peer infor-mation system based on the XOR metric," in Proc. IPTPS, 2002, pp. 53-65.
[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]
S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, "A scalable content-addressable network," in Proc. ACM SIGCOMM, 2001, pp. 161-172.
[34]
M. Schlosser, M. Sintek, S. Decker, and W. Nejdl, "A scalable and ontology-based P2P infrastructure for semantic web services," in Proc. P2P Computing, Sep. 2002, pp. 104-111.
[35]
C. Schmidt and M. Parashar, "Enabling flexible queries with guarantees in P2P systems," IEEE Internet Computing, vol. 8, no. 3, pp. 19-26, May-Jun. 2004.
[36]
I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan, "Chord: A scalable peer-to-peer lookup protocol for internet applications," IEEE/ACM Trans. Networking, vol. 11, no. 1, pp. 17-32, Feb. 2003.
[37]
D. Stutzbach and R. Rejaie, "Characterizing unstructured overlay topologies in modern P2P file-sharing systems," in Proc. Internet Measurement Conf. (IMC 2005), Oct. 2005, pp. 49-62.
[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]
D. Tsoumako and N. Roussopoulos, "Adaptive probabilistic search for peer-to-peer networks," in Proc. IEEE Int. Conf. P2P Computing, 2003, pp. 102-109.
[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]
B. Yang and H. Garcia-Molina, "Improving search in peer-to-peer net-works," in Proc. ICDCS, 2002, pp. 5-14.

Cited By

View all
  • (2023)Search mechanism for data contents based on bloom filter and tree hybrid structure in system wide information managementIET Communications10.1049/cmu2.1262117:11(1262-1273)Online publication date: 3-Jul-2023
  • (2014)An RDF-based P2P overlay network supporting range and wildcard queriesJournal of Network and Computer Applications10.1016/j.jnca.2014.08.00546:C(124-138)Online publication date: 1-Nov-2014
  • (2013)SMBSRPProceedings of the 12th international conference on Artificial Neural Networks: advances in computational intelligence - Volume Part I10.1007/978-3-642-38679-4_64(633-646)Online publication date: 12-Jun-2013
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 17, Issue 1
February 2009
346 pages

Publisher

IEEE Press

Publication History

Published: 01 February 2009
Revised: 05 November 2007
Received: 18 February 2007
Published in TON Volume 17, Issue 1

Author Tags

  1. bloom filter
  2. distributed pattern matching
  3. error correcting codes
  4. peer-to-peer search
  5. structured overlay network

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Search mechanism for data contents based on bloom filter and tree hybrid structure in system wide information managementIET Communications10.1049/cmu2.1262117:11(1262-1273)Online publication date: 3-Jul-2023
  • (2014)An RDF-based P2P overlay network supporting range and wildcard queriesJournal of Network and Computer Applications10.1016/j.jnca.2014.08.00546:C(124-138)Online publication date: 1-Nov-2014
  • (2013)SMBSRPProceedings of the 12th international conference on Artificial Neural Networks: advances in computational intelligence - Volume Part I10.1007/978-3-642-38679-4_64(633-646)Online publication date: 12-Jun-2013
  • (2011)The resource efficient forwarding in the content centric networkProceedings of the 10th international IFIP TC 6 conference on Networking - Volume Part I10.5555/2008780.2008788(66-77)Online publication date: 9-May-2011
  • (2011)Towards a Kademlia DHT-based n-tuple storeProceedings of the 3rd International Workshop on Theoretical Aspects of Dynamic Distributed Systems10.1145/2034640.2034648(23-27)Online publication date: 19-Sep-2011

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media