SkipMard: A multi-attribute peer-to-peer resource discovery approach

Tao He, Jun Ni, Alberto M. Segre, Shaowen Wang, Boyd M. Knosp

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Resource discovery technologies for Grids and Peer-to-Peer (P2P) systems share some characteristics. However, some P2P systems such as Skip Graph cannot simply be applied to Grid resource discovery because complex grid resources need to be searched by using multi-attribute queries. This paper proposes a new multi-attribute P2P resource discovery approach (SkipMard) that extends Skip Graph structure to support multi-attribute queries. SkipMard provides a prefix matching resource routing algorithm to resolve multi-attribute queries, and introduces the concepts of "layer" and "crossing layer nearest neighbor" into the data structure. To decrease message passing numbers, an approximate closest-point method is addressed that can help routing a searching key to a node with a key value that has the minimum distance between two keys. Each node has O(m *l) neighbors for total m layers and l levels in SkipMard. The expected time for a multi-attribute query is O(log N) and the message passing number is O(log N)+O(k).

Original languageEnglish (US)
Title of host publicationProceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07
Pages266-273
Number of pages8
DOIs
StatePublished - Dec 1 2007
Externally publishedYes
Event2nd International Multi-Symposiums on Computer and Computational Sciences 2007, IMSCCS'07 - Iowa City, IA, United States
Duration: Aug 13 2007Aug 15 2007

Publication series

NameProceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07

Other

Other2nd International Multi-Symposiums on Computer and Computational Sciences 2007, IMSCCS'07
CountryUnited States
CityIowa City, IA
Period8/13/078/15/07

Keywords

  • DHT
  • Grid
  • Multi-attribute
  • Network
  • Peer-to-peer
  • Resource discovery
  • SkipMard

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'SkipMard: A multi-attribute peer-to-peer resource discovery approach'. Together they form a unique fingerprint.

  • Cite this

    He, T., Ni, J., Segre, A. M., Wang, S., & Knosp, B. M. (2007). SkipMard: A multi-attribute peer-to-peer resource discovery approach. In Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07 (pp. 266-273). [4392611] (Proceedings - 2nd International Multi-Symposiums on Computer and Computational Sciences, IMSCCS'07). https://doi.org/10.1109/IMSCCS.2007.4392611