Σημειώσεις:Κατανεμημένοι Αλγόριθμοι:FloodSet

Από DistrSys

FloodSet
Πρόβλημα: Συναίνεση Δίκτυο: Πλήρες Κλάση: Αποκεντρωτικός

Πολυπλοκότητα
Χρονική: f+1 Επικοινωνίας: (f+1)n²

Στη σύνταξη του κειμένου συνεισέφερε η Μανέττα Νικολίτσα

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

Ο βασικός αλγόριθμος

Το πρόβλημα συναίνεσης για τα σφάλματα τερματισμού έχει ένα πολύ απλό αλγόριθμο, ο οποίος ονομάζεται FloodSet. Οι διεργασίες απλά εκπέμπουν όλες τις τιμές από το σύνολο V που έχουν λάβει μέχρι τώρα και χρησιμοποιούν έναν απλό τρόπο για να πάρουν μια απόφαση.

Αλγόριθμος Floodset

Κάθε διεργασία διατηρεί μια μεταβλητή W η οποία περιέχει ένα υποσύνολο του συνόλου V. Αρχικά η μεταβλητή W της i-οστής διεργασίας περιέχει μόνο την αρχική τιμή της i. Σε κάθε ένα από τους f+1 γύρους, κάθε διεργασία εκπέμπει το W, και έπειτα προσθέτει όλες τα νέα στοιχεία που έλαβε στη W. Μετά από f+1 γύρους, η i-οστής διεργασία εφαρμόζει τον κανόνα απόφασης. Αν η μεταβλητή W περιέχει μόνο μία τιμή τότε η διεργασία i αποφασίζει το μοναδικό αυτό στοιχείο της μεταβλητής W, διαφορετικά αποφασίζει την προκαθορισμένη τιμή u₀.}}

Ψευδοκώδικας Floodset(επίσημα)

Το αλφάβητο του μηνύματος αποτελεί υποσύνολο του V


''Κατάσταση i''

γύροι ϵ N

απόφαση ϵ V ∪ {unknown}, αρχικά unknown

W υποσύνολο του V αρχικά περιέχει μόνο μία τιμή η οποία είναι η αρχική τιμή της i-οστης διεργασίας.


''Μήνυμα i''

Αν γύροι ≤ f τότε στείλε το W σε όλες τις άλλες διεργασίες


''Μετάβαση i''

γύροι = γύροι + 1

Έστω ότι X_j είναι το μήνυμα από τη διεργασία j, για κάθε διεργασία j απ’ όπου ένα μήνυμα λαμβάνεται. 

W = W  ∪ (∪_j Xj)


Αν γύροι = f+1 τότε

*Αν |W| = 1 τότε απόφαση=u όπου W= {u}
*Αλλιώς απόφαση=u₀

Για την απόδειξη της ορθότητας του αλγορίθμου Floodset, χρησιμοποιούμε το συμβολισμό W_i(r) για να δηλώσουμε την μεταβλητή W της διεργασίας i μετά από r γύρους. Ως συνήθως χρησιμοποιούμε το δείκτη i για να δηλώσουμε την κατάσταση μια μεταβλητής που ανήκει στη διεργασία i. Λέμε ότι μια διεργασία i είναι ενεργή μετά από r γύρους, αν αυτή δεν έχει αποτύχει μέχρι το τέλος του γύρου r.

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

Λήμμα (FloodSet.1)

Αν καμία διεργασία δεν αποτύχει κατά τη διάρκεια ενός συγκεκριμένου γύρου r, όπου 1≤r≤f+1, τότε W_i(r)= W_j(r), για όλα τις διεργασίες i, j οι οποίες είναι ενεργές μέχρι το γύρο r..

Απόδειξη:

Έστω ότι καμία διεργασία δεν έχει αποτύχει κατά τον γύρο r και έστω I το σύνολο των διεργασιών οι οποίες είναι ενεργές μετά από r γύρους(ή ισοδύναμα μετά από r-1 γύρους). Τότε επειδή κάθε διεργασία στο σύνολο I στέλνει τη δική της μεταβλητή W σε όλες τις άλλες διεργασίες, στο τέλος του γύρου r, το σύνολο W κάθε διεργασίας που ανήκει στο σύνολο I είναι ακριβώς το σύνολο τιμών οι οποίες κρατιόντουσαν από τις διεργασίες στο σύνολο I πριν το γύρο r

☐

Στη συνέχεια ισχυριζόμαστε ότι εάν όλες οι ενεργές διεργασίες έχουν το ίδιο σύνολο W μετά από ένα συγκεκριμένο γύρο r, τότε αυτό ισχύει και μετά από τους γύρους που ακολουθούν.

Λήμμα (FloodSet.2)

Έστω ότι W_i(r)= W_j(r) για όλες τις διεργασίες i,j οι οποίες είναι ενεργές μετά από r γύρους. Τότε για κάθε γύρο r’, r ≤ r’ ≤ f+1, για κάθε ζεύγος διεργασιών i,j οι οποίες είναι ενεργές μετά από r΄ γύρους ισχύει W_i(r’)= W_j(r’).

Απόδειξη:

Η απόδειξη αφήνεται σαν άσκηση

☐

Το ακόλουθο λήμμα είναι σημαντικό για την ιδιότητα της συμφωνίας.

Λήμμα (FloodSet.3)

