Σημειώσεις:Προβλήματα:Συναίνεση

Από DistrSys

“Κατανεμημένη Συναίνεση με Αποτυχίες Συνδέσεων”

{{Σε αυτό και τα επόμενα δύο κεφάλαια, μελετάμε τα προβλήματα της συναίνεσης σε ένα κατανεμημένο δίκτυο. Σε τέτοια προβλήματα, κάθε μια από τις διαδικασίες στο δίκτυο ξεκινάει με μια αρχική τιμή ενός συγκεκριμμένου τύπου και αναμένεται τελικά να παράξει μια τιμή του ίδιου τύπου. Τα αποτελέσματα απαιτείται να είναι τα ίδια, οι διεργασίες δηλαδή πρέπει να συμφωνήσουν -- ακόμα κι αν οι αρχικές τους τιμές είναι αυθαίρετες. Γενικά, υπάρχει μια συνθήκη εγκυρότητας η οποία περιγράφει τις επιτρεπόμενες τιμές εξόδου για κάθε πιθανό σύνολο εισόδων.}}

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

Τα προβλήματα συναίνεσης προκύπτουν σε πολλές κατανεμημένες εφαρμογές υπολογισμού. Παραδείγματος χάριν, οι διεργασίες μπορούν να προσπαθήσουν να επιτύχουν τη συμφωνία για το κατά πόσο θα επικυρώσουν ή θα απορρίψουν τα αποτελέσματα μιας κατανεμημένης συναλλαγής βάσεων δεδομένων. Ή παραδείγματος χάριν,οι διεργασίες μπορούν να προσπαθήσουν να συμφωνήσουν σχετικά με μια εκτίμηση του ύψους ενός αεροπλάνου βασισμένου στις τιμές κάποιων κατανεμημένων υψομετρητών.

Το ιδιαίτερο πρόβλημα συναίνεσης που παρουσιάζουμε σε αυτό το κεφάλαιο καλείται το πρόβλημα συντονισμένης επίθεσης. Είναι ένα θεμελιώδες πρόβλημα συναίνεσης και αφορά την περίπτωση όπου κάποια μηνύματα μπορούν να χαθούν. Αρχίζουμε με την παρουσίαση ενός βασικού αποτελέσματος αδυνάτου για τα αιτιοκρατικά συστήματα, και διερευνάμε έπειτα τις δυνατότητες για την τυχαία λύση. Δείχνουμε ότι το πρόβλημα μπορεί να λυθεί από έναν τυχαίο ο αλγόριθμο, με μια ορισμένη (ουσιαστική) πιθανότητα λάθους. Επιπλέον, εκείνη η πιθανότητα του λάθους αποδεικνύεται αναπόφευκτη.

“Η αιτιοκρατική έκδοση προβλήματος συντονισμένης επίθεσης”

Αρχίζουμε με την χαλαρή δήλωση του προβλήματος, από την άποψη ενός σεναρίου πεδίων μαχών:

Διάφοροι στρατηγοί προγραμματίζουν μια συντονισμένη επίθεση από διαφορετικές κατευθύνσεις, ενάντια σε έναν κοινό στόχο. Ξέρουν ότι ο μόνος τρόπος που η επίθεση μπορεί να πετύχει είναι εάν όλοι οι στρατηγοί επιτεθούν συντονισμένα! Εάν μόνο μερικοί από τους στρατηγούς επιτεθούν, οι στρατοί τους θα καταστραφούν. Κάθε επικεφαλής στρατηγός έχει μια αρχική επιλογή για εάν ο στρατός του είναι έτοιμος να επιτεθεί. Οι στρατηγοί βρίσκονται στις διαφορετικές θέσεις. Οι κοντινοί στρατηγοί μπορούν να επικοινωνήσουν, αλλά μόνο μέσω των αγγελιοφόρων που ταξιδεύουν με ”τα πόδια”. Εντούτοις, οι αγγελιοφόροι μπορούν να χαθούν ή να συλληφθούν, και τα μηνύματά τους μπορούν έτσι να χαθούν. Χρησιμοποιώντας μόνο αυτόν τον αναξιόπιστο τρόπο επικοινωνίας, οι στρατηγοί πρέπει να κατορθώσουν να συμφωνήσουν σχετικά με το κατά πόσο πρέπει να επιτεθούν. Επιπλέον, πρέπει να επιτεθούν εαν είναι δυνατόν.

