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

Από DistrSys

OptFloodSet

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

Πολυπλοκότητα

Χρονική: f+1 Επικοινωνίας: 2n2

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

Ο αλγόριθμος OptFloodSet λύνει το πρόβλημα της συναίνεσης σε ένα πλήρες δίκτυο διεργασιών. Επιτυγχάνει μικρότερο αριθμό μηνυμάτων και δυαδικών ψηφίων επικοινωνίας συγκριτικά με τον αλγόριθμο FloodSet, επειδή αξιοποιεί πλήρως το κανόνα απόφασης. Αναλυτικότερα, στον πρώτο γύρο κάθε μια διεργασία χωρίς βλάβη αποστέλλει σε όλες τις άλλες την αρχική της τιμή v₀, στο τέλος του γύρου η κάθε μια ενθέτει στην λίστα της W_i τις τιμές που παρέλαβε επιτυχώς. Έπειτα κάθε διεργασία i, χωρίς σφάλμα, στέλνει μια μόνο φορά μια τιμή της λίστας της σε όλες τις άλλες. Ανάλογα με τον πρώτο γύρο, κάθε διεργασία ενθέτει στην λίστα της τις παραληφθείσες τιμές. Έτσι μετά το πολύ απο f+1 γύρους κάθε διεργασία i η οποία δεν έχει τερματίσει λόγω σφάλματος θα έχει είτε ένα είτε τουλάχιστον δύο στοιχεία στην W_i λίστα της. Οπότε σύμφωνα με το κανόνα απόφασης όλες οι ενεργές διεργασίες μπορούν να συναινέσουν.

Εσωτερικές μεταβλητές Άνω φράγμα αριθμού σφαλμάτων f Αρχική τιμή vi ( i ≠ 0 ), προκαθορισμένη τιμή v0, σύνολο W αρχικά ίσο με {vi} Μεταβλητή απόφασης απόφαση

Αρχική Γνώση Οι διεργασίες γνωρίζουν την ταυτότητα τους Γνωρίζουν το πλήθος n των διεργασίων του δικτύου και τις ταυτότητες τους (=> γνώση της τοπολογίας του δικτύου) Το δίκτυο είναι πλήρες γράφημα Γνώση αρχικής και προκαθορισμένης τιμής vi και v0 αντίστοιχα Οι διεργασίες γνωρίζουν το μέγιστο αριθμό σφαλμάτων f στο δίκτυο

Λειτουργία Στον πρώτο γύρο κάθε διεργασία στέλνει (σε όλες τις άλλες) την αρχική της τιμής v0. Στο πρώτο γύρο που γνωρίζει μια διαφορετική τιμή v απο την v0, την στέλνει σε όλες τις άλλες διεργασίες. Μετά απο f+1 γύρους, κάθε διεργασία, με ταυτότητα i, εξετάζει αν το σύνολο Wi έχει ένα στοιχείο ή περισσότερα. Στην πρώτη περίπτωση αποφασίζει την αρχική της τιμή vi, αλλίως αποφασίζει την προκαθορισμένη τιμή v0.

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

καταστάσειςi:

γύροι Є Ν, αρχικά 0
απόφαση Є V U {άγνωστο}, αρχικά άγνωστο
W υποσύνολο του V, αρχικά ίσο με {vi}
εύρεση διαφορετικής τιμής = όχι

μηνύματαi:

Αν ( γύροι ≤ f και εύρεση διαφορετικής τιμής = όχι ) τότε
   
   Αν ( |W| ≥ 2) τότε
      νέα τιμή = πάρε τυχαία μια τιμή του W-{vi}
      εύρεση διαφορετικής τιμής = ναι
   
   Αλλιώς
      νέα τιμή = W //=vi
      στείλε την νέα τιμή σε όλες τις άλλες διεργασίες

μεταβάσειςi:

γύροι = γύροι + 1
Έστω το μήνυμα Xj  απο την διεργασία j,
Για κάθε j απο το οποίο φτάνει ένα μήνυμα
   W = W U (UjXj)

Αν γύροι = f + 1 τότε
   Αν |W| = 1 τότε απόφαση = v,  όπου W = {v}
   Αλλιώς απόφαση = v0

