In this paper, we develop a scheme to recover a single erasure when using a Cartesian code,in the context of a distributed storage system. Particularly, we develop a scheme withconsiderations to minimize the associated bandwidth and maximize the associateddimension. The problem of recovering a missing node's data exactly in a distributedstorage system is known as theexact repair problem. Previous research has studied theexact repair problem for Reed-Solomon codes. We focus on Cartesian codes, and show wecan enact the recovery using a linear exact repair scheme framework, similar to the oneoutlined by Guruswami and Wooters in 2017. / Master of Science / Distributed storage systems are systems which store a single data file over multiple storage nodes. Each storage node has a certain storage efficiency, the "space" required to store the information on that node. The value of these systems, is their ability to safely store data for extended periods of time. We want to design distributed storage systems such that if one storage node fails, we can recover it from the data in the remaining nodes. Recovering a node from the data stored in the other nodes requires the nodes to communicate data with each other. Ideally, these systems are designed to minimize the bandwidth, the inter-nodal communication required to recover a lost node, as well as maximize the storage efficiency of each node. A great mathematical framework to build these distributed storage systems on is erasure codes. In this paper, we will specifically develop distributed storage systems that use Cartesian codes. We will show that in the right setting, these systems can have a very similar bandwidth to systems build from Reed-Solomon codes, without much loss in storage efficiency.