(Υποθέτουμε ότι η «γραφική παράσταση επικοινωνίας» των στρατηγών είναι μη κατευθυνόμενη και συνδεμένη, και ότι όλοι οι στρατηγοί ξέρουν τη γραφική παράσταση. Επίσης υποθέτουμε ότι υπάρχει ένας γνωστός ανώτερος που δεσμεύεται στο χρόνο που παίρνει για έναν επιτυχή αγγελιοφόρο για να παραδώσει ένα μήνυμα.)

Εάν όλοι οι αγγελιοφόροι είναι αξιόπιστοι, κατόπιν όλοι οι στρατηγοί μπορούν να στείλουν τους αγγελιοφόρους σε όλους τους άλλους στρατηγούς (ενδεχομένως μέσω άλλων στρατηγών), λέγοντας εάν είναι ή όχι πρόθυμοι να επιτεθούν. Μετά από διάφορους «κύκλους» ίσους με τη διάμετρο της «γραφικής παράστασης επικοινωνίας», όλοι οι στρατηγοί θα έχουν αυτές τις πληροφορίες. Κατόπιν μπορούν όλοι να εφαρμόσουν έναν συνήθως συμφωνημένο κανόνα για να ληφθεί η ίδια απόφαση για να επιτεθούν: παραδείγματος χάριν, μπορούν να αποφασίσουν να επιτεθούν ακριβώς εάν όλοι οι στρατηγοί το επιθυμούν.

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

Το πραγματικό πρόβλημα της επιστήμης μας το οποίο μας ενδιαφέρει να μελετήσουμε, πίσω από αυτήν την περιγραφή είναι το πρόβλημα επικύρωσης (commit) για τις κατανεμημένες βάσεις δεδομένων. Αυτό το πρόβλημα περιλαμβάνει μια συλλογή διεργασιών που έχουν συμμετάσχει στην επεξεργασία της συναλλαγής βάσεων δεδομένων. Μετά από αυτήν την επεξεργασία, κάθε διαδικασία φθάνει σε μια αρχική «επιλογή» για εάν η συναλλαγή οφείλει να επικυρωθεί (δηλ., τα αποτελέσματά της να γίνουν μόνιμα και να απελευθερωθούν για τη χρήση άλλων συναλλαγών) ή να απορριφθεί. Μια διεργασία θα ευνοήσει γενικά να επικυρώσει τη συναλλαγή εάν όλος ο τοπικός υπολογισμός της για εκείνη τη συναλλαγής συναινεί. Οι διεργασίες αναμένεται να επικοινωνήσουν και τελικά να συμφωνήσουν σχετικά με μια από τις εκβάσεις, να επικυρώσουν ή να απορρίψουν. Εάν είναι δυνατόν, η έκβαση πρέπει να είναι "επικύρωση".

