{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1320883"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1320883","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Analysis and Implementation of Bracha's Consensus Algorithm","abstract":"Τα προβλήματα Συγκατάθεσης (Consensus) επικεντρώνονται στην συμφωνία ανάμεσα σε ένα σετ από ν διαφορετικούς κόμβους για μία συγκεκριμένη τιμή. Κάθε κόμβος διατηρεί μία προσωπική τιμή και μέχρι τ από αυτούς τους κόμβους μπορεί να παρουσιάζει σφάλματα ή κακόβουλη συμπεριφορά. Οι αλγόριθμοι Συγκατάθεσης είναι ένας αρκετά μελετημένο πρόβλημα στα Κατανεμημένα Συστήματα, με πολλές πρακτικές εφαρμογές όπως σε Αλγορίθμους εκλογής ηγέτη, ή το πρόβλημα της κατανεμημένης παράδοσης. Το πρόβλημα της Συγκατάθεσης αποτελεί και την βάση του γνωστού FLP συμπεράσματος, το οποίο δηλώνει ότι η το πρόβλημα αυτό δεν μπορεί να λυθεί σε ένα πλήρες ασύγχρονο κατανεμημένο περιβάλλον, ακόμα και με την παρουσία ενός και μόνο σφάλματος. Υπάρχει εκτενής βιβλιογραφία που προτείνει εναλλακτικές λύσεις για την \"παράκαμψη\" του FLP. Αυτές οι λύσεις συνήθως εισάγουν κάποιες υποθέσεις συγχρονισμού στο σύστημα ή χρησιμοποιούν τυχαιότητα. Πρωτόκολλα που χρησιμοποιούν τυχαιότητα μπορούν να χρησιμοποιηθούν για την λύση του προβλήματος Συγκατάθεσης σε ένα πλήρες ασύγχρονο σύστημα αφού εγγυώνται ενδεχόμενο τερματισμό μετά από ένα πιθανοτικό αριθμό γύρων. Μέχρι σήμερα, έχει προταθεί στην βιβλιογραφία ένας σημαντικά μεγάλος αριθμός τέτοιων αλγορίθμων, που λύνουν το πρόβλημα σε ασύγχρονο περιβάλλον. Παρόλαυτά με την τωρινή μας γνώση, κανείς από τους προτεινόμενους αλγορίθμους δεν έχει υλοποιηθεί σε ένα πραγματικό κατανεμημένο σύστημα και η απόδοσή τους δεν έχει αξιολογηθεί εξ' αιτίας πληθώρας προβλημάτων.Στην παρούσα διπλωματική εργασία, επικεντρωνόμαστε, μεταξύ άλλων, στον αλγόριθμο ασύγχρονης συγκατάθεσης του Bracha. Αναλύουμε τα θεωρητικά και πρακτικά προβλήματα και παρουσιάζουμε την δική μας υλοποίηση του πρωτοκόλλου. Καταλήγοντας, αξιολογούμε την απόδοσή του σε σχέση με την πολυπλοκότητα μηνυμάτων και προτείνουμε κάποια εναλλακτικές προσεγγίσεις για κάποια κομμάτια του πρωτοκόλλου, τα οποία μπορούν να βελτιώσουν την συνολική του απόδοση.","abstract_html":"Τα προβλήματα Συγκατάθεσης (Consensus) επικεντρώνονται στην συμφωνία ανάμεσα σε ένα σετ από ν διαφορετικούς κόμβους για μία συγκεκριμένη τιμή. Κάθε κόμβος διατηρεί μία προσωπική τιμή και μέχρι τ από αυτούς τους κόμβους μπορεί να παρουσιάζει σφάλματα ή κακόβουλη συμπεριφορά. Οι αλγόριθμοι Συγκατάθεσης είναι ένας αρκετά μελετημένο πρόβλημα στα Κατανεμημένα Συστήματα, με πολλές πρακτικές εφαρμογές όπως σε Αλγορίθμους εκλογής ηγέτη, ή το πρόβλημα της κατανεμημένης παράδοσης. Το πρόβλημα της Συγκατάθεσης αποτελεί και την βάση του γνωστού FLP συμπεράσματος, το οποίο δηλώνει ότι η το πρόβλημα αυτό δεν μπορεί να λυθεί σε ένα πλήρες ασύγχρονο κατανεμημένο περιβάλλον, ακόμα και με την παρουσία ενός και μόνο σφάλματος. Υπάρχει εκτενής βιβλιογραφία που προτείνει εναλλακτικές λύσεις για την &quot;παράκαμψη&quot; του FLP. Αυτές οι λύσεις συνήθως εισάγουν κάποιες υποθέσεις συγχρονισμού στο σύστημα ή χρησιμοποιούν τυχαιότητα. Πρωτόκολλα που χρησιμοποιούν τυχαιότητα μπορούν να χρησιμοποιηθούν για την λύση του προβλήματος Συγκατάθεσης σε ένα πλήρες ασύγχρονο σύστημα αφού εγγυώνται ενδεχόμενο τερματισμό μετά από ένα πιθανοτικό αριθμό γύρων. Μέχρι σήμερα, έχει προταθεί στην βιβλιογραφία ένας σημαντικά μεγάλος αριθμός τέτοιων αλγορίθμων, που λύνουν το πρόβλημα σε ασύγχρονο περιβάλλον. Παρόλαυτά με την τωρινή μας γνώση, κανείς από τους προτεινόμενους αλγορίθμους δεν έχει υλοποιηθεί σε ένα πραγματικό κατανεμημένο σύστημα και η απόδοσή τους δεν έχει αξιολογηθεί εξ&#x27; αιτίας πληθώρας προβλημάτων.Στην παρούσα διπλωματική εργασία, επικεντρωνόμαστε, μεταξύ άλλων, στον αλγόριθμο ασύγχρονης συγκατάθεσης του Bracha. Αναλύουμε τα θεωρητικά και πρακτικά προβλήματα και παρουσιάζουμε την δική μας υλοποίηση του πρωτοκόλλου. Καταλήγοντας, αξιολογούμε την απόδοσή του σε σχέση με την πολυπλοκότητα μηνυμάτων και προτείνουμε κάποια εναλλακτικές προσεγγίσεις για κάποια κομμάτια του πρωτοκόλλου, τα οποία μπορούν να βελτιώσουν την συνολική του απόδοση.","abstract_has_math":false,"creators":["Διαμαντόπουλος Παναγιώτης"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014","date_published":"2014","updated_at":"2026-11-19T05:26:32Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320883"],"render_values":[{"text":"uoadl:1320883","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320883","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1320883","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1320883","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Διαμαντόπουλος Παναγιώτης"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1320883","https://pergamos.lib.uoa.gr/uoa/dl/object/1320883"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Τα προβλήματα Συγκατάθεσης (Consensus) επικεντρώνονται στην συμφωνία ανάμεσα σε ένα σετ από ν διαφορετικούς κόμβους για μία συγκεκριμένη τιμή. Κάθε κόμβος διατηρεί μία προσωπική τιμή και μέχρι τ από αυτούς τους κόμβους μπορεί να παρουσιάζει σφάλματα ή κακόβουλη συμπεριφορά. Οι αλγόριθμοι Συγκατάθεσης είναι ένας αρκετά μελετημένο πρόβλημα στα Κατανεμημένα Συστήματα, με πολλές πρακτικές εφαρμογές όπως σε Αλγορίθμους εκλογής ηγέτη, ή το πρόβλημα της κατανεμημένης παράδοσης. Το πρόβλημα της Συγκατάθεσης αποτελεί και την βάση του γνωστού FLP συμπεράσματος, το οποίο δηλώνει ότι η το πρόβλημα αυτό δεν μπορεί να λυθεί σε ένα πλήρες ασύγχρονο κατανεμημένο περιβάλλον, ακόμα και με την παρουσία ενός και μόνο σφάλματος. Υπάρχει εκτενής βιβλιογραφία που προτείνει εναλλακτικές λύσεις για την \"παράκαμψη\" του FLP. Αυτές οι λύσεις συνήθως εισάγουν κάποιες υποθέσεις συγχρονισμού στο σύστημα ή χρησιμοποιούν τυχαιότητα. Πρωτόκολλα που χρησιμοποιούν τυχαιότητα μπορούν να χρησιμοποιηθούν για την λύση του προβλήματος Συγκατάθεσης σε ένα πλήρες ασύγχρονο σύστημα αφού εγγυώνται ενδεχόμενο τερματισμό μετά από ένα πιθανοτικό αριθμό γύρων. Μέχρι σήμερα, έχει προταθεί στην βιβλιογραφία ένας σημαντικά μεγάλος αριθμός τέτοιων αλγορίθμων, που λύνουν το πρόβλημα σε ασύγχρονο περιβάλλον. Παρόλαυτά με την τωρινή μας γνώση, κανείς από τους προτεινόμενους αλγορίθμους δεν έχει υλοποιηθεί σε ένα πραγματικό κατανεμημένο σύστημα και η απόδοσή τους δεν έχει αξιολογηθεί εξ' αιτίας πληθώρας προβλημάτων.Στην παρούσα διπλωματική εργασία, επικεντρωνόμαστε, μεταξύ άλλων, στον αλγόριθμο ασύγχρονης συγκατάθεσης του Bracha. Αναλύουμε τα θεωρητικά και πρακτικά προβλήματα και παρουσιάζουμε την δική μας υλοποίηση του πρωτοκόλλου. Καταλήγοντας, αξιολογούμε την απόδοσή του σε σχέση με την πολυπλοκότητα μηνυμάτων και προτείνουμε κάποια εναλλακτικές προσεγγίσεις για κάποια κομμάτια του πρωτοκόλλου, τα οποία μπορούν να βελτιώσουν την συνολική του απόδοση.","The Consensus problem focuses on the agreement among a set of n different nodes for a single data value. Each node holds a private value and up to t nodes might fail, be unreliable, or exhibit arbitrary (Byzantine) behaviour. Consensus is a heavily studied problem in distributed systems, with relevance to many critical applications, such as the distributed commit problem, leader election, and atomic broadcast. Consensus is also the basis of the famous FLP impossibility result, which states that in a purely asynchronous environment, there is no deterministic algorithm that can solve consensus even with one crash-fault. There is extensive bibliography suggesting alternatives for circumventing the FLP impossibility result, usually by adding some form of synchrony into the system or by using randomization. Randomized protocols are capable of solving the consensus problem in a completely asynchronous environment, since they guarantee eventual termination after a probabilistic number of rounds. Until now, a number of randomized algorithms have been proposed for solving consensus in asynchronous systems. However, to our knowledge, these proposed algorithms have not been implemented in a real distributed system and their performance has not been evaluated, due to a number of issues. In this thesis, we focus on Bracha's asynchronous consensus protocol among others. We analyze the theoretical and practical challenges and present our implementation of the protocol. Finally, we evaluate its performance, in terms of message and communication complexity, and propose some alternatives to certain components of the protocol, to improve its overall efficiency."]},{"key":"dc:title","label":"Title","values":["Analysis and Implementation of Bracha's Consensus Algorithm"]}]}],"canonical_facts":{"dc:creator":["Διαμαντόπουλος Παναγιώτης"],"dc:date":["2014"],"dc:description":["Τα προβλήματα Συγκατάθεσης (Consensus) επικεντρώνονται στην συμφωνία ανάμεσα σε ένα σετ από ν διαφορετικούς κόμβους για μία συγκεκριμένη τιμή. Κάθε κόμβος διατηρεί μία προσωπική τιμή και μέχρι τ από αυτούς τους κόμβους μπορεί να παρουσιάζει σφάλματα ή κακόβουλη συμπεριφορά. Οι αλγόριθμοι Συγκατάθεσης είναι ένας αρκετά μελετημένο πρόβλημα στα Κατανεμημένα Συστήματα, με πολλές πρακτικές εφαρμογές όπως σε Αλγορίθμους εκλογής ηγέτη, ή το πρόβλημα της κατανεμημένης παράδοσης. Το πρόβλημα της Συγκατάθεσης αποτελεί και την βάση του γνωστού FLP συμπεράσματος, το οποίο δηλώνει ότι η το πρόβλημα αυτό δεν μπορεί να λυθεί σε ένα πλήρες ασύγχρονο κατανεμημένο περιβάλλον, ακόμα και με την παρουσία ενός και μόνο σφάλματος. Υπάρχει εκτενής βιβλιογραφία που προτείνει εναλλακτικές λύσεις για την \"παράκαμψη\" του FLP. Αυτές οι λύσεις συνήθως εισάγουν κάποιες υποθέσεις συγχρονισμού στο σύστημα ή χρησιμοποιούν τυχαιότητα. Πρωτόκολλα που χρησιμοποιούν τυχαιότητα μπορούν να χρησιμοποιηθούν για την λύση του προβλήματος Συγκατάθεσης σε ένα πλήρες ασύγχρονο σύστημα αφού εγγυώνται ενδεχόμενο τερματισμό μετά από ένα πιθανοτικό αριθμό γύρων. Μέχρι σήμερα, έχει προταθεί στην βιβλιογραφία ένας σημαντικά μεγάλος αριθμός τέτοιων αλγορίθμων, που λύνουν το πρόβλημα σε ασύγχρονο περιβάλλον. Παρόλαυτά με την τωρινή μας γνώση, κανείς από τους προτεινόμενους αλγορίθμους δεν έχει υλοποιηθεί σε ένα πραγματικό κατανεμημένο σύστημα και η απόδοσή τους δεν έχει αξιολογηθεί εξ' αιτίας πληθώρας προβλημάτων.Στην παρούσα διπλωματική εργασία, επικεντρωνόμαστε, μεταξύ άλλων, στον αλγόριθμο ασύγχρονης συγκατάθεσης του Bracha. Αναλύουμε τα θεωρητικά και πρακτικά προβλήματα και παρουσιάζουμε την δική μας υλοποίηση του πρωτοκόλλου. Καταλήγοντας, αξιολογούμε την απόδοσή του σε σχέση με την πολυπλοκότητα μηνυμάτων και προτείνουμε κάποια εναλλακτικές προσεγγίσεις για κάποια κομμάτια του πρωτοκόλλου, τα οποία μπορούν να βελτιώσουν την συνολική του απόδοση.","The Consensus problem focuses on the agreement among a set of n different nodes for a single data value. Each node holds a private value and up to t nodes might fail, be unreliable, or exhibit arbitrary (Byzantine) behaviour. Consensus is a heavily studied problem in distributed systems, with relevance to many critical applications, such as the distributed commit problem, leader election, and atomic broadcast. Consensus is also the basis of the famous FLP impossibility result, which states that in a purely asynchronous environment, there is no deterministic algorithm that can solve consensus even with one crash-fault. There is extensive bibliography suggesting alternatives for circumventing the FLP impossibility result, usually by adding some form of synchrony into the system or by using randomization. Randomized protocols are capable of solving the consensus problem in a completely asynchronous environment, since they guarantee eventual termination after a probabilistic number of rounds. Until now, a number of randomized algorithms have been proposed for solving consensus in asynchronous systems. However, to our knowledge, these proposed algorithms have not been implemented in a real distributed system and their performance has not been evaluated, due to a number of issues. In this thesis, we focus on Bracha's asynchronous consensus protocol among others. We analyze the theoretical and practical challenges and present our implementation of the protocol. Finally, we evaluate its performance, in terms of message and communication complexity, and propose some alternatives to certain components of the protocol, to improve its overall efficiency."],"dc:identifier":["uoadl:1320883","https://pergamos.lib.uoa.gr/uoa/dl/object/1320883"],"dc:language":["English"],"dc:title":["Analysis and Implementation of Bracha's Consensus Algorithm"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:32Z"}