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

Από DistrSys

ThreePhaseCommit

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

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

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

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

Μία αναβάθμιση του αλγορίθμου TwoPhaseCommit αποτελεί ο αλγόριθμος επικύρωσης three-phase commit (3PC - “επικύρωση σε 3 φάσεις”) που εγγυάται ισχυρή συνθήκη τερματισμού. Πάλι αρχικά χρησιμοποιείται μία διεργασία-συντονιστής για να επικυρωθούν οι αποφάσεις των διεργασιών και επακολούθως αναδρομικά επιλέγεται επόμενη διεργασία-συντονιστής. Ο 3PC είναι επίσης ένας non-blocking αλγόριθμος, δηλαδή δεν υπάρχει περίπτωση για τις συμμετέχουσες διεργασίες να περιμένουν για αόριστο χρονικό διάστημα απάντηση από την διεργασία-συντονιστή.

Εκτέλεση των 3 πρώτων γύρων ThreephaseCommit χωρίς σφάλματα τερματισμού.

Έστω προ-επιλεγμένη διεργασία u₁ που θα παίξει τον ρόλο του αρχικού “συντονιστή” και δυνατότητες απόφασης για τις διεργασίες {“ΝΑΙ”,“ΟΧΙ”} καθώς και καταστάσεις κ₀ (αποφάσισε “ΟΧΙ”), κ₁ (αποφάσισε “ΝΑΙ”), “έτοιμη”, “άγνωστη”. Η ουσιαστική διαφορά του 3PC από τον 2PC για τους αρχικούς τρείς πρώτους γύρους του είναι ότι για να αποφασίσει η u₁ “ΝΑΙ” πρέπει πρώτα να εγγυηθούμε ότι όλες οι άλλες διεργασίες είναι έτοιμες να αποφασίσουν πριν αποσταλεί το μήνυμα απόφασης. Αυτό στοιχίζει επιπλέον ένα γύρο. Οι γύροι που ακολουθούν εκφράζουν το πρωτόκολλο τερματισμού και εγγυώνται τον ισχυρό τερματισμό του αλγορίθμου με εναλλαγές διεργασιών-συντονιστών.

• 1ος γύρος:

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

• 2ος γύρος:

Αν η διεργασία u₁ στον πρώτο γύρο είχε αποφασίσει o₁ = “ΟΧΙ” στέλνει στις υπόλοιπες διεργασίες το μήνυμα “άκυρη”, διαφορετικά στέλνει το μήνυμα “έτοιμη”. Όποια διεργασία λάβει το μήνυμα “άκυρη” από την u₁ αποφασίζει o_u = “ΟΧΙ”. Όποια διεργασία λάβει μήνυμα “έτοιμη” μεταβαίνει σε κατάσταση “έτοιμη”. Η u₁ αν μέχρι στιγμής δεν έχει αποφασίσει, αποφασίζει o₁ = “ΝΑΙ”.

• 3ος γύρος:

Αν η διεργασία u₁ αποφάσισε o₁ = “ΝΑΙ”, στέλνει σε όλες τις άλλες διεργασίες αυτή την απόφαση. Όποιες διεργασίες λάβουν το μήνυμα αποφασίζουν o_u = “ΝΑΙ”.

• 4ος γύρος:

Όλες οι διεργασίες που δεν έχουν παρουσιάσει σφάλμα (ενεργές διεργασίες) στέλνουν την κατάστασή τους (κ₀, κ₁, “έτοιμη”, “άγνωστη”) στην διεργασία u₂, η οποία τις τοποθετεί σε μία συλλογή συμπεριλαμβάνοντας και την δική της κατάσταση.

α) Αν εμπεριέχεται έστω μία τιμή κ₀ και η u₂ δεν έχει ακόμη αποφασίσει, τότε αποφασίζει “ΟΧΙ” (μετάβαση σε κ₀).

β) Αν εμπεριέχεται τιμή κ₁ και η u₂ δεν έχει ακόμη αποφασίσει, τότε αποφασίζει “ΝΑΙ” (μετάβαση σε κ₁).

γ) Αν όλες οι τιμές είναι “άγνωστη” τότε η u₂ αποφασίζει “ΟΧΙ” (μετάβαση σε κ₀).