Θα ορίσουμε το πρόβλημα τυπικότερα αφαιρώντας τις ασάφειες. Εξετάζουμε n διεργασίες που συντάσσονται από 1 … n, τακτοποιημένες σε ένα αυθαίρετο μη κατευθυνόμενο δίκτυο, όπου κάθε διεργασία ξέρει την ολόκληρο το δίκτυο, συμπεριλαμβανομένων των ταυτοτήτων των διεργασιών. Κάθε διαδικασία αρχίζει με μια εισαγωγή μέσα στο πεδίο {0,1}. Χρησιμοποιούμε 1 για να δείξουμε «την επίθεση», ή επικύρωση, και 0 για να δείξουν «δεν επιτίθενται», ή απόρριψη. Χρησιμοποιούμε το ίδιο σύγχρονο πρότυπο με το οποίο έχουμε εργαστεί μέχρι τώρα, εκτός από το ότι τώρα επιτρέπουμε σε οποιοδήποτε αριθμό μηνυμάτων για να χαθούν κατά τη διάρκεια μιας εκτέλεσης του αλγορίθμου. Ο στόχος είναι όλες οι διαδικασίες τελικά να αποφασίσουν μέσα στο πεδίο {0,1}, ορίζοντας τη μεταβλητή "απόφαση" σε 0 ή 1. Υπάρχουν τρεις όροι που επιβάλλονται στις αποφάσεις που λαμβάνονται από τις διαδικασίες:

Συμφωνία:  Όλες οι διεργασίες αποφασίζουν την ίδια τιμή.

Εγκυρότητα:
1.   Εάν όλες οι διαδικασίες αρχίσουν με 0, τότε το 0 είναι η μόνη πιθανή επιλογή απόφασης.
2.   Εάν όλες οι διαδικασίες αρχίσουν με 1 και όλα τα μηνύματα παραδοθούν, κατόπιν 1 είναι η μόνη πιθανή επιλογή απόφασης.

Τερματισμός:  Όλες οι διαδικασίες αποφασίζουν τελικά.

Οι απαιτήσεις Συμφωνίας και Τερματισμού είναι οι φυσικές. Η απαίτηση Εγκυρότητας είναι μόνο μια δυνατότητα - υπάρχουν πολλές χρήσιμες εναλλακτικές λύσεις. Οι συνθήκες Εγκυρότητας, σε γενικές γραμμές, εκφράζουν την έννοια ότι η τιμή που αποφασίζεται πρέπει να είναι “εύλογη”. Για παράδειγμα, σε αυτή τη περίπτωση, που το τετριμμένο πρωτόκολλο πάντα αποφασίζει 0, έχει αποκλειστεί από το σκέλος 2 της απαίτησης Εγκυρότητας. Η ιδιαίτερη συνθήκη Εγκυρότητας που έχουμε αναφέρει παραπάνω είναι αρκετά αδύναμη: για παράδειγμα, εάν έστω και μια διαδικασία αρχίζει με 1, ο αλγόριθμος μπορεί να αποφασίσει 1. Εάν όλες οι διεργασίες αρχίζουν με 1 και ακόμη και ένα μήνυμα έχει χαθεί, ο αλγόριθμος μπορεί αποφασίσει 0. Αυτή η αδύναμη διατύπωση είναι κατάλληλη, επειδή κύριος στόχος μας σε αυτό το κεφάλαιο είναι τα αδύνατα αποτελέσματα. Αποδεικνύεται ότι ακόμα και αυτή η αδύναμη εκδοχή του προβλήματος είναι αδύνατο να λυθεί σε οποιοδήποτε γράφημα με δυο ή περισσότερους κόμβους.

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

Θεώρημα (Συντονισμένη επίθεση)

Έστω G το γράφημα που αποτελείτε από τους κόμβους 1 και 2, οι οποίοι συνδέονται με μια ακμή. Τότε, δεν υπάρχει αλγόριθμος που να λύνει το πρόβλημα της συντονισμένης επίθεσης στο G..

Απόδειξη:

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

☐