Ανάλυση Πολυπλοκότητας. Ο αριθμός γύρων εκτέλεσης για τον OptFloodSet είναι οι ίδιοι με αυτούς για τον FloodSet, f + 1. Ο αριθμός μηνυμάτων είναι το πολύ 2n², αφού κάθε διεργασία στέλνει το πολύ δύο μη-κενά μηνύματα σε κάθε άλλη διεργασία. Ο αριθμός των δυαδικών ψηφίων επικοινωνίας είναι O(n²b). Αποδεικνύουμε την ορθότητα του OptFloodSet συσχετίζοντας τον με τον FloodSet χρησιμοποιώντας μια προσομοίωση συσχέτισης (μια όμοια λογική χρησιμοποιήθηκε στην ενότητα εκλογής αρχηγού για να αποδειχτεί η ορθότητα του OptFloodMax συσχετίζοντας τον με τον FloodMax). Αυτή η προσομοίωση απαιτεί πρώτα να συμπληρωθούν οι λεπτομέρειες στην περιγραφή του OptFloodSet, που περιλαμβάνουν ρητό αριθμό γύρων, απόφαση και στοιχείων του συνόλου W όπως στον FloodSet. Χρησιμοποιούμε τον συμβολισμό Wi(r) και OWi(r), αντίστοιχα, για να δηλώσουμε τις τιμές του Wi μετά απο r γύρους εκτέλεσης του FloodSet και OptFloodSet, αντίστοιχα. Το επόμενο λήμμα περιγράφει την διάδοση μηνυμάτων στον FloodSet.

Σημείωση: num(A) = |A|, δηλαδή αριθμός στοιχείων του συνόλου Α (ή πληθάριθμος του Α).

Λήμμα (OptFloodSet.1)

Στον FloodSet, έστω ότι η i στέλνει ένα μήνυμα στην j στον γύρο r+1, και η j το λαμβάνει και το επεξεργάζεται.

Τότε το W_i(r) είναι υποσύνολο του W_j(r+1)..

Απόδειξη:

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

☐

Η βασική ιδιότητα μείωσης του OptFloodSet περιλαμβάνεται στο επόμενο λήμμα.

Λήμμα (OptFloodSet.2)

Στον FloodSet, έστω ότι η i αποστέλλει μήνυμα στην j στον γύρο r + 1 και η j το λαμβάνει και το επεξεργάζεται.

Τότε

 1. Αν num(OWi (r)) = 1, τότε το OWi(r) είναι υποσύνολο του OWj(r+1).
       
 2. Αν num(OWi (r)) ≥ 2, τότε num(OWj (r+1)) ≥ 2.

Επιπλέον, τα ίδια δύο συμπεράσματα ισχύουν στην περίπτωση όπου η i δεν παρουσιάζει σφάλμα στους πρώτους r γύρους, και δεν στείλει μήνυμα στην j στον γύρο r + 1, αλλά ακριβώς επειδή ο OptFloodSet δεν προσδιορίζει οτι οποιοδήποτε τέτοιο μήνυμα υποτίθεται οτι θα σταλεί..

Απόδειξη:

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

☐

Τώρα εκτελούμε τους OptFloodSet και FloodSet πλάι πλάι, με τις ίδιες εισόδους και ίδια πρότυπα σφαλμάτων. Δηλαδή, η ίδια διεργασία αποτυχαίνει στους ίδιους γύρους και στις δύο εκτελέσεις. Επιπλέον, εάν η διεργασία i αποστείλει μόνο κάποια απο τα μηνύματα της σε κάποιες διεργασίες στο γύρο r στον έναν αλγόριθμο, τότε θα αποστείλει τα μηνύματα της στις ίδιες διεργασίες στο γύρο r στον άλλον αλγόριθμο. Με μεγαλύτερη ακρίβεια, δεν υπάρχει j στην οποία η i στέλνει μήνυμα στον γύρο r στον πρώτο αλγόριθμο αλλά αποτυγχάνει να στείλει ένα μήνυμα που υποτίθεται οτι θα έστελνε στον άλλον αλγόριθμο. Δίνουμε αναλοίωτους ισχυρισμούς που σχετίζονται με τις καταστάσεις των δύο αλγορίθμων.

Λήμμα (OptFloodSet.3)

Ύστερα απο οποιοδήποτε αριθμό γύρων r, 0 ≤ r ≤ f + 1:

 1. OWi(r) είναι υποσύνολο του Wi(r).
     
 2.  Αν num(Wi(r)) = 1, τότε OWi(r) = Wi(r)..

Απόδειξη:

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

☐

Λήμμα (OptFloodSet.4)

Μετά απο οποιοδήποτε αριθμό γύρων r, 0 ≤ r ≤ f + 1:

Αν num(W_i (r)) ≥ 2, τότε num(OW_i (r)) ≥ 2..

Απόδειξη:

Με επαγωγή. Στο αρχικό βήμα, r = 0, προφανώς ισχύει. Έστω πως το λήμμα ισχύει για τον γύρο r. Θα αποδείξουμε πως ισχύει για r + 1. Υποθέτουμε ότι num(W_i (r + 1)) ≥ 2. Αν num(W_i (r)) ≥ 2, τότε απο επαγωγική υπόθεση έχουμε οτι num(OW_i (r)) ≥ 2, το οποίο συνεπάγεται num(OWi (r + 1)) ≥ 2, όπως απαιτείται.

Ας υποθέσουμε οτι num(W_i (r)) = 1. Τότε το λήμμα OptFloodSet 3 συνεπάγεται οτι OW_i (r) = W_i (r). Μελετάμε δύο υποπεριπτώσεις:

 1. num(Wj (r)) = 1 για κάθε j απο την οποία η i λαμβάνει μήνυμα στον γύρο r + 1 στον FloodSet.

Τότε για κάθε τέτοια j, έχουμε οτι OW_j (r) = W_j (r) απο το λήμμα 6.7, έτσι ώστε num(OW_j(r)) = 1. Το λήμμα 6.6 συνεπάγεται οτι για όλα αυτά τα j,ισχύει. Συνάγεται οτι OW_i(r + 1) = W_i(r + 1), το οποίο αρκεί για να αποδείξουμε το επαγωγικό βήμα.

 2. num(Wj (r)) ≥ 2 για κάποια j απο την οποία η i λαμβάνει μήνυμα στον γύρο r + 1 στον FloodSet.

Τότε απο την επαγωγική υπόθεση, num(OW_j (r)) ≥ 2. Έτσι το λήμμα OptFloodSet 2 συνεπάγεται οτι num(OW_i (r + 1)) ≥ 2, όπως απαιτείται.

Λήμμα (OptFloodSet.5)

Μετά απο οποιοδήποτε αριθμό απο γύρους r, 0 ≤ r ≤ f + 1, οι μεταβλητές των γύρων και της απόφασης έχουν τις ίδιες τιμές στον FloodSet και OptFloodSet..

Απόδειξη:

(Σκιαγράφηση απόδειξης) Το ενδιαφέρον σημείο προς απόδειξη είναι οτι η ίδια απόφαση πέρνεται απο οποιαδήποτε διεργασία I στον γύρο f + 1 στους δύο αλγόριθμους. Το οποίο συνεπάγεται απο τα λήμματα OptFloodSet 3 και 4 για r = f + 1 και απο τους κανόνες απόφασης των δύο αλγορίθμων.

☐

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

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

Απόδειξη:

Απο το λήμμα OptFloodSet 5 και το θεώρημα FloodSet 1(το θεώρημα ορθότητας για τον FloodSet).

☐

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

Κάθε κόμβος(διεργασία) δέχεται ως είσοδο μια αρχική τιμή v₀, ροζ κουτί. Το γαλάζιο κουτί αναπαριστά την λίστα W_i όπου αποθηκεύονται οι ληφθείσες τιμές της κάθε διεργασίας i και το κίτρινο κουτί δείχνει την τελική απόφαση της κάθε μιας.

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

Κατά τον πρώτο γύρο εκτέλεσης του αλγορίθμου συμβαίνει ένα σφάλμα επικοινωνίας στην διεργασία 3 καθώς αποστέλλει μήνυμα στην διεργασία 1. Σύμφωνα με τον αλγόριθμο κάθε άλλη διεργασία i, με i Є {1,2,4}, αποθηκεύει στην λίστα Wi τις τιμές που έλαβε.

Στον δεύτερο γύρο αφού όλες οι διεργασίες πλην της 3 έχουν ενημερωθεί με τουλάχιστον μια νέα τιμή, την στέλνουν σε όλες τις άλλες. Έστω πως η 1 διαλέγει να στείλει την τιμή {2,1}, η 2 στέλνει την {1,1} και η 4 στέλνει την {3,0}. Ακόμα συμβαίνει σφάλμα τερματισμού στην διεργασία 4, με τέτοιο τρόπο ώστε να αποτύχει να στείλει οποιοδήποτε μήνυμα.

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

Λαμβάνοντας υπόψιν τον κανόνα απόφασης των διεργασίων και τον αλγόριθμο OptFloodSet μπορούμε να παρατηρήσουμε πως ακόμα και αν στο γύρο 2 οι διεργασίες 1,2 και 4 διάλεγαν άλλες τιμές να στείλουν πάλι θα χρειάζονταν ο ίδιος αριθμός μηνυμάτων και συνολικών γύρων εκτελέσης για να συναινέσουν οι διεργασίες. Aυτό ισχύει αφού απο το τέλος του πρώτου γύρου αυτές οι διεργασίες έχουν παραπάνω απο 2 στοιχεία στις λίστες τους.