Σημειώσεις:Προβλήματα:Συγχρονισμός

Από DistrSys

Πίνακας περιεχομένων 1 Ασύγχρονα Κατανεμημένα Συστήματα 2 Εφαρμογές 2.1 Εκλογή Αρχηγού 2.2 Αναζήτηση Κατά Πλάτος 2.3 Συντομότερα Μονοπάτια 2.4 Διάδοση και Επιβεβαίωση (Broadcast and Acknowledgment)

Ασύγχρονα Κατανεμημένα Συστήματα

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

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

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

Διατυπώνουμε τον μετασχηματισμό από το σύγχρονο μοντέλο δικτύου στο ασύγχρονο μέσω μιας μονάδας που ονομάζεται συγχρονιστής. Στην συνέχεια περιγράφουμε διάφορες κατανεμημένες υλοποιήσεις του συγχρονιστή. Όλες αυτές οι υλοποιήσεις περιλαμβάνουν συγχρονισμό του συστήματος σε κάθε σύγχρονο γύρο. Αυτό είναι αναγκαίο καθώς οι μετατροπές είναι σχεδιασμένες για να λειτουργούν για αυθαίρετους σύγχρονους αλγορίθμους. Η ικανότητα για λιγότερο συχνό συγχρονισμό (όπως για παράδειγμα στον SimpleMST αλγόριθμο) εξαρτάται από ειδικές ιδιότητες του αλγορίθμου που εξασφαλίζουν ότι εξακολουθεί να λειτουργεί σωστά στην περίπτωση που επιτρέπεται η εμφάνιση αυθαίρετων επικαλύψεων των βημάτων των διεργασιών ανάμεσα στα σημεία συγχρονισμού.

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

Η ιδέα προτάθηκε για πρώτη φορά το 1985 από τον Awerbuch μαζί με τρεις αλγορίθμους συγχρονιστών, τους Alpha, Beta και Gamma που είχαν ο καθένας διαφορετικά tradeoffs σε χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Ουσιαστικά, είναι μια λύση στο πρόβλημα του ότι ασύγχρονοι αλγόριθμοι (που λειτουργούν σε δίκτυα χωρίς καθολικό ρολόι) είναι πιο δύσκολο να σχεδιαστούν και συχνά λιγότερο αποδοτικοί από τους αντίστοιχους σύγχρονους αλγορίθμους. Με την χρήση ενός συγχρονιστή, οι σχεδιαστές αλγορίθμων μπορούν να βασιστούν στο απλουστευμένο «ιδανικό δίκτυο» και να παράγουν αργότερα μηχανικά μια έκδοση που λειτουργεί σε πιο ρεαλιστικές ασύγχρονες συνθήκες. Παρά την επιβάρυνση που προσδίδει η χρήση συγχρονιστή, ο αλγόριθμος που προκύπτει μπορεί να είναι καλύτερος σε σύγκριση με αλγορίθμους που σχεδιάστηκαν κατευθείαν για το ασύγχρονο μοντέλο δικτύου.

Σε αυτό το σημείο περιγράφουμε το πρόβλημα που σκοπεύουμε να επιλύσουμε με την χρήση του συγχρονιστή. Ξεκινώντας από το σύγχρονο μοντέλο δικτύου θυμίζουμε ότι είναι ένα σύνολο από n σύγχρονες διεργασίες στους κόμβους ενός μη-κατευθυνόμενου γραφήματος G = (V, E), που επικοινωνούν μέσω μηνυμάτων που στέλνονται μέσω των ακμών-καναλιών. Στον ορισμό που δώσαμε για το μοντέλο αντιλαμβανόμαστε κάθε διεργασία i ως ένα πεπερασμένο αυτόματο με συναρτήσεις παραγωγής μηνυμάτων και συναρτήσεις μετάβασης. Εδώ, αποκλίνουμε από αυτήν την περιγραφή και θεωρούμε κάθε διεργασία ως «διεργασία χρήστη» (use process) που είναι ένα αυτόματο εισόδου/εξόδου (I/O automaton) Ui. (Αναφερόμαστε στις διεργασίες αυτές ως «διεργασίες χρήστη» καθώς είναι χρήστες του συστήματος του συγχρονιστή, που είναι εξάλλου και το κύριο τμήμα του συστήματος που εξετάζουμε).