Αντικείμενο αυτής της διδακτορικής διατριβής είναι η μελέτη και η υλοποίηση ενός ολοκληρωμένου κατανεμημένου συστήματος διανομής δεδομένων σε πραγματικό χρόνο. Η ταχεία ανάπτυξη του Διαδικτύου και η πολυπλοκότητα των υπηρεσιών που προσφέρονται μέσα από αυτό έχει εξαντλήσει τα περιθώρια- όρια της κλασικής αρχιτεκτονικής του εξυπηρετητή και του πελάτη , καθώς, ο συνεχώς αυξανόμενος αριθμός χρηστών που ζητούν διάφορες υπηρεσίες δημιουργούν ένα τεράστιο φορτίο στους εξυπηρετητές, το οποίο δεν είναι σε θέση πια να ικανοποιήσουν. Η αρχιτεκτονική των διομότιμων συστημάτων αποτελεί σήμερα τον πιο υποσχόμενο αντικαταστάτη της αρχιτεκτονικής του εξυπηρετητή-πελάτη για την παροχή υπηρεσιών μέσω του Διαδικτύου. Η υπόθεση αυτή δικαιολογείται, αφού αξιοποιώντας τους πόρους των ίδιων των χρηστών, που αποτελούν πλέον ενεργό κομμάτι του συστήματος, η συγκεκριμένη αρχιτεκτονική μπορεί να εξασφαλίσει κλιμάκωση των συστημάτων αυτών σε αριθμό χρηστών αλλά και σε πόρους, του οποίους και αυτό-διαχειρίζονται για την παροχή οποιασδήποτε υπηρεσίας. Η ανάπτυξη, όμως, διομότιμων συστημάτων προϋποθέτει την επίλυση ενός συνόλου προβλημάτων που προκύπτουν από την κατανεμημένη φύση τους και την πολυπλοκότητα τους. Τα τελευταία χρόνια, η επιστημονική κοινότητα έχει ασχοληθεί εκτενώς με τα συστήματα αυτά και έχει προτείνει τρόπους επίλυσης των προβλημάτων που εμφανίζουν, οι οποίες όμως επικεντρώνονται σε συγκεκριμένες πτυχές τους, με αποτέλεσμα να μην προσφέρουν ακόμα δυνατότητες επαρκούς αξιοποίησης των πλεονεκτημάτων τους. Στην παρούσα διδακτορική διατριβή μελετήθηκαν η ανάπτυξη και η υλοποίηση ενός ολοκληρωμένου κατανεμημένου συστήματος διαμοιρασμού δεδομένων σε πραγματικό χρόνο. Το σύστημα αυτό αποτελείται από τρία διακριτά υποσυστήματα: 1. Ένα διομότιμο σύστημα για το διαμοιρασμό δεδομένων σε πραγματικό χρόνο. Το υποσύστημα αυτό αποτελείται από το γράφο διασύνδεσης των κόμβων που το συγκροτούν και το χρονοπρογραμματιστή που εκτελείται σε κάθε κόμβο. 2. Ένα σύστημα υποστήριξης, το οποίο είναι υπεύθυνο για την παρακολούθηση της λειτουργίας του υποσυστήματος διαμοιρασμού και την παροχή επιπλέον εύρους ζώνης, στην περίπτωση που δεν επαρκούν οι πόροι του πρώτου. 3. Ένα διομότιμο σύστημα για την αποθήκευση και την εύρεση των αντικειμένων που είναι διαθέσιμα προς διανομή μέσω του πρώτου υποσυστήματος. Για την ανάπτυξη του πρώτου υποσυστήματος, αρχικά διερευνήθηκε η φύση της εφαρμογής και ορίστηκαν τα επιθυμητά χαρακτηριστικά. Αυτά είναι ο μικρός χρόνος στησίματος, η ανοχή του σε δυναμικά φαινόμενα, όπως είναι η δυναμική συμπεριφορά των χρηστών και του φυσικού δικτύου, η ικανότητα κλιμάκωσης ως προς τον αριθμό των κόμβων και η ικανότητα για διαμοιρασμό δεδομένων με το μεγαλύτερο δυνατό ρυθμό υπό τον περιορισμό του μέσου εύρους ζώνης των κόμβων που αποτελούν το σύστημα. Στη συνέχεια ακολούθησε η μοντελοποίηση της λειτουργίας των συστημάτων κατανεμημένου διαμοιρασμού μέσα από την οποία προέκυψε η κατάλληλη αρχιτεκτονική ενός τέτοιου συστήματος που εγγυάται τη βέλτιστη εκπλήρωση των παραπάνω χαρακτηριστικών. Η προσφορά της παρούσας διατριβής στην έρευνα του επιστημονικού πεδίου των διομότιμων συστημάτων διαμοιρασμού δεδομένων σε πραγματικό χρόνο συνοψίζεται στα παρακάτω σημεία/συμπεράσματα : • Αντίθετα με τη μέχρι τώρα πρακτική που εφαρμόζεται στα συστήματα κατανεμημένου διαμοιρασμού, είναι αναγκαία η παράλληλη ανάπτυξη του γράφου διασύνδεσης και του χρονοπρογραμματιστή έτσι ώστε να μπορεί το κάθε υποσύστημα να χρησιμοποιήσει με βέλτιστο τρόπο τα χαρακτηριστικά του άλλου. • Ο γράφος διασύνδεσης πρέπει να αντικατοπτρίζει τη θέση των κόμβων στο φυσικό υποδίκτυο και να μπορεί να αυτό-οργανώνεται στις δυναμικές αλλαγές του δικτύου ή του πληθυσμού των κόμβων. • Η λειτουργία του χρονοπρογραμματιστή γίνεται πιο αποτελεσματική όταν διαχωρίζεται σε τρεις διαφορετικούς μηχανισμούς. Στο μηχανισμό δημιουργίας κουπονιών, στο μηχανισμό προ-ενεργής αίτησης πακέτου και στο μηχανισμό απόφασης επόμενου κόμβου προς αποστολή πακέτου. Τέλος, υλοποιήθηκαν κατανεμημένοι αλγόριθμοι για τη δημιουργία και την αυτό-οργάνωση του γράφου διασύνδεσης καθώς και οι απαραίτητοι αλγόριθμοι για την υλοποίηση του χρονοπρογραμματιστή. Οι αλγόριθμοι αυτοί σχεδιάστηκαν με τέτοιο τρόπο έτσι ώστε να χρησιμοποιούν ένα ελάχιστο ποσοστό του εύρους ζώνης των κόμβων χωρίς να συμβιβάζουν την αποτελεσματικότητα και την ταχύτητα σύγκλισής τους. Το δεύτερο ζήτημα που μελετήθηκε είναι η βοηθητική χρήση εξυπηρετητών με στόχο την αδιάλειπτη διάθεση απαραίτητων δικτυακών πόρων (εύρος ζώνης) που απαιτούνται από το σύστημα για τον πλήρη και συνεχή διαμοιρασμό του αντικειμένου. Αναλυτικότερα, ο σύγχρονος διαμοιρασμός βίντεο μέσω διομότιμων συστημάτων απαιτεί τη συνεχή ύπαρξη μέσου εύρους ζώνης συμμετεχόντων κόμβων μεγαλύτερο από το ρυθμό αναπαραγωγής του αντικειμένου που διαμοιράζεται. Αντιθέτως, λόγω της δυναμικής συμπεριφοράς των χρηστών και του απρόβλεπτου μέσου όρου εύρους ζώνης που διατίθεται από τους κόμβους οδηγούμαστε συχνά στη μη ομαλή λειτουργία του συστήματος ή/και στο διαμοιρασμό ενός αντικειμένου με μικρό ρυθμό αναπαραγωγής. Η επίλυση αυτού του προβλήματος απαιτεί την εξασφάλιση του ακριβούς και σε πραγματικό χρόνο υπολογισμού των διαθέσιμων πόρων του συστήματος. Επιπλέον, προϋποθέτει το σχεδιασμό μιας αρχιτεκτονικής που είναι κλιμακούμενη, δηλαδή επιτρέπει την παρακολούθηση συστημάτων στα οποία συμμετέχει πολύ μεγάλος αριθμός χρηστών. Παράλληλα, το προτεινόμενο σύστημα παρακολούθησης και ελέγχου του εύρους ζώνης πρέπει να εισάγει στο σύστημα όσο το δυνατόν μικρότερη κατανάλωση πόρων. Ομοίως, το εύρος ζώνης που συνεισφέρουν οι εξυπηρετητές πρέπει να ελαχιστοποιείται με στόχο την ελαχιστοποίηση του κόστους λειτουργίας. Τέλος, οι συνδέσεις που δημιουργούνται μεταξύ εξυπηρετητών και κόμβων πρέπει να εισάγουν με τη σειρά τους ελάχιστο φορτίο στο δίκτυο του προτεινόμενου συστήματος. Εκμεταλλευόμενοι, λοιπόν, τις ιδιότητες του χρονοπρογραμματιστή που αναπτύχθηκε είμαστε σε θέση μετρώντας ένα μικρό μόνο υποσύνολο κόμβων να εκτιμήσουμε γρήγορα και με ακρίβεια το συνολικό διαθέσιμο εύρος ζώνης του συστήματος. Επιπλέον, μετρώντας κάποιες παραμέτρους του χρονοπρογραμματιστή ανταλλαγής μπλοκ εκτιμούμε δυναμικά το φορτίο που αυτός εισάγει για διαμοιρασμό ανάλογα με τις επικρατούσες συνθήκες. Ο αριθμός των κόμβων αυτών είναι αρκετά μικρός και ανεξάρτητος από τον αριθμό των συμμετεχόντων κόμβων καθιστώντας το προτεινόμενο σύστημα ικανό για εξαιρετική κλιμάκωση. Με τις μετρήσεις αυτές γίνεται εφικτός ο υπολογισμός του εύρους ζώνης που απαιτείται από τους εξυπηρετητές για την ομαλή λειτουργία του συστήματος διαμοιρασμού. Τέλος, με τη βοήθεια ενός δυναμικά προσαρμόσιμου στο δίκτυο γράφου διασύνδεσης επιτυγχάνεται η μέγιστη εκμετάλλευση του εύρους ζώνης που συνεισφέρουν οι εξυπηρετητές και ο διαμοιρασμός του σε κόμβους με τη μικρότερη δυνατή δικτυακή καθυστέρηση. Το προτεινόμενο σύστημα αξιολογήθηκε σε κάθε είδους κατάσταση όπως: αυξομειούμενο μέσο εύρος ζώνης, γρήγορες μεταβολές στο μέσο εύρος ζώνης, μέσο εύρος ζώνης μεγαλύτερο και μικρότερο από το ρυθμό αναπαραγωγής. Η αξιολόγηση απέδειξε ότι ο πλήρης διαμοιρασμός του αντικειμένου, η ελαχιστοποίηση του εύρους ζώνης που συνεισφέρουν οι εξυπηρετητές μέσω της ακριβούς εκτίμησης των διαθέσιμων πόρων και η δυνατότητα εκτίμησης μέσω ενός μικρού υποσυνόλου συμμετεχόντων κόμβων είναι εφικτά κάτω από οποιεσδήποτε συνθήκες. Ο τρίτος στόχος που επιδιώξαμε να εκπληρώσουμε είναι η δημιουργία ενός κατανεμημένου συστήματος αποθήκευσης δεδομένων. Αυτό το σύστημα βασίστηκε στους Κατανεμημένους Πίνακες Κατακερματισμού (ΚΠΚ). Σκοπός αυτού του συστήματος είναι η δημιουργία ενός κατανεμημένου αποθηκευτικού χώρου, αποτελούμενου από πόρους των συμμετεχόντων κόμβων, για την αποθήκευση και ανάκτηση δεδομένων που πρόκειται να διαμοιραστούν. Οι απαιτήσεις ενός τέτοιου συστήματος περιλαμβάνουν την γρήγορη αναζήτηση δεδομένων, τη χρησιμοποίηση του μικρότερου δυνατού ποσοστού εύρος ζώνης για τη δρομολόγηση των αναζητήσεων, τη δυνατότητα εκτέλεσης σύνθετων αναζητήσεων και τη συμμέτοχη των κόμβων στο σύστημα ανάλογα με τους διαθέσιμους πόρους τους. Οι παραπάνω απαιτήσεις είναι αδύνατον να ικανοποιηθούν από έναν μόνο γράφο διασύνδεσης, καθώς προϋποθέτουν ετερόκλητα χαρακτηριστικά από το γράφο. Προκειμένου να είναι εφικτή η γρήγορη δρομολόγηση ο γράφος πρέπει να αντανακλά τη θέση των κόμβων στο φυσικό δίκτυο συνεπώς η εισαγωγή των κόμβων στον γράφο πρέπει επίσης να βασίζεται σε αυτό το χαρακτηριστικό. Η δυνατότητα για σύνθετες αναζητήσεις και η συμμετοχή των κόμβων ανάλογα με τους διαθέσιμους πόρους τους προϋποθέτει την μη ομοιόμορφη κατανομή των δεδομένων στο γράφο καθώς και επίσης και την εισαγωγή των κόμβων σε αυτόν ανάλογα με τους πόρους τους και τα δεδομένα που επιθυμούν να αποθηκεύσουν στο δίκτυο. Στα πλαίσια αυτής της διδακτορικής διατριβής προτείνεται ένα σύστημα κατανεμημένης αποθήκευσης το οποίο αποτελείται από δύο συνδεόμενους γράφους διασύνδεσης και μπορεί να ικανοποιήσει τις απαιτήσεις που έχουν τεθεί. Αυτοί οι δύο γράφοι είναι: • Ο γράφος διασύνδεσης και δρομολόγησης ο οποίος είναι υπεύθυνος για τη δρομολόγηση των αιτήσεων αναζήτησης. Οι κόμβοι εισέρχονται σε αυτόν ανάλογα με τη θέση τους στο φυσικό δίκτυο. Η παραπάνω συνθήκη συντελεί στην ταχύτατη δρομολόγηση των αιτήσεων αναζήτησης και τη χρησιμοποίηση ελάχιστου εύρους ζώνης για την εκτέλεσή τους. Για τη δημιουργία αυτού του γράφου αναπτύχτηκαν/σχεδιάστηκαν δύο κατανεμημένοι αλγόριθμοι. Ο πρώτος είναι υπεύθυνος για την εισαγωγή ενός κόμβου στο γράφο ανάλογα με τη θέση του στο φυσικό δίκτυο. Ο δεύτερος είναι υπεύθυνος για τη βελτιστοποίηση και προσαρμοστικότητα του γράφου στις δυναμικές αλλαγές των ιδιοτήτων του φυσικού δικτύου ή του πληθυσμού των συμμετεχόντων κόμβων. • Ο γράφος αποθήκευσης δεδομένων. Αυτός ο γράφος είναι υπεύθυνος για την αποθήκευση των δεδομένων στους κόμβους του συστήματος με τέτοιο τρόπο ώστε να είναι δυνατή η σύνθετη αναζήτησή τους καθώς επίσης και η αποθήκευσή τους ανάλογα με τους διαθέσιμους πόρους κάθε κόμβου. Η αξιολόγηση του συστήματος αυτού απέδειξε ότι ο διαχωρισμός της διαδικασίας δρομολόγησης από τη διαδικασία αποθήκευσης δεδομένων με την δημιουργία δύο ξεχωριστών γράφων διασύνδεσης εξασφαλίζει την εκπλήρωση όλων των απαιτήσεων ενός τέτοιου συστήματος. / The subject of this phd thesis is the study and development of a complete distributed system for real time data distribution. The rapid growth of the Internet and the complexity of the provided services, renders the investigation for a new architectural paradigm necessary, since classic server-client architecture has reached its full potential. The main reason for the above is that the continuously increasing number of users demanding a diversity of services generates an enormous overhead on the servers, that can’t be dealt with efficiently. Today, Peer-to-Peer architecture is considered to be the most promising replacement for client-server architecture for providing such services via the Internet. This assumption can be easily justified since, taking advantage of users resources, who now become active members of the system, peer-to-peer architecture can guarantee the scalability of these systems in respect to the number of participating users as well as the amount of data that they can manage. The development, however, of peer-to-peer systems requires the clarification of a set of problems which stem from their distributed nature and their complexity. In recent years, scientific community has been focusing on these systems suggesting a number of solutions, which, however, deal with certain only aspects of them, thus are unable to provide a holistic approach that could benefit from their numerous advantages. The complete distributed system for the real time distribution of data developed in the current dissertation thesis consists of three discrete subsystems: • a peer-to-peer live streaming system. This subsystem consists of an overlay, for the interconnection of peers, and a scheduler, which runs in every peer. • a supporting system, responsible for the monitoring of live streaming system and the supply of extra bandwidth in cases when peers’ aggregated resources are insufficient to sustain the streaming process • a peer-to-peer system for the storage and query of objects available for streaming, aided by the first subsystem described above. For the development of the first subsystem initially we investigated the nature of the application and defined the required characteristics. Those are the small setup time values, the tolerance of the system in dynamic conditions, like the dynamic behavior of the participating users and the dynamic conditions of the underlying network, the increased scalability concerning the number of supported users, and the ability to support streaming rates as high as possible having as constrain the aggregated upload bandwidth of the participating peers. The contribution of the present dissertation in the research of the scientific field of P2P real time data distribution systems is summarized below: 1. in contrast to contemporary practices regarding distributed live streaming systems the parallel development of the overlay and scheduler are necessary in order for the systems to be able to benefit from each other characteristics 2. the overlay should reflect the locations of the peers in the underlying network and be able to self-organize in response to dynamic changes of the peer population and the network conditions 3. the performance of the scheduler is enhanced when it comprises of three different mechanisms: the token generation algorithm, the mechanism of pro-active block request and the mechanism for selecting the next peer for packet transmitting. At last, distributed algorithms for the realization and self-organization of the overlay along with the necessary algorithms for the actualization of the scheduler were developed. These algorithms were designed in a way that allows for the usage of a small percentage of the nodes’ upload capacities without compromising the efficiency and the speed of their convergence A second subject that was studied was the use of supporting servers for the continuous provision of the required resources (upload bandwidth) for the complete and uninterrupted delivery of a stream. In more detail, peer-to-peer live streaming requires the constant presence of aggregated upload bandwidth greater than the rate of the stream being delivered. In contrast, the dynamic behavior of peers and the unpredictable upload bandwidth of nodes and of the conditions of the underlying network, often result in the disturbance of the streaming process and/or the delivery of a stream with low rate. Solving the above problems requires precise and real time monitoring of participating peers’ resources. Moreover, it assumes the development of an architecture which is scalable, allowing for the monitoring of systems with large peers number. Additionally, the proposed monitoring and bandwidth control system should introduce as little overhead as possible to the system, meaning that the amount of bandwidth used by the servers should be the minimum required to support peer-to-peer streaming system. Finally, connections established between servers and nodes should introduce, in their turn, the least possible overhead. Benefitting from the properties of our proposed peer-to-peer live streaming system’s scheduler we manage, by monitoring a small subset of participating peers, to measure with accuracy and in real time the aggregated upload bandwidth of the total participating peers. In addition, by measuring some parameters of the scheduler of bloc exchange we can dynamically estimate the overhead introduced for the distribution depending on the present conditions. The number of nodes is quite small and independent of the number of participant nodes allowing for the exceptional scalability of the proposed system. Because of these measurements the approximation of the bandwidth necessary for the successful performance of the distribution system becomes feasible. The evaluation process proved that the complete distribution of data, the minimization of the available servers bandwidth through the precise estimation of the available resources as well as the potential for estimation of a small subset of participating nodes are possible under any given circumstances. The third goal we tried to achieve is the development of a distributed data storage system. This system is based on DHTs. It aims to create a distributed storage space that consists of resources belonging to participating nodes, for the storage and retrieval of data about to be distributed. The prerequisites of such a system include: - fast routing process - usage of the smallest possible percentage of bandwidth for the querying process - the potential for execution of complex queries and - the participation of nodes in the system depending on their available recourses The above prerequisites can not be met by one only overlay, since they require diverse characteristics/ from the overlay. In order to achieve fast queries the overlay should reflect the location of all nodes in the physical network, therefore the introduction of nodes in the overlay should also rely on the above feature. The potential for complex queries and the participation of nodes depending on their available resources assumes a non-uniform node distribution in the overlay as well as the introduction of nodes in the system depending on their resources and the data needed to be stored in the network. In this work we propose a system for distributed storage that comprises of two interconnected overlays and can achieve all the demands set. The two overlays are described below: - LCAN is responsible for the routing process. Nodes enter this overlay in terms of their location on the physical network. The condition above leads to the fast routing of queries and the usage of the least possible bandwidth for their execution. In order to design this overlay the development of two distributed algorithms was necessary. The first one performs the introduction of nodes in the overlay according to their location in the network. The second distributed algorithm is responsible for the optimization and the adjustability of the overlay to the dynamic changes of the physical network properties or the participating nodes population. - VCAN. This is responsible for the storage of data in the nodes of the system in a way their storage according to each node’s available resources becomes feasible, while complex queries can be performed. The evaluation of the system has proved that the separation of the routing process from the data storage process with the creation of two separate overlays can result in the successful achievement of all prerequisites set by a distributed data storage system.