Back to search

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

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Διαμαντόπουλος Παναγιώτης. Analysis and Implementation of Bracha's Consensus Algorithm. 2014. https://pergamos.lib.uoa.gr/uoa/dl/object/1320883