δ) Αν όλες οι τιμές είναι “άγνωστη” ή “ετοιμη”, αλλά περιέχεται τουλάχιστον μία τιμή “έτοιμη”, τότε μεταβαίνει σε κατάσταση “έτοιμη” αλλά δεν αποφασίζει.

• 5ος γύρος:

Όμοια με την u₁ στους γύρους 2,3, αν η διεργασία u₂ αποφάσισε o₂ = “ΟΧΙ” στέλνει σε όλες τις υπόλοιπες ένα μήνυμα “άκυρη”, ενώ αν o₂ = “ΝΑΙ”, στέλνει μήνυμα “έγκυρη”. Αν δεν έχει αποφασίσει στέλνει μήνυμα “έτοιμη”. Όποια διεργασία λάβει το μήνυμα “έγκυρη” ή “άκυρη” και δεν έχει ακόμη αποφασίσει, αποφασίζει “ΝΑΙ” ή “ΟΧΙ” αντίστοιχα. Αν η διεργασία u₂ δεν έχει ακόμη αποφασίσει, αποφασίζει o₂ = “ΝΑΙ”.

• 6ος γύρος:

Αν η διεργασία u₂ αποφάσισε o₂ = “NAI” στέλνει σε όλες τις υπόλοιπες μήνυμα “έγκυρη”. Όποια διεργασία λάβει το μήνυμα αυτό και δεν έχει αποφασίσει ακόμη, αποφασίζει o_u = “ΝΑΙ”.

Ακολούθως, μετά τον 6ο γύρο το πρωτόκολλο συνεχίζει με τρείς ακόμη όμοιους γύρους [4-6] συντονισμού για κάθε διεργασία u_j, j ∊ [3,n].

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

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

Μετά από τους τρείς πρώτους γύρους οι καταστάσεις στις οποίες μπορούν να βρίσκονται οι διεργασίες (είτε αν παρουσίασαν σφάλματα είτε όχι) είναι οι εξής:

1. κ₀ – έχει αποφασίσει o_u = “ΟΧΙ”
2. κ₁ – έχει αποφασίσει o_u = “ΝΑΙ”
3. ”ετοιμη” - δεν έχει αποφασίσει, αλλά είναι έτοιμη.
4. ”άγνωστη” - δεν έχει αποφασίσει και δεν είναι έτοιμη.

Κάθε διεργασία μπορεί να βρίσκεται μόνον σε μία κατάσταση σε κάθε χρονική στιγμή. Υπάρχουν όμως επίσης και συνδυασμοί των παραπάνω καταστάσεων που δεν είναι δυνατοί. Αυτοί επεξηγούνται στο παρακάτω λήμμα.

Λήμμα (ThreePhaseCommit.1)

1. Αν κάποια διεργασία βρίσκεται στην κατάσταση “έτοιμη” ή κ₁, τότε οι αρχικές τιμές όλων των διεργασιών ήταν “ΝΑΙ”.
2. Αν κάποια διεργασία βρίσκεται στην κατάσταση κ₀, τότε καμία διεργασία δεν είναι σε κατάσταση κ₁ και καμία ενεργή διεργασία δεν είναι σε κατάσταση “έτοιμη”.
3. Αν κάποια διεργασία βρίσκεται στην κατάσταση κ₁, τότε καμία διεργασία δεν είναι σε κατάσταση κ₀ και καμία ενεργή διεργασία δεν είναι σε κατάσταση “άγνωστη”..

Απόδειξη:

Τα 1 και 2 συνεπάγονται άμεσα από τον ορισμό του μοντέλου και τις μεταβάσεις που ορίζονται στον αλγόριθμο.
Για το 3 παρατηρούμε ότι η διεργασία u₁ μπορεί να αποφασίσει “ΝΑΙ” στο τέλος του 2ου γύρου, αφότου στείλει τα μηνύματα “έτοιμη” στις υπόλοιπες διεργασίες. Αυτό σημαίνει ότι η u₁ γνωρίζει στο τέλος του 2ου γύρου ότι κάθε μία από τις υπόλοιπες διεργασίες είτε έχουν λάβει σωστά το μήνυμα και έχουν μεταβεί σε κατάσταση “έτοιμη” είτε έχουν παρουσιάσει σφάλμα. Επομένως ο συγχρονισμός παίζει σημαντικό ρόλο εδώ.

