Αυτόνομα δίκτυα παγκόσμιας κλίμακας για τη διαχείριση και διάθεση πληροφορίας

Abstract

Structured peer-to-peer systems, or else Distributed Hash Tables (DHTs), are widely established as one of the most efficient platforms for global-scale, distributed data management. The resulting overlay networks tire based on the concept of equality and homogeneity of capabilities and obligations among participating parties. Their prominent features include scalability to extremely large network sizes and fault-tolerance. DHTs self-regulate and self-manage problems that may arise both at the layer of the physical infrastructure (unadvertised network connectivity failures, or unresponsiveness of computing systems hosting the overlay nodes), or the communication protocol (deliberate malicious behavior). The research presented in this dissertation, focuses on the fact that proposed DHT algorithms and implementations, succeed on delivering only a subset of data management operations, such as insertion and lookup based on an identification key. They do not allow altering information already stored and tied to a specific identifier, or searching and retrieving a range of keys (range queries). Although these functions represent important research targets in the field of databases (distributed or not) and many implementation options have been suggested in related literature, the applicability of corresponding algorithms in DHTs is limited by tire particular, peculiar characteristics of the P2P environment. A DHT is highly dynamic in nature, thus no specific node can be trusted to solitary handle information crucial to the completion of the distributed operation. Moreover, all operations should account for the special techniques employed by DHTs to distribute available data to participating peers. For example, the difficulty in supporting mutable data lies in the fact that each individual stored key-value pair is automatically copied to a dynamic set of nodes. For most widespread protocols, information, once stored in a DHT, cannot be changed. Accordingly, most DHT based range query implementations, are designed so that the search function runs on a separate layer of software, on top of the overlay, disregarding the existence of data replicas and without exploiting the network configuration, which already encodes peer and data relationships in its structure. We propose and evaluate the implementations of two alternatives for updating key-value pairs in DHTs: A lookup algorithm that helps in maintaining a loose consistency between multiple versions of data replicas, as well as a new DHT protocol - XOROS, based on the Kademlia routing scheme, which inherently supports serializable and consistent data changes. XOROS is also tolerant to “Byzantine” behavior - intentional non-compliance with its protocol by some participants. In addition, we present a protocol that addresses the problem of implementing complex, single or multi-dimensional range queries in DHTs. In all cases, the extra functionality is offered without sacrificing fundamental properties of the system, such as scalability and fault tolerance. Therefore, the resulting infrastructure for storing, retrieving and searching data can form the basis for supporting a multitude of novel, global-scale distributed applications. The proposed algorithms and protocols have been thoroughly evaluated, using a prototype integrated environment for implementing and evaluating P2P networks. Experimental results are used to assess how the various overlay parameters affect its performance and help in proposing directions for future work.