Ανάπτυξη και αξιοποίηση καινοτόμων συστημάτων παρακολούθησης, ελέγχου και εξεύρεσης καθολικών χαρακτηριστικών και ιδιοτήτων των οντοτή...

Abstract

Within 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.

Στο πλαίσιο της διδακτορικής διατριβής αυτής, δώσαμε ένα σύνολο λύσεων στο κεντρικό πρόβλημα του σχεδιασμού και της υλοποίησης κατανεμημένων αρχιτεκτονικών συστήματος, πρωτοκόλλων και αλγορίθμων που παρέχουν την αναγκαία υποδομή για τον υπολογισμό ορισμένων βασικών καθολικών ιδιοτήτων και μεταβλητών της κατάστασης ενός Δικτύου Ομοτίμων Εταίρων (ΔΟΕ). Μπορούμε να διακρίνουμε δύο κύριες διαστάσεις καθολικών ιδιοτήτων: (α) ιδιότητες που αναφέρονται στους κόμβους του δικτύου και τα ιδιαίτερα χαρακτηριστικά τους (υπολογιστική ισχύ, συμπεριφορά, κτλ.) και (β) ιδιότητες και μεταβλητές των αντικειμένων/δεδομένων που χειρίζεται το ΔΟΕ. Για το σκοπό αυτό, κινηθήκαμε προς δύο αλληλοσυμπληρούμενες κατευθύνσεις: (α) ποσοτικοποίηση και εκμετάλλευση της ετερογένειας των κόμβων ενός ΔΟΕ, και (β) υπολογισμός εκτιμήσεων καθολικών μεταβλητών του συστήματος, με απώτερο στόχο την υποστήριξη επεξεργασίας πολύπλοκων ερωτημάτων σε συστήματα διαχείρισης δεδομένων Διαδικτυακής κλίμακας. Πρώτα παρουσιάζουμε ένα νέο παράδειγμα αρχιτεκτονικής δόμησης των ΔΟΕ, το οποίο ονομάζουμε AESOP. Παρουσιάζουμε επίσης πειραματικά και αναλυτικά δεδομένα τα οποία δείχνουν σημαντικά κέρδη στην απόδοση καθώς και τα συναφή κόστη. Υπό το φως των πολλά υποσχόμενων αποτελεσμάτων αυτών, προτείνουμε αυτό το αρχιτεκτονικό παράδειγμα ως τον τρόπο δόμησης των ΔΟΕ του μέλλοντος. Ακόμα, ασχολούμαστε με το πρόβλημα της αποδοτικής επεξεργασίας ερωτημάτων εύρους σε ΔΟΕ βασισμένα σε DHT. Η καινοτομία της προτεινόμενης προσέγγισης βρίσκεται σε αρχιτεκτονικές, αλγορίθμους και πρωτόκολλα ταυτοποίησης και κατάλληλης εκμετάλλευσης δυνατών κόμβων των δικτύων αυτών. Κατόπιν, ασχολούμαστε με την κατανεμημένη εκτίμηση καθολικών μεταβλητών συστημάτων ΔOE. Αρχικά, παρουσιάζουμε τις Κατανεμημένες Συνόψεις Κατακερματισμού (DHS): έναν καινοτόμο, πλήρως κατανεμημένο μηχανισμό, ικανό για την παροχή εκτιμήσεων για τον πληθάριθμο πολυσυνόλων αντικειμένων σε ένα δομημένο δίκτυο επικάλυψης ομοτίμων εταίρων. Βασιζόμαστε στα αποτελέσματα αυτά και συνεισφέρουμε αποδοτικούς, ακριβείς και πλήρως κατανεμημένους αλγορίθμους οι οποίοι μπορούν να υπολογίσουν βασικά συναθροιστικά ερωτήματα, όπως τα Count, CountDistinct, Sum και Average. Δείχνουμε ακόμα πως μπορούν να κατασκευαστούν κατανεμημένα ιστογράμματα διαφόρων ειδών, από τα απλά ιστογράμματα τύπου Equi-Width και Average-Shifted Equi-Width, ως και πιο πολύπλοκα ιστογράμματα όπως τα Equi-Depth, MaxDiff(V,F) και Compressed(V,F). Τέλος, παρουσιάζουμε μία πλήρη υλοποίηση ανοιχτού κώδικα των παραπάνω εργαλείων, καθώς και μία εμπεριστατωμένη πειραματική αξιολόγησή τους, όσον αφορά τους τομείς της απόδοσης, της ακρίβειας και της κλιμακωσιμότητας.