University of Patras
Ανάπτυξη και αξιοποίηση καινοτόμων συστημάτων παρακολούθησης, ελέγχου και εξεύρεσης καθολικών χαρακτηριστικών και ιδιοτήτων των οντοτή...
Abstract
dc:descriptionWithin the framework of this thesis we give a set of solutions to the central issue of designing and implementing distributed system architectures, protocols and algorithms that provide the necessary infrastructure for the computation of several basic global properties and variables of the state of a Peer-to-Peer (P2P) network. We discern two major types of such global properties: (a) properties pertaining to the nodes of the network and their characteristics (e.g. processing power, behavior, etc.) and (b) properties and variables of the objects/entities managed by the P2P network. To this extent we moved in two directions: (a) quantification and harnessing of the heterogeneity of the nodes in a P2P network, and (b) computation of estimates of global variables of the system, en route to supporting complex query processing in Internet-scale data management systems. First we present a new architectural paradigm for P2P networks, coined AESOP. We further provide experimental and analytical results that show significant gains in system performance and relevant costs. Under the light of our very promising results we put forth this paradigm as the way of architecting future P2P networks. Moreover, we deal with the problem of efficient range query processing in DHT-based P2P networks. The novelty of our approach lies in architectures, algorithms, and protocols for identifying and appropriately harnessing of powerful nodes in these networks. We then deal with the distributed estimation of global variables in P2P networks. First we preset Distributed Hash Sketches (DHS): a novel, fully decentralized mechanism, capable of providing estimates on the cardinality of multisets distributed over a structured P2P overlay network. Then, based on these results, we contribute efficient, accurate, and fully decentralized algorithms to compute basic aggregate queries, such as Count, CountDistinct, Sum, and Average. We also show how to construct distributed histograms of various types, ranging from simple Equi-Width and Average-Shifted Equi-Width, to more complex histogram types such as Equi-Depth, MaxDiff(V,F), and Compressed(V,F). Finally we present a full open-source implementation of the above tools, as well as an in-depth experimental evaluation with regard to their efficiency, accuracy, and scalability.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2008
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Ντάρμος, Νικόλαος
- Ntarmos, Nikolaos
Subjects
dc:subject × 16- Δίκτυα ομοτίμων εταίρων
- Κατανεμημένος έλεγχος και καταγραφή
- Κατανεμημένη εκτίμηση πληθαρίθμου
- Κατανεμημένη διατήρηση στατιστικών
- Επεξεργασία κατανεμημένων ερωτημάτων
- Βελτιστοποίηση κατανεμημένων ερωτημάτων
- Peer-to-peer networks
- Distributed auditing and accounting
- Distributed cardinality estimation
- Distributed statistics management
- Distributed query processing
- Distributed query optimization
- Natural Sciences
- Computer and Information Sciences
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/26358