Έστω α η εκτέλεση που προκύπτει όταν και οι δυο διαδικασίες ξεκινούν με τιμή 1 και όλα τα μηνύματα παραδίδονται. Σύμφωνα με την απαίτηση Τερματισμού, και οι δυο τερματίζουν. Σύμφωνα με το σκέλος 2 της απαίτησης Εγκυρότητας, και οι δυο αποφασίζουν την τιμή 1. Υποθέτουμε ότι και οι δυο αποφασίζουν εντός r γύρων. Έστω τώρα η εκτέλεση α₁, ίδια με την α, με τη διαφορά ότι όλα τα μηνύματα μετά τους πρώτους r γύρους χάνονται. Στην α₁ και οι δυο διαδικασίες αποφασίζουν 1 εντός r γύρων. Το πρωτόκολλο επικοινωνίας της α₁ παρουσιάζετε στην Εικόνα 5.1. Οι ακμές αναπαριστούν τα μηνύματα που παραδίδονται. Δεν υπάρχουν ακμές για τα μηνύματα που στέλνονται αλλά δεν παραδίδονται.

Εικόνα 1 Σύνολο μηνυμάτων που στάλθηκαν στην εκτέλεση α₁

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

Έστω εκτέλεση α₂, ίδια με την α₁, με τη διαφορά ότι το τελευταίο μήνυμα (γύρος r) από την διαδικασία 1 προς την διαδικασία 2 δεν παραδίδεται (βλέπε Εικόνα 5.2). Στη συνέχεια, μολονότι η διαδικασία 2 μπορεί να μεταβεί σε διαφορετικές καταστάσεις μετά τον γύρο r στις εκτελέσεις α₁ και α₂, αυτή η διαφορετικότητα δεν ανακοινώνεται ποτέ στην διεργασία 1, ως εκ τούτου α₁ ~ α₂. Δεδομένου ότι η διεργασία 1 αποφασίζει 1 στην α₁, αποφασίζει επίσης 1 και στην α₂. Σύμφωνα με τις ιδιότητες τερματισμού και συμφωνίας, και η διεργασία 2 αποφασίζει τελικά 1 στην α2.

Εικόνα 2 Σύνολο μηνυμάτων που στάλθηκαν στην εκτέλεση α₂

Στη συνέχεια, έστω εκτέλεση α₃, ίδια με την α₂, με τη διαφορά ότι το τελευταίο μήνυμα από την διεργασία 2 στην διεργασία 1 χάνεται. Δεδομένου α₂ ~ α₃, η διεργασία 2 αποφασίζει 1 στην α₃, και σύμφωνα με τις ιδιότητες τερματισμού και συμφωνίας, το ίδιο κάνει και η διεργασία 1.

Συνεχίζοντας κατά αυτόν τον τρόπο, δηλαδή αφαιρώντας εναλλακτικά το τελευταίο μήνυμα από τις διεργασίες 1 και 2, φτάνουμε τελικά σε μια εκτέλεση α’ στην οποία και οι δυο διαδικασίες ξεκινούν με 1 και κανένα μήνυμα δεν παραδίδεται. Με την ίδια λογική όπως παραπάνω, οι δυο διεργασίες αποφασίσουν 1 και σε αυτήν την περίπτωση.

Αλλά ας εξετάσουμε τώρα την εκτέλεση α’’ στην οποία η διαδικασία 1 ξεκινά με 1 αλλά η διεργασία 2 ξεκινά με 0 και κανένα μήνυμα δεν παραδίδεται. Τότε α’’ ~ α’, και ως εκ τούτου η διεργασία 1 αποφασίζει ακόμα 1 στην α’’, το ίδιο κάνει και η διεργασία 2, σύμφωνα με τις ιδιότητες τερματισμού και την συμφωνίας. Αλλά α’’ ~ α’’’, όπου α’’’ η εκτέλεση στην οποία και οι δυο διαδικασίες ξεκινούν με 0 και κανένα μήνυμα δεν παραδίδεται. Έτσι η διεργασία 2 αποφασίζει 1 στην α’’’. Αλλά αυτό παράγει μια αντίφαση, καθώς το σκέλος 1 της συνθήκης εγκυρότητας, απαιτεί και οι δυο διεργασίες να αποφασίζουν 0 στην α’’’.

