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

Από DistrSys

GlobSynch

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

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

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

-

Περιγράφουμε το υπόλοιπο σύστημα σαν έναν σφαιρικό συγχρονιστή (global synchronizer), GlobSynch. Σκοπός του είναι, σε κάθε γύρο, να συλλέγει όλα τα μηνύματα που στέλνονται από αυτόματα χρηστών σε εκείνο τον γύρο σε user-send ενέργειες και να τα παραδίδει σε όλα τα αυτόματα χρηστών σε user-receive ενέργειες. Συγχρονίζει δηλαδή σφαιρικά, μετά από όλα γεγονότα user-send και πριν από τα γεγονότα user-receive κάθε γύρου. Στην παρακάτω εικόνα φαίνεται ο συνδυασμός αυτομάτων χρήστη και GlobSynch, που αποτελούν μαζί το GloSynch σύστημα. Παρατηρείστε πως οι ενέργειες user-send είναι ενέργειες εισόδου του GlobSynch, ενώ οι ενέργειες user-receive είναι ενέργειες εξόδου.

GlobSynch

Το GlobSynch μπορεί εύκολα να περιγραφεί σαν ένα αυτόματο εισόδου/εξόδου:

GlobSynch αυτόματο:

Ενέργειες:

Εισόδου: user-send(T, r)i, T ένα σύνολο από tagged messages, r > 0, 1 ≤ i ≤ n 

Eξόδου: user-receive(T, r)i, T ένα σύνολο από tagged messages, r > 0, 1 ≤ i ≤ n 

Καταστάσεις: tray ένας πίνακας από {1,…,n} x N+ σύνολα από tagged messages, αρχικά όλα 0
             user-sent, user-rcvd, το καθένα ένας πίνακας από {1,…,n} x N+ μεταβλητές τύπου Boolean, αρχικά όλες 

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

   Αποτέλεσμα: User-sent(i, r) = true 
               for all j i do
                  tray(j, r) = tray(j, r) U {(m, i) | (m, j) Є T} 
               user-receive(T, r)i 

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

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

Εκτέλεση: For every i, r:
             user-receive(T, r)i, T ένα σύνολο από tagged messages

Στον παραπάνω κώδικα, το tray(i, r) είναι σχεδιασμένο να κρατάει στο Ui τα μηνύματα που του παραδίδονται από όλους του τους γείτονες. Αυτά τα μηνύματα περιέχουν στην ετικέτα τους την ταυτότητα του αποστολέα. Τα user-sent και user-rcvd στοιχεία απλώς ελέγχουν αν έχουν γίνει τα user-send και user-received γεγονότα.

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

Το πρόβλημα του συγχρονιστή είναι να υλοποιήσει το GlobSynch αυτόματο με έναν αλγόριθμο ασύγχρονου δικτύου, με μία διεργασία Pi σε κάθε κόμβο i του γραφήματος G και αξιόπιστα FIFO send/receive κανάλια Ci,j σε κάθε κατεύθυνση κάθε ακμής (i, j) του G. Αυτή η υλοποίηση θα πρέπει να διασφαλίζει ότι κανένα μεμονωμένο αυτόματο χρήστη Ui δεν θα μπορεί να καταλάβει την διαφορά ανάμεσα σε μια εκτέλεση στο σύστημα υλοποίησης (π.χ. αυτόματα χρήστη και κατανεμημένος αλγόριθμος) και σε μια εκτέλεση στο GlobSynch σύστημα. Θέλουμε δηλαδή να διασφαλίσουμε ότι αν a είναι μια δίκαιη εκτέλεση στο σύστημα υλοποίησης, τότε θα υπάρχει μια δίκαιη εκτέλεση a΄ του άλλου συστήματος τέτοια ώστε για κάθε i να μην μπορεί η Ui να ξεχωρίσει την a από την a΄.

Οι τρεις αλγόριθμοι συγχρονιστών που πρότεινε ο Awerbuch είναι:

• Alpha συγχρονιστής: Έχει χαμηλή χρονική πολυπλοκότητα αλλά υψηλή πολυπλοκότητα μηνυμάτων.
• Beta συγχρονιστής: Έχει υψηλή χρονική πολυπλοκότητα αλλά χαμηλή πολυπλοκότητα μηνυμάτων.
• Gamma συγχρονιστής: Κάτι ανάμεσα στους δύο προηγούμενους αλγορίθμους Alpha και Beta. Παρέχει σχετικά μικρή πολυπλοκότητα τόσο χρονική όσο και μηνυμάτων.