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

Από DistrSys

LocSynch

Πρόβλημα: Συγχρονισμός Δίκτυο: Γενικό Κλάση: -

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

Χρονική: - Επικοινωνίας: -

-

Όλες οι υλοποιήσεις του συγχρονιστή που περιγράφουμε είναι «τοπικές» με την έννοια ότι περιλαμβάνουν μόνο συγχρονισμό ανάμεσα σε γειτονικούς κόμβους στο δίκτυο και όχι σε οποιουσδήποτε κόμβους. Το πλεονέκτημα της χρήσης μόνο τοπικού συγχρονισμού είναι η δυνατότητα για εξοικονόμηση σε χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Σε αυτό το σημείο περιγράφουμε μια τοπική έκδοση του GlobSynch που την καλούμε LocSynch. Οι αλγόριθμοι θα παρουσιαστούν σαν υλοποιήσεις του LocSynch.

Ο LocSynch είναι σχεδόν ίδιος με τον GlobSynch. Η μόνη διαφορά είναι στις user-receive μεταβάσεις, οι οποίες εδώ περιγράφονται από:

LocSynch αυτόματο:

Μεταβάσεις: user-receive(T, r)i

Προϋπόθεση: for all j Є nbrs U {i}
            user-sent(j, r) = true 
            user-rcvd(i, r) = false 
            T = tray(i, r) 

Αποτέλεσμα: User-rcvd(i, r) = true 

Έτσι, στο LocSynch, r (γύρος) μηνύματα μπορούν να σταλούν στο Ui όταν r μηνύματα θα έχουν παραληφθεί από όλους τους γείτονές του και το ίδιο το Ui. Δεν είναι, δηλαδή, απαραίτητο να περιμένουμε για μηνύματα από όλους τους χρήστες του δικτύου.

Λήμμα (LocSynch.1)

Αν α είναι μια δίκαιη εκτέλεση του LocSynch συστήματος (πχ, χρήστες και LocSynch), τότε υπάρχει μια δίκαιη εκτέλεση α΄ του GlobSynch συστήματος την οποία κανένα Ui δεν μπορεί να ξεχωρίσει από την α.

Απόδειξη:

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

☐

• Αποδεικτική Ιδέα:

Έστω L και G τα LocSynch και GlobSynch συστήματα αντίστοιχα, ελαφρώς τροποποιημένα κατηγοριοποιώντας όλες τις εσωτερικές ενέργειες των αυτομάτων χρήστη σαν εξόδους. (Έτσι όλες οι εξωτερικές ενέργειες κάθε συστήματος είναι ακριβώς όλες οι ενέργειες των αυτομάτων χρήστη.) Ορισμένα γεγονότα του L «εξαρτώνται» από άλλα γεγονότα: ένα user-receive γεγονός εξαρτάται από user-send γεγονότα για τον ίδιο γύρο στο ίδιο ή σε γειτονικούς κόμβους και κάθε γεγονός σε ένα αυτόματο χρήστη μπορεί να εξαρτάται από ένα οποιοδήποτε προηγούμενο γεγονός στο ίδιο αυτόματο. Αν β είναι ένα οποιοδήποτε ίχνος του L, ορίζουμε μια μη ανακλαστική μερική σχέση →β στα γεγονότα του β ως εξής. Αν π και φ είναι δύο γεγονότα στο β, με το π να προηγείται του φ, τότε λέμε π →β φ, ή το π εξαρτάται από το φ αν μία από τις ακόλουθες συνθήκες ισχύει:

1. Τα π και φ είναι γεγονότα του ίδιου χρήστη Ui.
2. π = user-sent(T, r) i και φ = user-reveive(T΄, r)j όπου j Є nbrsi.
3. Τα π και φ σχετίζονται μέσω μιας ακολουθίας από σχέσεις των τύπων 1 και 2.

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

Θυμίζουμε εδώ, όσον αφορά το ίχνος, ότι μερικές φορές ενδιαφερόμαστε να παρατηρήσουμε μόνο την εξωτερική συμπεριφορά ενός αυτομάτου εισόδου/εξόδου. Έτσι, το ίχνος μια εκτέλεσης α ενός αυτομάτου εισόδου/εξόδου Α (trace(α)) είναι η υποακολουθία του α που αποτελείται από όλες τις εξωτερικές ενέργειες. Λέμε επίσης ότι το β είναι ένα ίχνος του Α αν το β είναι ίχνος μιας εκτέλεσης του Α. Συμβολίζουμε επίσης το σύνολο των ιχνών του Α ως traces(Α).

Επίσης, όσον αφορά την δικαιοσύνη υπενθυμίζουμε ότι στα κατανεμημένα συστήματα συνήθως μας ενδιαφέρουν εκείνες οι εκτελέσεις του συστήματος στις οποίες όλα τα στοιχεία έχουν δίκαιο αριθμό γύρων για να εκτελούν βήματα. Έτσι ορίζουμε την έννοια της δικαιοσύνης για τα αυτόματα εισόδου/εξόδου ώστε κάθε εργασία να έχει στην διάθεσή της άπειρο αριθμό ευκαιριών να εκτελέσει μια ενέργειά της. Λέμε ότι β είναι ένα δίκαιο ίχνος του Α αν το β είναι το ίχνος μια δίκαιας εκτέλεσης του Α και συμβολίζουμε το σύνολο των δίκαιων ιχνών του Α ως fairtraces(A).

Ισχυρισμός 1: Αν β είναι ένα δίκαιο ίχνος του L και γ είναι μια ακολουθία που προκύπτει από την αναδιάταξη των γεγονότων στο β ενώ διατηρείται η →β διάταξη, τότε το γ είναι επίσης ένα δίκαιο ίχνος του L.

Δεδομένου του παραπάνω ισχυρισμού, για να αποδείξουμε το λήμμα, ξεκινάμε από μια οποιαδήποτε δίκαιη εκτέλεση α του L και έστω β = trace(α). Αναδιατάσσουμε τα γεγονότα του β ώστε να πάρουμε ένα νέο ίχνος γ στο οποίο οι γύροι «διατάσσονται» συνολικά. Αυτό το κάνουμε τοποθετώντας όλα τα user-send γεγονότα για έναν συγκεκριμένο γύρο r πριν από όλα τα user-receive γεγονότα για τον ίδιο γύρο r. Η νέα απαίτηση διάταξης είναι συνεπής με τις απαιτήσεις εξάρτησης στην →β, εφόσον ποτέ δεν προϋποθέτουν την ανάποδη διάταξη, ακόμα και όταν εφαρμόζονται αντίθετα. Από τον ισχυρισμό, το γ είναι επίσης ένα δίκαιο ίχνος του L. Ωστόσο, επιπλέον, εφόσον όλα τα user-send γεγονότα για κάθε γύρο r προηγούνται όλων των user-receive γεγονότων για τον ίδιο γύρο, δεν είναι δύσκολο να δείξουμε ότι το γ είναι ίχνος του G. Για να ολοκληρώσουμε την απόδειξη, συμπληρώνουμε τις καταστάσεις στο γ για να πάρουμε μια εκτέλεση του G, συμπληρώνουμε τις καταστάσεις χρήστη όπως στο α. Τυπικά, αυτή η συμπλήρωση μπορεί να γίνει χρησιμοποιώντας γενικά θεωρήματα για την σύνθεση αυτομάτων εισόδου/εξόδου.

Ένα απλό παράδειγμα κατανεμημένου αλγορίθμου που υλοποιεί το LocSynch είναι το ακόλουθο.

• Αλγόριθμος SimpleSynch