Range Queries in Peer-to-Peer Systems
Christina Kaskoura · 2007
1. Motivation Peer-to-peer systems (P2P) are distributed systems which allow the sharing of resources in a decentralized and autonomous way. The nodes of the system (peers) are all equal and can join or leave the system whenever they want, thus making the peerto-peer network extremely dynamic. Since there is no one node or set of nodes responsible for routing and communication between peers, this is done through a selforganizing overlay network which runs on top of the physical network. Given the increased number of applications that are built over peer-to-peer networks, the development of such overlay structures that perform efficiently certain desired tasks is becoming a very important and interesting problem. In this project we concentrate on such overlay networks that facilitate the location of data in the peer-to-peer network. During the past few years, a big part of the research on peer-to-peer networks has concentrated on the issue of efficiently locating a value in a peer-to-peer system. This means that we need to determine which peer holds this value and retrieve it. A number of different solutions have been proposed for this problem, the most popular of which are based on a structure called a Distributed Hash Table (DHT). In DHTs the identifiers of the nodes participating in the peer-to-peer system are hashed as well as the keys of the data that is to be stored in the system. Then, the data is distributed among the nodes depending on their hash values and the hash values of the nodes, while algorithms are provided to determine in which node each key is (or should be) stored depending on its hash value. This way, the data and thus the load balance is evenly distributed among the peers. Different approaches to this problem mainly vary on the way they choose to distribute the data among the nodes. Chord for example [SMK+01] organizes the nodes in a modulo 2 ring where m the number of bits in the hashed ids of the keys and the nodes and assigns each key to the first node whose id is equal or follows the id of the key. Each node in the ring has pointers to the nodes that succeed it by 2 where and this way any value can be located efficiently in O(logn) steps. Pastry [RD01] on the other hand assigns each key to the node that is numerically closest to it. Routing is done by forwarding any query for a particular key at each step to a node that shares with the key a prefix that is at least b bits longer than that of the current node or one that is numerically closer to the key than the current node. m i ≤ ≤ 1