Το Θεώρημα 1 περιγράφει ένα θεμελιώδες όριο στις δυνατότητες των κατανεμημένων δικτύων. Προτείνει ότι υπάρχουν λίγα που μπορούν να γίνουν για την επίλυση βασικών προβλημάτων συναίνεσης, όπως είναι το πρόβλημα των κατανεμημένων βάσεων δεδομένων από την πλευρά των αναξιόπιστων επικοινωνιών. Ωστόσο, κάποιες εκδοχές αυτού του προβλήματος πρέπει να λυθούν σε συστήματα πραγματικού χρόνου. Για να αντιμετωπιστεί ο περιορισμός του παραπάνω Θεωρήματος, είναι αναγκαίο να ενισχυθεί το μοντέλο ή να χαλαρώσουν οι απαιτήσεις του προβλήματος.

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

“Κατανεμημένη Συναίνεση με Αποτυχίες Διεργασιών”

Σε αυτή την περίπτωση μελετάμε την περίπτωση όπου σφάλματα συμβαίνουν στις υπολογιστικές μονάδα(επεξεργαστές) του κατανεμημένου συστήματος και όχι στο δίκτυο επικοινωνίας. Είναι πιο φυσικό να μιλάμε για σφάλματα στις φυσικές διεργασίες παρά στις λογικές διεργασίες αλλά για να είμαστε συνεπείς με την ορολογία θα αναφερόμαστε γενικά στις διεργασίες. Θα αναλύσουμε δύο μοντέλα σφαλμάτων: το σφάλμα τερματισμού όπου κάποια ελαττωματική μονάδα μπορεί να σταματήσει ξαφνικά κατά την παραγωγή μηνυμάτων χωρίς προειδοποίηση και τα Βυζαντινά σφάλματα όπου το δίκτυο περιέχει ελαττωματικές διεργασίες που δεν σταματούν αλλά συνεχίζουν να εκτελούνται με ένα τελείως ανεξέλεγκτο τρόπο. Τα σφάλματα τερματισμού στοχεύουν στην μοντελοποίηση απρόβλεπτων σφαλμάτων στις διεργασίες. Τα βυζαντινά σφάλματα στοχεύουν στην μοντελοποίηση κάθε τύπου ελαττωματικής διεργασίας, συμπεριλαμβάνοντας, για παράδειγμα κάθε αποτυχία των στοιχείων μιας διεργασίας.

Ο όρος Βυζαντινά χρησιμοποιήθηκε αρχικά για αυτό τον τύπο των σφαλμάτων σε ένα paper από τους Lamport, Pease και Shostak στο οποίο διαπραγματευόταν ένα πρόβλημα συναίνεσης των Βυζαντινών στρατηγών. Οι Βυζαντινοί στρατηγοί προσπαθούσαν να αποφασίσουν στο αν διεξαχθεί ή όχι μια επίθεση. Σε αυτή την περίπτωση οι στρατηγοί δεν πρέπει να ανησυχούν για τα χαμένα μηνύματα αλλά για την πιθανότητα κάποιοι από τους στρατηγούς να τους προδώσουν. Ο όρος Βυζαντινά είναι απλά ένα λογοπαίγνιο. Η μάχη συμβαίνει στο αρχαίο Βυζάντιο και η συμπεριφορά κάποιων στρατηγών που είναι προδότες μπορεί να περιγραφεί μόνο με τον όρο Βυζαντινά.

Σε αυτό το συγκεκριμένο πρόβλημα συναίνεσης, το οποίο καλούμε agreement problem, οι διεργασίες ξεκινούν με μία αρχική τιμή από ένα συγκεκριμένο σύνολο V. Όλες οι διεργασίες στις οποίες δεν έχει συμβεί κάποιο σφάλμα, πρέπει να εξάγουν μία έξοδο, από το ίδιο σύνολο V, η οποία θα υπόκεινται στη συνθήκη εγκυρότητας και στη συνθήκη συμφωνίας. (Για τη συνθήκη εγκυρότητας, υποθέτουμε ότι αν όλες οι διεργασίες ξεκινούν με την ίδια αρχική τιμή u, η μόνη επιτρεπτή απόφαση είναι η u).

