Σημειώσεις:Προβλήματα:Επικύρωση

Από DistrSys

Πίνακας περιεχομένων 1 Το πρόβλημα της Επικύρωσης Δοσοληψιών 2 Συνθήκες Ορθότητας 2.1 Παρατηρήσεις 2.2 Συγκρίσεις με άλλα προβλήματα 3 Εξωτερικοί Σύνδεσμοι

Το πρόβλημα της Επικύρωσης Δοσοληψιών

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

Αλγόριθμοι Επικύρωσης:

• TwoPhaseCommit
  
• ThreePhaseCommit

Συνθήκες Ορθότητας

Έστω ότι οι πιθανές τιμές εισόδου/εξόδου των διεργασιών είναι “ΝΑΙ” και “ΟΧΙ” αντίστοιχα για επικύρωση και ακύρωση. Δηλαδή το σύνολο των τιμών τους ορίζεται ως S = {“ΝΑΙ, “ΟΧΙ”}. Θεωρούμε ότι το πρόβλημα της επικύρωσης λύνεται αν τηρούνται οι παρακάτω συνθήκες:

Συμφωνία:

Κανένα ζεύγος διεργασιών δεν αποφασίζει σε διαφορετικές τιμές εξόδου. Δηλ. ∄u,v : o_u ≠ o_v.

Εγκυρότητα:

1. Αν υπάρχει μια διεργασία u με αρχική τιμή i_u = “OXI” τότε η μοναδική πιθανή απόφαση είναι “ΟΧΙ”.
2. Αν ∀u: i_u = “ΝΑΙ” και δεν παρουσιαστούν σφάλματα, τότε η μοναδική πιθανή απόφαση είναι “ΝΑΙ”.

Τερματισμός:

1. χαλαρός – εάν δεν παρουσιαστούν σφάλματα, τότε όλες οι διεργασίες αποφασίζουν τελικά (blocking αλγόριθμοι, πχ TwoPhaseCommit).
2. ισχυρός – όλες οι διεργασίες που δεν παρουσίασαν σφάλμα (ενεργές διεργασίες) αποφασίζουν τελικά (non-blocking αλγόριθμοι, πχ ThreePhaseCommit).

Παρατηρήσεις

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

Συγκρίσεις με άλλα προβλήματα

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

• Διαφορές με συντονισμένη επίθεση: Στην επικύρωση θεωρούμε μόνο σφάλματα τερματισμού και όχι σφάλματα επικοινωνίας. Επίσης, στο σημείο (1) της εγκυρότητας ορίζεται αυστηρά ότι η αρχική τιμή μίας διεργασίας μπορεί να επηρεάσει το τελικό αποτέλεσμα. Αντιθέτως, στην συντονισμένη επίθεση, ζητείται μόνον αν όλες οι διεργασίες ξεκινήσουν με τιμή “ΟΧΙ” να καταλήγουμε σε τιμή “ΟΧΙ”.
• Διαφορές με συναίνεση: Η συνθήκη εγκυρότητας είναι αυστηρά ορισμένη στην επικύρωση, με σύνολο δυνατών τιμών S. Επίσης, υπάρχει η έννοια του χαλαρού τερματισμού. Στην συναίνεση αντιθέτως υποδηλώνεται ένα κάτω όριο n-1 γύρων που απαιτούνται για την επίλυση του προβλήματος με τον ισχυρό τερματισμό.

Εξωτερικοί Σύνδεσμοι

Wikipedia: Atomic commit , Commit (data management)