Έστω Μ το σταθερό αλφάβητο μηνυμάτων που χρησιμοποιείται στο σύγχρονο σύστημα. Ορίζουμε ένα «μήνυμα ετικέτα» (tagged message) ως ένα ζευγάρι (m, i), όπου m Є Μ και 1 ≤ i ≤ n.

Ένα αυτόματο εισόδου/εξόδου Ui αποτελείται από τα εξής:

• Ενέργειες εξόδου της μορφής user-send(T, r)i, όπου T είναι σύνολο από tagged messages και r > 0, μέσω των οποίων στέλνει μηνύματα στους γείτονές του. Η ετικέτα (tag) στο μήνυμα ετικέτα δηλώνει τον προορισμό του μηνύματος και το r αναπαριστά τον αριθμό του γύρου. Σημειώνουμε ότι αν το Ui δεν έχει να στείλει μηνύματα στον γύρο r τότε εκτελεί μια ενέργεια user-send(0, r)i.
• Ενέργειες εισόδου της μορφής user-receive(T, r)i, όπου T είναι σύνολο από tagged messages και r > 0, μέσω των οποίων λαμβάνει μηνύματα από τους γείτονές του. Εδώ η ετικέτα δηλώνει την προέλευση του μηνύματος, ενώ το r αντιπροσωπεύει και πάλι τον αριθμό του γύρου.

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

Παράδειγμα user-send και user-receive ενεργειών:

Έστω n = 4. Τότε, user-send({(m1, 1), (m2, 2)}, 3)4 σημαίνει ότι στον γύρο 3, ο χρήστης U4 στέλνει το μήνυμα m1 στο χρήστη U1, το μήνυμα m2 στον χρήστη U2 και δεν στέλνει κανένα άλλο μήνυμα. Επίσης, user-receive({(m1, 1), (m2, 2)}, 3)4 σημαίνει ότι στον γύρο 3, ο χρήστης U4 λαμβάνει το μήνυμα m1 από τον χρήστη U1, το μήνυμα m2 από τον χρήστη U2 και δεν λαμβάνει κανένα άλλο μήνυμα.

Κάθε αυτόματο εισόδου/εξόδου πρέπει να ικανοποιεί δύο συνθήκες (conditions):

• Να είναι καλώς ορισμένο (well-formed) με την έννοια ότι οι ενέργειες user-sendi και user-receivei εναλλάσσονται, ξεκινώντας με μία user-sendi ενέργεια και με την έννοια ότι διαδοχικά ζεύγη ενεργειών λαμβάνουν χώρα σε διαδοχικούς γύρους. Έτσι, μια ακολουθία τέτοιων ενεργειών είναι μέρος μιας άπειρης ακολουθίας της μορφής: user-send(T1, 1)i, user-receive(T1', 1) i, user-send(T2, 2)i, user-receive(T2', 2) i, user-send(T3, 3)i, …
• Να έχει βιωσιμότητα (liveness). Δηλαδή, σε κάθε καλώς ορισμένη δίκαιη εκτέλεση, το Ui πρέπει τελικά να εκτελεί μια user-sendi ενέργεια για κάθε γύρο r για τον οποίο σε όλους τους προηγούμενους από αυτόν γύρους έχουν συμβεί user-receivei ενέργειες. Με απλά λόγια δηλαδή, ότι οι χρήστες συνεχίζουν μηνύματα όσο το σύστημα ανταποκρίνεται.