☐

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

Λήμμα (ThreePhaseCommit.2)

1. Τηρείται η συνθήκη συμφωνίας.
2. Τηρείται η συνθήκη εγκυρότητας.
3. Αν η διεργασία-συντονιστής u₁ δεν έχει παρουσιάσει σφάλμα, τότε όλες οι ενεργές διεργασίες έχουν αποφασίσει..

Απόδειξη:

Το 1 προκύπτει από το Λήμμα ThreePhaseCommit.1.
Το 2 προκύπτει μερικώς από το Λήμμα ThreePhaseCommit.1 και συμπεριλαμβάνοντας το αντίστροφο της πρότασης (1) του ίδιου Λήμματος. Δηλαδή, αν όλες οι διεργασίες έχουν αρχική τιμή “ΝΑΙ”, τότε με την απουσία σφαλμάτων οι μοναδικές καταστάσεις στις οποίες μπορούν να βρίσκονται οι διεργασίες είναι στην κ₁ ή “ετοιμη”. Οι διεργασίες που βρίσκονται σε κατάσταση “έτοιμη” θα λάβουν ακολούθως μήνυμα από την διεργασία-συντονιστή και θα μεταβούν στην κατάσταση κ₁.
Το 3 ισχύει δεδομένου ότι η διεργασία u₁ δεν παρουσιάζει σφάλματα. Τότε όλες οι ενεργές διεργασίες τελικά αποφασίζουν, καθώς μετά τον 2ο γύρο αφενός η απόφαση της διεργασίας u₁ δεν μπορεί να επηρεαστεί πλέον από τις άλλες διεργασίες, αφετέρου αποστέλλεται άμεσα σε αυτές που αποφασίζουν κι αυτές με την σειρά τους παρομοίως.

☐

Αναφορικά, με τους τρείς μόνο πρώτους γύρους δεν θα ήταν δυνατή η ύπαρξη του ισχυρού τερματισμού. Αν παρουσιαζόταν σφάλμα στην διεργασία u₁ θα ήταν δυνατό όπως και στον αλγόριθμο 2PC να μείνουν οι υπόλοιπες διεργασίες σε μία αναποφάσιστη κατάσταση. Γι' αυτόν τον λόγο εφαρμόζεται το πρωτόκολλο τερματισμού που ακολουθεί στους γύρους 4 και μετά που μας εγγυάται την ορθότητα και καθιστά τον αλγόριθμο non-blocking.

Χρονική Πολυπλοκότητα [Ο(n)]: Στην παρούσα έκδοσή του ο 3PC απαιτεί 3n αριθμό γύρων. 3 αρχικοί γύροι με διεργασία-συντονιστή την προ-επιλεγμένη u1 και μετά οι γύροι 4-6 επαναλαμβάνονται για κάθε μία από τις υπόλοιπες n-1 διεργασίες. Άρα 3 + 3(n-1) = 3n.

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

Τερματισμός

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

Συμφωνία: Προκύπτει από το Λήμμα (ThreePhaseCommit.2).

Εγκυρότητα: Προκύπτει από το Λήμμα (ThreePhaseCommit.2).

Τερματισμός: Με επαγωγή στον αριθμό των γύρων εκτέλεσης του αλγορίθμου και κάνοντας χρήση των Λημμάτων ThreePhaseCommit.1, ThreePhaseCommit.2 σε κάθε γύρο, αποδεικνύεται ότι οι διεργασίες τερματίζουν με ισχυρό τερματισμό. Αν όλες οι διεργασίες παρουσιάσουν σφάλμα, τότε προφανώς καμία διεργασία δεν αποφασίζει. Επίσης, έστω ότι η διεργασία u_i είναι μία ενεργή διεργασία. Τότε, κατά τους γύρους που θα οριστεί η u_i ως διεργασία-συντονιστής κάθε ενεργή διεργασία αποφασίζει.