Το πρόβλημα συναίνεσης είναι μια απλοποιημένη έκδοση του προβλήματος που προέκυψε αρχικά κατά την ανάπτυξη των συστημάτων ελέγχου των αεροσκαφών. Σε αυτό το πρόβλημα, μια συλλογή διεργασιών κάθε μια από τις οποίες είχε πρόσβαση σε μία συσκευή υπολογισμού του υψομέτρου και κάποιες από αυτές ήταν λανθασμένες, προσπαθούσαν να αποφασίσουν για το ύψος του αεροσκάφους. Οι Βυζαντινοί αλγόριθμοι συναίνεσης έχουν ενσωματωθεί στο υλικό των συστημάτων που είναι ανεκτά σε σφάλματα. Εκεί χρησιμοποιούνται ώστε οι διεργασίες να μπορούν να εκτελούν υπολογισμούς συμφωνώντας στα αποτελέσματα κάθε βήματος. Αυτό επιτρέπει στις διεργασίες να ανέχονται Βυζαντινά σφάλματα που συμβαίνουν σε κάποια διεργασία. Οι Βυζαντινοί αλγόριθμοι συμφωνίας είναι επίσης χρήσιμοι όταν οι διεργασίες κάνουν λανθασμένες διαγνώσεις όπου μπορούν να επιτρέψουν σε μια συλλογή διεργασιών να συμφωνήσουν στον αριθμό των διεργασιών που έχουν αποτύχει(και πρέπει να αντικατασταθούν ή να αγνοηθούν).

Και στα δυο μοντέλα σφαλμάτων μας πρέπει να θέσουμε κάποιους περιορισμούς στην συχνότητα με την οποία συμβαίνουν σφάλματα στις διεργασίες. Πως πρέπει να εκφραστούν αυτοί οι περιορισμοί; Με άλλα λόγια στα συστήματα που υπάρχουν διεργασίες που αποτυγχάνουν, αυτοί οι περιορισμοί συχνά παίρνουν την μορφή κατανομών πιθανοτήτων που διαχειρίζονται τις περιπτώσεις σφαλμάτων. Εδώ παρότι χρησιμοποιούμε πιθανότητες, υποθέτουμε ότι ο αριθμός των διεργασιών που αποτυγχάνουν φράσσεται εκ των προτέρων από ένα σταθερό αριθμό f. Αυτή είναι μια απλή υπόθεση με την οποία δουλεύουμε ώστε να αποφύγουμε την πολυπλοκότητα ανάλυσης των πιθανοτικών σφαλμάτων που συμβαίνουν. Στην πραγματικότητα αυτή η υπόθεση μπορεί να είναι πραγματική υπό την έννοια ότι είναι απίθανο να συμβούν παραπάνω από f σφάλματα. Όμως πρέπει να έχουμε κατά νου ότι η υπόθεση αυτή μπορεί αν δημιουργήσει προβλήματα: στις περισσότερες πρακτικές εφαρμογές, αν ο αριθμός των σφαλμάτων είναι ήδη ψηλός, τότε είναι πιθανόν να συμβούν περισσότερα σφάλματα. Υποθέτοντας ένα όριο στον αριθμό των σφαλμάτων υπονοεί ότι τα σφάλματα είναι αρνητική συσχετισμένα, ενώ στην πράξη τα σφάλματα συνήθως είναι ανεξάρτητα ή θετικά συσχετισμένα.