Για κάθε ζεύγος διεργασιών i,j που είναι ενεργές μετά από f+1 γύρους, ισχύει W_i= W_j στο τέλος του γύρου f+1.

Απόδειξη:

Εφόσον παρουσιάζονται μόνο f σφάλματα θα υπάρχει ένας γύρος r, 1≤r≤f+1, κατά τον οποίο καμία διεργασία δεν θα αποτύχει. Από το λήμμα 1 δείξαμε ότι ισχύει W_i(r)= W_j(r) για όλες τις διεργασίες i,j οι οποίες είναι ενεργές μετά από r γύρους. Από το λήμμα 2 δείξαμε ότι ισχύει W_i(f+1)= W_j(f+1) για όλες τις διεργασίες i,j οι οποίες είναι ενεργές μετά από r γύρους

☐

Θεώρημα (FloodSet.1)

Ο αλγόριθμος Floodset λύνει το πρόβλημα της συναίνεσης στην περίπτωση των σφαλμάτων τερματισμού.

Απόδειξη:

Η συνθήκη τερματισμού είναι προφανής από τον κανόνα απόφασης. Για τη συνθήκη εγκυρότητας υποθέτουμε ότι όλες οι αρχικές τιμές των διεργασιών είναι ίσες με την τιμή u. Οπότε η τιμή u είναι η μοναδική που στέλνεται. Κάθε σύνολο W_i(f+1) δεν είναι ποτέ άδειο γιατί περιέχει την αρχική τιμή της i-οστης διεργασίας. Για αυτό κάθε W_i(f+1) πρέπει να είναι ακριβώς ίσο με την τιμή u, έτσι ο κανόνας απόφασης λέει ότι η τιμή u είναι η μόνη πιθανή απόφαση

☐

Για τη συνθήκη συμφωνίας, ας υποθέσουμε ότι i, j είναι οποιεσδήποτε δύο διεργασίες που αποφασίζουν. Αφού οι αποφάσεις παίρνονται μόνο στο τέλος του γύρου f+1, αυτό συνεπάγεται ότι οι διεργασίες i, j είναι ενεργές στο τέλος του γύρου f+1. Από το λήμμα 3 συνεπάγεται ότι W_i(f+1)= W_j(f+1). Από τον κανόνα απόφασης συνεπάγεται ότι οι διεργασίες i και j παίρνουν την ίδια απόφαση.

Ανάλυση πολυπλοκότητας:

Ο αλγόριθμος Floodset απαιτεί ακριβώς f+1 γύρους μέχρι όλες οι ενεργές διεργασίες να αποφασίσουν. Ο συνολικός αριθμός μηνυμάτων είναι O((f+1)n²). Κάθε μήνυμα αποτελείται από ένα σύνολο το πολύ n στοιχείων(αφού κάθε στοιχείο πρέπει να είναι η αρχική τιμή κάποιων διεργασιών), έτσι το πλήθος των bits ανά μήνυμα είναι O(nb). Έτσι το συνολικό πλήθος των bits επικοινωνίας είναι O((f+1)n³b)

Εναλλακτικός κανόνας απόφασης:

Ο κανόνας απόφασης για τον αλγόριθμο Floodset είναι κάπως αυθαίρετος. Αφού ο αλγόριθμος Floodset εγγυάται ότι όλες οι διεργασίες έχουν το ίδιο σύνολο W μετά από f+1 γύρους, διάφοροι άλλοι κανόνες απόφασης θα μπορούσαν να παρθούν, οι οποίοι επίσης θα δούλευαν σωστά εφόσον όλες οι διεργασίες ακολουθούν τον ίδιο κανόνα. Για παράδειγμα, αν οι τιμές στο σύνολο V ήταν διαταγμένες τότε όλες οι διεργασίες θα μπορούσαν να επιλέξουν την ελάχιστη τιμή στο σύνολο W. Αυτός ο εναλλακτικός κανόνας έχει το πλεονέκτημα ότι εξασφαλίζεται η ισχυρή συνθήκη εγκυρότητας που αναφέρεται παραπάνω. Ο κανόνας απόφασης για τον αλγόριθμο Floodset δεν εγγυάται αυτή την ισχυρή συνθήκη γιατί η προκαθορισμένη τιμή u₀, μπορεί να μην είναι η αρχική τιμή για όλες τις διεργασίες.

Οι διεργασίες σε σχέση με τα σφάλματα επικοινωνίας:

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

Στη συνέχεια ακολουθεί ένα παράδειγμα εκτέλεσης του αλγορίθμου Floodset:

Πλήρες δίκτυο τεσσάρων κόμβων. Κάθε κόμβος (διεργασία) δέχεται σαν είσοδο μια αρχική τιμή

Κατά τον πρώτο γύρο εκτέλεσης του αλγορίθμου συμβαίνει ένα σφάλμα επικοινωνίας στην διεργασία 3 κατά την αποστολή ενός μηνύματος στη διεργασία 1. Οι υπόλοιπες διεργασίες του δικτύου μας αποθηκεύουν σε μία λίστα τις τιμές και τις διεργασίες από τις οποίες τις λαμβάνουν.

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

Στον τρίτο γύρο εκτέλεσης του αλγορίθμου δεν συμβαίνει κανένα σφάλμα. Οπότε οι διεργασίες 1 και 2 οι οποίες είναι οι μοναδικές ενεργές ανταλλάσουν ορθά τα μηνύματά τους