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

Από DistrSys

TwoPhaseCommit

Πρόβλημα: Επικύρωση Δίκτυο: Δέντρο ύψους 1 (ρίζα u1, παιδιά οι υπόλοιπες διεργασίες), Πλήρες Κλάση: Συγκεντρωτικός

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

Χρονική: O(1) Επικοινωνίας: O(n)

Στη σύνταξη του κειμένου συνεισέφερε ο Δημήτρης Ζερβάκης

Ο πιο απλός και ευρύτερα διαδεδομένος αλγόριθμος επικύρωσης είναι ο two-phase commit (2PC - “επικύρωση σε 2 φάσεις”). Όλες οι διεργασίες που παίρνουν μέρος σε αυτόν είτε αποφασίζουν σε κοινή δέσμευση είτε σε κοινή ακύρωση του πρωτοκόλλου. Ο αλγόριθμος 2PC στηρίζεται στην ύπαρξη μίας διεργασίας-συντονιστή και εγγυάται χαλαρή συνθήκη τερματισμού μόνο.

Έστω προ-επιλεγμένη διεργασία u₁ που θα παίξει τον ρόλο του “συντονιστή” και δυνατότητες απόφασης για τις διεργασίες {“ΝΑΙ”,“ΟΧΙ”}.

• 1ος γύρος:

Όλες οι διεργασίες u_j (j ∊ (1,n]) εκτός της u₁ στέλνουν τις αρχικές τιμές τους i_u στην u₁. Αν κάποιες έχουν τιμή “ΟΧΙ”, αποφασίζουν “ΟΧΙ”. Αφού συλλέξει όλες αυτές τις τιμές, η διεργασία u₁ συνυπολογίζει και την δική της αρχική τιμή i₁ και αν όλες μαζί συμφωνούν σε τιμή “ΝΑΙ” τότε αποφασίζει o₁ = “ΝΑΙ”. Διαφορετικά αποφασίζει o₁ = “ΟΧΙ”.

• 2ος γύρος:

Η διεργασία u₁ αποστέλλει την απόφασή της σε όλες τις άλλες διεργασίες. Όποιες από αυτές λάβουν το μήνυμα και δεν είχαν ήδη αποφασίσει από τον 1ο γύρο, αποφασίζουν την ληφθήσα τιμή o₁.

Σε μία πιο αυστηρή διατύπωση του πρωτοκόλλου η διεργασία u₁ αρχικά στέλνει ένα αίτημα ψηφοφορίας στις διεργασίες περιμένοντας απάντηση δέσμευσης ή ακύρωσης και μετά ακολουθεί ο 1ος γύρος. Επίσης, διεργασίες που αποφασίζουν “ΟΧΙ” κατά τον 1ο γύρο τερματίζουν, ενώ οι άλλες αναμένουν την εντολή o₁ από την u₁.

Εκτέλεση του TwoPhaseCommit χωρίς σφάλματα τερματισμού

Τερματισμός

Ο αλγόριθμος 2PC λύνει το πρόβλημα της επικύρωσης υπό την χαλαρή συνθήκη τερματισμού.

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

Εγκυρότητα: Πάλι εξαιτίας της ύπαρξης της διεργασίας-συντονιστή εγγυούμαστε την εγκυρότητα. Αν υπάρξει έστω μία διεργασία που αρχικά έχει τιμή “ΟΧΙ”, η u₁ θα το αναγνωρίσει αυτό και θα ορίσει και τις υπόλοιπες με την απόφασή της o₁ = “ΟΧΙ”. Αν αντίθετα όλες οι διεργασίες έχουν αποφασίσει σε τιμή “ΝΑΙ”, συμπεριλαμβανομένης της u₁ και δεν υπάρξουν σφάλματα, όλες τελικά οι διεργασίες θα αποφασίσουν στην τιμή o₁ = “ΝΑΙ”.

Τερματισμός: Ο 2PC τερματίζει υπό την χαλαρή συνθήκη τερματισμού μόνο, εξαιτίας του ότι είναι ένας blocking αλγόριθμος, δηλαδή υπάρχουν βήματα όπου διεργασίες βρίσκονται σε κατάσταση αναμονής.

Αν υπάρξει σφάλμα στην u₁ προτού αποστείλει την απόφασή της στον 2ο γύρο, τότε καμία διεργασία που είχε αρχική τιμή “ΝΑΙ” δεν θα αποφασίσει καθώς θα περιμένει επικύρωση ή αλλαγή βάσει της o₁ που δεν θα έρθει ποτέ. Γι' αυτόν τον λόγο, σε πρακτικές εφαρμογές του πρωτοκόλλου 2PC χρησιμοποιούνται τερματικές διαδικασίες, όπως για παράδειγμα timeout διεργασίες, πρωτόκολλα αποκατάστασης, ή και ενημερώσεις μεταξύ των διεργασίων από αυτές που είχαν αποφασίσει “ΟΧΙ” από τον πρώτο γύρο. Σε μία ακραία περίπτωση θα μπορούσαν όλες οι διεργασίες να έχουν αρχική τιμή “ΝΑΙ” εκτός της u₁ και επακολούθως η u₁ να παρουσιάσει σφάλμα προτού στείλει οποιοδήποτε μήνυμα. Έτσι, καμία από τις άλλες διεργασίες δεν μαθαίνει ποτέ την τιμή της u₁ κι επομένως, λόγω συνθήκης εγγυρότητας, καμία δεν μπορεί να κλειδώσει στην τιμή “ΝΑΙ”. Από την άλλη, καμία διεργασία δεν μπορεί να αποφασίσει “ΟΧΙ” καθώς καμία δεν γνωρίζει αν η διεργασία u₁ είχε αποφασίσει “ΝΑΙ” προτού παρουσιάσει σφάλμα κι επομένως έτσι θα παραβίαζαν την συνθήκη συμφωνίας. Αυτά τα μειονεκτήματα του αλγορίθμου εξαλείφονται με τον αλγόριθμο ThreePhaseCommit που εγγυάται την ισχυρή συνθήκη τερματισμου.

Ανάλυση Απόδοσης

Χρονική Πολυπλοκότητα [O(1)]: Με τον τρόπο που περιγράψαμε τον αλγόριθμο και χωρίς την παρουσία σφαλμάτων ο αλγόριθμος 2PC απαιτεί μόνον δύο γύρους. Αυτό τηρεί και την συμφωνία τερματισμού για το κάτω όριο των f+1 γύρων, καθώς ο 2PC ικανοποιεί μόνον την χαλαρή συνθήκη τερματισμού.

Πολυπλοκότητα Επικοινωνίας [O(n)]: Στην χειρότερη περίπτωση που τυγχάνει να είναι και εκείνη όπου δεν παρουσιάζεται κανένα σφάλμα, στον αλγόριθμο 2PC ανταλλάσονται 2n-2 μηνύματα. Στον πρώτο γύρο n-1 διεργασίες στέλνουν 1 μήνυμα στην u1 και στον δεύτερο γύρο η u₁ στέλνει 1 μήνυμα σε n-1 διεργασίες.

Προφανώς και οι δύο πολυπλοκότητες αυξάνονται αν επιτρέψουμε επιπλέον προσαρμογές πάνω στο πρωτόκολλο.