National and Kapodistrian University of Athens
Analysis and Implementation of Bracha's Consensus Algorithm
Abstract
dc:descriptionΤα προβλήματα Συγκατάθεσης (Consensus) επικεντρώνονται στην συμφωνία ανάμεσα σε ένα σετ από ν διαφορετικούς κόμβους για μία συγκεκριμένη τιμή. Κάθε κόμβος διατηρεί μία προσωπική τιμή και μέχρι τ από αυτούς τους κόμβους μπορεί να παρουσιάζει σφάλματα ή κακόβουλη συμπεριφορά. Οι αλγόριθμοι Συγκατάθεσης είναι ένας αρκετά μελετημένο πρόβλημα στα Κατανεμημένα Συστήματα, με πολλές πρακτικές εφαρμογές όπως σε Αλγορίθμους εκλογής ηγέτη, ή το πρόβλημα της κατανεμημένης παράδοσης. Το πρόβλημα της Συγκατάθεσης αποτελεί και την βάση του γνωστού FLP συμπεράσματος, το οποίο δηλώνει ότι η το πρόβλημα αυτό δεν μπορεί να λυθεί σε ένα πλήρες ασύγχρονο κατανεμημένο περιβάλλον, ακόμα και με την παρουσία ενός και μόνο σφάλματος. Υπάρχει εκτενής βιβλιογραφία που προτείνει εναλλακτικές λύσεις για την "παράκαμψη" του FLP. Αυτές οι λύσεις συνήθως εισάγουν κάποιες υποθέσεις συγχρονισμού στο σύστημα ή χρησιμοποιούν τυχαιότητα. Πρωτόκολλα που χρησιμοποιούν τυχαιότητα μπορούν να χρησιμοποιηθούν για την λύση του προβλήματος Συγκατάθεσης σε ένα πλήρες ασύγχρονο σύστημα αφού εγγυώνται ενδεχόμενο τερματισμό μετά από ένα πιθανοτικό αριθμό γύρων. Μέχρι σήμερα, έχει προταθεί στην βιβλιογραφία ένας σημαντικά μεγάλος αριθμός τέτοιων αλγορίθμων, που λύνουν το πρόβλημα σε ασύγχρονο περιβάλλον. Παρόλαυτά με την τωρινή μας γνώση, κανείς από τους προτεινόμενους αλγορίθμους δεν έχει υλοποιηθεί σε ένα πραγματικό κατανεμημένο σύστημα και η απόδοσή τους δεν έχει αξιολογηθεί εξ' αιτίας πληθώρας προβλημάτων.Στην παρούσα διπλωματική εργασία, επικεντρωνόμαστε, μεταξύ άλλων, στον αλγόριθμο ασύγχρονης συγκατάθεσης του Bracha. Αναλύουμε τα θεωρητικά και πρακτικά προβλήματα και παρουσιάζουμε την δική μας υλοποίηση του πρωτοκόλλου. Καταλήγοντας, αξιολογούμε την απόδοσή του σε σχέση με την πολυπλοκότητα μηνυμάτων και προτείνουμε κάποια εναλλακτικές προσεγγίσεις για κάποια κομμάτια του πρωτοκόλλου, τα οποία μπορούν να βελτιώσουν την συνολική του απόδοση.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Διαμαντόπουλος Παναγιώτης
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1320883