Αφού ορίσαμε το πρόβλημα συμφωνίας, τόσο για τα τερματικά όσο και τα Βυζαντινά σφάλματα, παρουσιάζουμε ένα σύνολο από αλγορίθμους. Έτσι αποδεικνύουμε ένα κάτω όριο στον αριθμό των διεργασιών που απαιτούνται για να λύσουν το πρόβλημα με τα Βυζαντινά σφάλματα, και στον αριθμό των γύρων που απαιτούνται για να λύσουν το πρόβλημα για κάθε είδους σφαλμάτων.

Το πρόβλημα

Υποθέτουμε ότι το δίκτυό μας είναι ένα συνεκτικό μη κατευθυνόμενο δίκτυο με n κόμβους, 1, … …,n όπου κάθε διεργασία γνωρίζει ολόκληρο το γράφημα. Κάθε διεργασία ξεκινά με μία είσοδο από ένα σταθερό σύνολο V. Υποθέτουμε ότι για κάθε διεργασία υπάρχει ακριβώς μια αρχική κατάσταση η οποία περιλαμβάνει την τιμή εισόδου της. Σκοπός είναι οι διεργασίες μας να βγάλουν μια απόφαση στην έξοδο τους για το σύνολο V, με τον καθορισμό της κατάστασης απόφασης στις τιμές του συνόλου V. Χρησιμοποιούμε το μοντέλο συγχρονισμού, όμως επίσης επιτρέπουμε την πιθανότητα ένα περιορισμένος αριθμός διεργασιών(το πολύ f) να αποτύχουν. Επίσης υποθέτουμε ότι οι συνδέσεις στο δίκτυό μας είναι αξιόπιστες και όλα τα μηνύματα που στέλνονται, παραδίδονται. Θεωρούμε δύο ειδών σφαλμάτων: τα σφάλματα τερματισμού και τα Βυζαντινά σφάλματα.

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

Για τα σφάλματα τερματισμού, οι σωστές συνθήκες για το πρόβλημα συναίνεσης είναι:

Συμφωνία: καμία διεργασία δεν αποφασίζει διαφορετικές τιμές εξόδου

Εγκυρότητα: αν όλες οι ενεργές διεργασίες ξεκινήσουν με την ίδια τιμή u ϵ V, τότε η τιμή u είναι η μόνη πιθανή απάντηση για   τις ενεργές διεργασίες

Τερματισμός: όλες οι ενεργές διεργασίες τελικά αποφασίζουν

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

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

Συμφωνία: κανένα ζεύγος διεργασιών δεν μπορεί να αποφασίσει σε διαφορετική τιμή

Εγκυρότητα: αν όλες οι ενεργές διεργασίες ξεκινούν με την ίδια τιμή u ϵ V, τότε η τιμή u είναι η μόνη πιθανή απάντηση για τις ενεργές διεργασίες

Τερματισμός:όλες οι ενεργές διεργασίες τελικά αποφασίζουν(ίδια συνθήκη τερματισμού με παραπάνω)

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

Σχέση μεταξύ του προβλήματος συμφωνίας μεταξύ των Βυζαντινών σφαλμάτων και των σφαλμάτων τερματισμού:

Ένας αλγόριθμος που μπορεί να λύνει το πρόβλημα συμφωνίας σε Βυζαντινά σφάλματα, μπορεί αυτόματα να λύνει το πρόβλημα συμφωνίας σε σφάλματα τερματισμού. Η διαφορά είναι ότι στα σφάλματα τερματισμού απατούμε όλες οι ενεργές διεργασίες ακόμα και αυτές που θα αποτύχουν μελλοντικά να συμφωνούν. Αν η συνθήκη συμφωνίας για τα σφάλματα τερματισμού αντικατασταθεί για με την αντίστοιχη για τα Βυζαντινά σφάλματα τότε ο αλγόριθμος λειτουργεί κανονικά. Εναλλακτικά, αν όλες οι ενεργές διεργασίες στο Βυζαντινό αλγόριθμο πάντα αποφασίζουν στον ίδιο γύρο, τότε ο αλγόριθμος λειτουργεί και για τα σφάλματα τερματισμού.