Περιγράφουμε το υπόλοιπο σύστημα σαν έναν σφαιρικό συγχρονιστή (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. Παρέχει σχετικά μικρή πολυπλοκότητα τόσο χρονική όσο και μηνυμάτων.

Εφαρμογές

Οι αλγόριθμοι συγχρονιστή επιτρέπουν σε ένα ασύγχρονο δίκτυο στο οποίο δεν συμβαίνουν σφάλματα να υλοποιεί οποιονδήποτε αλγόριθμο για σύγχρονο δίκτυο χωρίς ανοχή σε σφάλματα. Εδώ δίνουμε κάποια παραδείγματα ασύγχρονων αλγορίθμων κατασκευασμένων με την βοήθεια συγχρονιστών. Υπενθυμίζουμε ότι σε αυτήν την ενότητα εξετάζουμε μόνο μη κατευθυνόμενα δίκτυα. Τέλος θυμίζουμε την δυσκολία που θέτει στην μέτρηση της χρονικής πολυπλοκότητας η χρονική απροσδιοριστία. Για αυτόν τον λόγο έχουμε θέσει ένα άνω φράγμα l στον χρόνο εκτέλεσης κάθε ενέργειας ε σε κάποια κατάσταση k και ένα άνω φράγμα d στον χρόνο παράδοσης του παλαιότερου μηνύματος που βρίσκεται σε κάποιο κανάλι επικοινωνίας.

Εκλογή Αρχηγού

Χρησιμοποιώντας συγχρονιστές, σύγχρονοι αλγόριθμοι εκλογής αρχηγού για δίκτυα δακτυλίου όπως ο LCR και ο HS μπορούν να εκτελεστούν σε ασύγχρονα δίκτυα δακτυλίου. Ωστόσο αυτή η περίπτωση δεν παρουσιάζει ιδιαίτερο ενδιαφέρον καθώς αυτοί οι αλγόριθμοι ήδη λειτουργούν σε ασύγχρονα δίκτυα, χωρίς να εισαχθεί ο επιπλέον φόρτος που επιφέρει η χρήση συγχρονιστών.

Σε ένα ασύγχρονο δίκτυο βασισμένο σε ένα τυχαίο μη-κατευθυνόμενο γράφημα με γνωστή διάμετρο, diam, ο συγχρονιστής μπορεί να χρησιμοποιηθεί για να εκτελέσουμε τον FloodMax αλγόριθμο εκλογής αρχηγού για σύγχρονα δίκτυα. Χρησιμοποιώντας έναν ειδικό συγχρονιστή (τον συγχρονιστή Alpha), ο αλγόριθμος που προκύπτει στέλνει Ο(|Ε|diam) μηνύματα και χρειάζεται Ο(diam*d) χρόνο για να προσομοιώσει τους απαραίτητους diam γύρους της σύγχρονης εκτέλεσης.

Ο συγχρονιστής μπορεί επίσης να χρησιμοποιηθεί για την εκτέλεση του OptFloodMax αλγορίθμου εκλογής αρχηγού για σύγχρονα δίκτυα, ο οποίος μοιάζει με τον FloodMax εκτός του ότι οι κόμβοι στέλνουν μηνύματα μόνο στην περίπτωση που έχουν να στείλουν νέα πληροφορία. Αν και σε αυτήν την περίπτωση χρησιμοποιηθεί ο συγχρονιστής Alpha το πλεονέκτημα της βελτίωσης της απόδοσης χάνεται, καθώς ο ίδιος ο συγχρονιστής στέλνει μηνύματα σε όλα τα κανάλια σε όλους τους γύρους. Ωστόσο με την χρήση ενός άλλου συγχρονιστή, του συγχρονιστή Beta, η πολυπλοκότητα επικοινωνίας διατηρείται σε χαμηλά επίπεδα (με το κόστος επιπλέον χρόνου).

Αναζήτηση Κατά Πλάτος

Υπενθυμίζουμε ότι ο SynchBFS αλγόριθμος απαιτεί Ο(|Ε|) μηνύματα και Ο(diam) γύρους σε ένα δίκτυο με δίαμετρο diam (οι διεργασίες δεν είναι απαραίτητο να γνωρίζουν την διάμετρο). Χρησιμοποιώντας συγχρονιστές, ο αλγόριθμος SynchBFS μπορεί να εκτελεστεί σε ένα ασύγχρονο δίκτυο. Με χρήση του συγχρονιστή τύπου Alpha, ο αλγόριθμος που προκύπτει στέλνει O(|E|diam) μηνύματα και χρειάζεται O(diam*d) χρόνο σε γύρους για να εξομοιώσει τους diam γύρους που χρειάζονται ώστε όλες οι διεργασίες να δώσουν έξοδο για τους γονείς τους. Με τον συγχρονιστή τύπου Beta (χρησιμοποιώντας ένα δέντρο ύψους το πολύ diam) ο αλγόριθμος στέλνει μόλις O(|E| + n*diam) μηνύματα και χρειάζεται O(diam2*d) χρόνο. Υπάρχει η δυνατότητα βελτίωσης της χρονικής πολυπλοκότητας με χρήση του συγχρονιστή Gamma αλλά με το κόστος επιπλέον πολυπλοκότητας επικοινωνίας.

Εδώ υπάρχει ένα λεπτό σημείο: δεν είναι προφανές το πώς πρέπει να τερματίζουν οι αλγόριθμοι BFS που προκύπτουν με χρήση συγχρονιστών. Όπως περιγράψαμε, η υλοποίηση συνεχίζει να προσομοιώνει γύρους επ άπειρον και έτσι παράγει άπειρο αριθμό μηνυμάτων. (Αν οι διεργασίες ήξεραν την διάμετρο diam, θα μπορούσαν απλώς να σταματούν μετά την εξομοίωση diam γύρων, ωστόσο υποθέσαμε ότι οι διεργασίες δεν γνωρίζουν την διάμετρο.) Μια ad hoc [1] λύση σε αυτό το πρόβλημα είναι να κάνουμε κάθε αυτόματο χρήστη που διαπιστώνει τον γονέα του να εκτελείται μόνο για ακόμη έναν γύρο ενημερώνοντας τους γείτονές του και στην συνέχεια να σταματάει.

Συντομότερα Μονοπάτια

Για το πρόβλημα της εύρεσης συντομότερου μονοπατιού από ένα συγκεκριμένο σημείο η χρήση συγχρονιστών επιφέρει μεγάλες βελτιώσεις. Υπενθυμίζουμε ότι ο AsynchBellmanFord αλγόριθμος έχει χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων που είναι εκθετική στον αριθμό των κόμβων. Ωστόσο ο σύγχρονος BellmanFord αλγόριθμος έχει πολυπλοκότητα μηνυμάτων μόνο O(n|E|) και χρονική πολυπλοκότητα μόνο O(n), για ένα δίκτυο με γνωστό μέγεθος n. Μπορούμε να εκτελέσουμε τον σύγχρονο BellmanFord αλγόριθμο χρησιμοποιώντας, για παράδειγμα, τον συγχρονιστή Alpha και να πάρουμε έναν αλγόριθμο που στέλνει O(n|E|) μηνύματα και απαιτεί O(n*d) χρόνο να εξομοιώσει τους απαιτούμενους n γύρους. Ο συγχρονιστής SimpleSynch θα λειτουργούσε εξίσου καλά.

Διάδοση και Επιβεβαίωση (Broadcast and Acknowledgment)

Είναι δυνατόν να σχεδιάσουμε έναν σύγχρονο αλγόριθμο, που επιτρέπει σε μια διεργασία να διαδώσει ένα μήνυμα σε όλες τις υπόλοιπες διεργασίες και να λάβει από αυτές μια επιβεβαίωση, και που να στέλνει Ο(|Ε|) μηνύματα και χρειάζεται O(diam) γύρους. Μπορούμε να εκτελέσουμε αυτόν τον αλγόριθμο χρησιμοποιώντας τον συγχρονιστή Alpha και να πάρουμε έτσι έναν ασύγχρονο αλγόριθμο για διάδοση και επιβεβαίωση που χρησιμοποιεί O(|E|diam) μηνύματα και O(diam*d) χρόνο.

Οι συγχρονιστές μπορούν επίσης να χρησιμοποιηθούν και για προβλήματα όπως το Maximal Independent Set. [2]