SkiPeR: A Family of Distributed Range Addressing Spaces for Peer-to-Peer Systems

摘要

A relational database management system based on a peer-to-peer network must support both exact-match and range selection predicates efficiently. One approach to process range predicates is to design and implement a distributed range addressing space in support of decentralized routing of predicates, insertion and removal of peers. To route predicates in O(log N) with a N peer system, two alternative approaches have been proposed. The first, Skip Graphs [2, 9], employs a hierarchical order-preserving structure on the peers and their assigned ranges. The second, PePeR [6], constructs multiple ranges per peer and controls their assignment across the peers intelligently. The primary contribution of this paper is SkiPeR, a general purpose technique that unifies Skip Graphs and PePeR. SkiPeR consists of two key parameters whose extreme settings correspond to Skip Graphs and PePeR. There are in-between parameter settings that are a tradeoff between the amount of state information maintained by each peer, continued routing of predicates in the presence of peer removal, and the number of hops required to route a predicate. A secondary contribution of this study is to quantify these tradeoffs. This enables a system designer to choose parameters settings that fit the requirements of an application and the characteristics of the underlying peer-to-peer network.