Ισχυρότερη συνθήκη εγκυρότητας για τα σφάλματα τερματισμού:

Μια εναλλακτική συνθήκη εγκυρότητας η οποία μερικές φορές χρησιμοποιείται για τα σφάλματα τερματισμού είναι αυτή που ακολουθεί.

Εγκυρότητα:κάθε απόφαση για κάθε διεργασία είναι η αρχική τιμή κάποιων διεργασιών

Είναι εύκολο να δούμε ότι αυτή η συνθήκη εγκυρότητας υπονοεί την συνθήκη εγκυρότητας για την οποία έχουμε ήδη μιλήσει. Αυτή η συνθήκη εγκυρότητας χρησιμοποιείται στον ορισμό του προβλήματος k-agreement. Εδώ θα χρησιμοποιήσουμε την ασθενέστερη συνθήκη, αυτό μειώνει τις απαιτήσεις μας για τον αλγόριθμό και ενισχύει λίγο τα αδύνατα αποτελέσματα.

Μέτρηση πολυπλοκότητας:

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

Μειώνοντας την πολυπλοκότητα επικοινωνίας

Είναι δυνατό να μειωθεί το ποσό της επικοινωνίας απο τα O((f+1)n²) μηνύματα και τα O((f+1)n³b) δυαδικά ψηφία επικοινωνίας που χρησιμοποιούνται απο τον FloodSet. Για παράδειγμα, ο αριθμός των μηνυμάτων μπορεί να μειωθεί σε 2n² και ο αριθμός των δυαδικών ψηφίων επικοινωνίας σε O(2n²) χρησιμοποιώντας την παρακάτω απλή ιδέα. Παρατηρήστε ότι τελικά, κάθε διεργασία, i χρειάζεται να γνωρίζει τα ακριβή στοιχεία του συνόλου Wi αν |Wi | = 1, αλλιώς η i χρειάζεται να γνωρίζει το γεγονός ότι |Wi | ≥ 2. Συνεπώς είναι εύλογο κάθε διεργασία να ενδέχεται να χρειαστεί να αποστείλει σε όλες τις άλλες μόνο τις δύο πρώτες τιμές που έχει καταγράψει, αντί για όλες τις τιμές. Αυτή η ιδέα είναι η βάση του επόμενου αλγορίθμου.

Αλγόριθμοι που λύνουν το πρόβλημα της συναίνεσης υπο την παρουσία τερματικών σφαλμάτων και σφαλμάτων επικοινωνίας:

• FloodSet
• OptFloodSet

Διαφορετικοί τρόποι για να μειωθεί η πολυπλοκότητα επικοινωνίας. Υπάρχουν και άλλοι τρόποι για να μειωθεί η πολυπλοκότητα επικοινωνίας του FloodSet. Για παράδειγμα, ας θυμηθούμε πως εάν το V είναι διετεταγμένο πλήρως, ο κανόνας απόφασης μπορεί να τροποποιηθεί ώστε απλά για διαλέγει την ελάχιστη τιμή στο W. Έτσι είναι πιθανόν να τροποποιήσουμε τον FloodSet αλγόριθμο ώστε κάθε κόμβος μόνο να θυμάται και να αναμεταδίδει την ελάχιστη τιμή που έχει δεί μέχρι τώρα, αντί για όλες τις τιμές. Αυτός ο αλγόριθμος χρησιμοποιεί O((f + 1)n²b) δυαδικά ψηφία επικοινωνίας. Μπορεί να αποδειχτεί ορθός απο μια προσομοίωση που τον συσχετίζει με τον FloodSet (με τον τροποποιημένο κανόνα απόφασης). Αυτός ο αλγόριθμος ικανοποιεί την πιο ισχυρή συνθήκη εγκυρότητας του προηγούμενου τμήματος.