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

Από DistrSys

ABD

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

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

Χρονική: O(D)+O(2d*σύγχρονοι γύροι εκτέλεσης) Επικοινωνίας: O(2E)+Ο(σύγχρονου αλγόριθμου)

Στη σύνταξη του κειμένου συνεισέφερε ο Αμαξηλάτης Δημήτριος και ο Μάριος Λογαράς

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

1. Η εκτέλεση ενός γεγονότος σε μια διεργασία χρειάζεται μηδενικό χρόνο
2. Κάθε διεργασία έχει ένα ρολόι για να μετρήσει τον φυσικό χρόνο. Εάν CLOCK_p(t) δείχνει τον χρόνο του ρολογιού της διεργασίας p την χρονική στιγμή t και αν η p δεν αναθέτει μια τιμή στο ρολόι του ανάμεσα στις στιγμές t1 και t2 τότε CLOCK_p(t₁) - CLOCK_p(t₂) = t₂ - t₁
3. Ο φυσικός χρόνος ανάμεσα στην αποστολή ενός μηνύματος και στην παραλαβή του είναι φραγμένη από το d.

Ο συγχρονιστής των Tel και Leewuen βασίζεται στις εξής παραδοχές: Πρώτον, υποθέτει ότι υπάρχει ένα άνω φράγμα l στον χρόνο εκτέλεσης της κάθε ενέργειας ε σε κάποια κατάσταση κ και δεύτερον ότι υπάρχει ένα άνω φράγμα d στον χρόνο παράδοσης του παλαιότερου μηνύματος που βρίσκεται σε κάποιο κανάλι επικοινωνίας. Τα ασύγχρονα αυτά συστήματα που ικανοποιούν τις 2 παραπάνω συνθήκες τα ονομάζουμε Asynchronous Bounded-Delay Networks. Τα μοντέλα αυτά δικτύων είναι πιο αδύναμα από τα σύγχρονα μοντέλα αλλά πιο ισχυρά από τα ασύγχρονα. Υπό αυτές τις συνθήκες είναι εύκολο να υλοποιηθεί ένας συγχρονιστής με μια μικρή αύξηση σε μηνύματα και χρόνο εκτέλεσης αλλά το βασικό πρόβλημα που προκύπτει στην σχεδίασή του είναι η εξασφάλιση του ότι όλα τα μηνύματα του γύρου r παραλαμβάνονται πριν ξεκινήσει ο γύρος r+1.

Συγχρονιστές ABD

Για να λύσουμε το πρόβλημα αυτό θεωρούμε ότι οι κόμβοι διαθέτουν ένα ρολόι και ότι τα ρολόγια των κόμβων είναι συγχρονισμένα όσο περισσότερο γίνεται και με μέγιστη απόκλιση το πολύ δ. Έτσι οι διεργασίες μεταβαίνουν στον επόμενο γύρο μετά από χρόνο d + δ (Για περαιτέρω ανάλυση στον συγχρονισμό ρολογιών βλέπε φυσικά λογικά ρολόγια σε επόμενη ενότητα) Θεωρούμε τότε ότι υπάρχει ένα άνω φράγμα μ ≥ l+d το οποίο υποθέτουμε ότι είναι γνωστό. Συνεπώς, δεν υποχρεώνουμε την Pu να στείλει ένα μήνυμα null κατά τον γύρο r αν δεν έχει κάποιο μήνυμα να στείλει.

Ο συγχρονιστής ABD αποτελείται από 2 τμήματα, την φάση συγχρονισμού-ρολογιού και την φάση προσομοίωσης. Στην φάση συγχρονισμού κάθε διεργασία μηδενίζει το ρολόι της και στέλνει μηνύματα ‹START› σε κάθε ένα από τους γείτονές της. Μία από τις υποθέσεις των ABD δικτύων είναι πως ο μηδενισμός του ρολογιού και η αποστολή του μηνύματος ‹START› απαιτούν μηδενικό χρόνο εκτέλεσης. Μια διεργασία εκτελεί αυτά τα βήματα είτε για να αρχικοποιήσει τον σύγχρονο αλγόριθμο είτε όταν ληφθεί το πρώτο ‹START› μήνυμα. Αποτέλεσμα του της φάσης συγχρονισμού είναι τα ρολόγια των διεργασιών να είναι συγχρονισμένα με απόκλιση το πολύ δ.

Θεώρημα (ABD.1)

Σε κάθε χρονική στιγμή t μετά την εκτέλεση της φάσης συγχρονισμού-ρολογιού για γειτονικές διεργασίες p και q , τα ρολόγια τους ικανοποιούν την σχέση CLOCK_p(t) - CLOCK_q(t) < d.

Απόδειξη:

Έστω w_p ( ή w_q ) ο χρόνος στον οποίο η p (ή η q) εκτελεί την διαδικασία αρχικοποίησης. Καθώς η p στέλνει ένα μήνυμα ‹START› στον χρόνο w_p και η q εκτελεί την αρχικοποίηση της στο αργότερο όταν το μήνυμα αυτό παραληφθεί, w_q < w_p + d. Από αυτήν την σχέση προκύπτει πως w_p - w_q < d. Επειδή οι p και q δεν αλλάζουν τις τιμές που αναθέτουν στα ρολόγια τους μετά την εκτέλεση της αρχικοποίησης έχουμε για t ≥ max (w_p,w_q) , CLOCK_p(t) - CLOCK_q(t) = [CLOCK_p(w_p) + (t-w_p] - [CLOCK_q(w_q) + (t-w_q] = [0 + (t - w_p)] - [0 + (t - w_q)] = w_q - w_p < d

☐

Στην φάση προσομοίωσης οι διεργασίες εκτελούν τους γύρους που υπαγορεύονται από τον σύγχρονο αλγόριθμο. Ένα μήνυμα που ανταλλάσσεται από τον αλγόριθμο στον γύρο i αναφέρεται i-μήνυμα. Ο i-οστός γύρος ξεκινά όταν το τοπικό ρολόι διαβάσει την τιμή 2id, μετά από μια αλλαγή κατάστασης χρησιμοποιώντας όλα τα (i-1)-μηνύματα που έχει λάβει η διεργασία μέχρι τότε. Ο κατά προσέγγιση συγχρονισμός και το άνω όριο της καθυστέρησης παράδοσης των μηνυμάτων υποδηλώνει πως όλα τα μηνύματα ενός γύρου έχει φτάσει σε μια διεργασία πριν αυτή η διεργασία ξεκινήσει τον επόμενο γύρο, και ότι το σύστημα συμπεριφέρεται σαν ένα σύγχρονο σύστημα.

Εσωτερικές μεταβλητές CLOCKp : clock ; statep : Zp ; pulsep : integer ;

Αρχική Γνώση (Εκτελείται τυχαία κάποια χρονική στιγμή) procedure init: begin if not startedp then begin CLOCKp:=0; forall q Є Neighp do send ‹START› to q end end end init Ip: [ Ένα ‹START› μήνυμα έφτασε στην διεργασία p ] begin receive ‹START› ; init end

Λειτουργία Pp(i): [Η αρχή του i-οστού γύρου] when CLOCKp = 2id do begin (* Τέλος προηγούμενου γύρου, υπολόγισε την κατάσταση του p για την i-1 -statep(i-1)-*) if i==1 then statep:= initial state; else (* M ορίζεται η συλλογή των i-1 μηνυμάτων που παρελήφθησαν *) statep:=dp που ικανοποιεί (statep)├ dp; pulsep:=i; (* αποστολή μηνυμάτων του γύρου i *) Μ' = MG(statep); αποστολή όλων των μηνυμάτων M' end Mp: [Ένα i-μήνυμα έχει φτάσει] begin λήψη και αποθήκευση όλων των μηνυμάτων end

Έστω ότι state_p(i) είναι η κατάσταση της διεργασίας p μετά από i+1 αλλαγές κατάστασης, για παράδειγμα στην έναρξη του (i+1)-οστού γύρου , και γ_i το σύνολο των ( state_p1(i),...,state_pn(i) ). Να σημειωθεί ότι το παραπάνω σύνολο δεν συμβαίνει απαραίτητα κατά την διάρκεια του ABD αλγορίθμου, δηλαδή οι διεργασίες δεν είναι απαραίτητο να βρεθούν ταυτόχρονα σε αυτές τις καταστάσεις.

Θεώρημα (ABD.2)

Η ακολουθία C = (γ₀,γ₁,...) είναι ένας υπολογισμός του σύγχρονου αλγορίθμου..

Απόδειξη:

Μπορεί να αποδειχθεί με επαγωγή στο i ότι η ακολουθία (γ₀,γ₁,...,γ_i) είναι το πρόθεμα ενός υπολογισμού. Για i=0 , παρατηρούμε πως το γ₀ είναι ένα αρχικό στιγμιότυπο του σύγχρονου αλγορίθμου γιατί για κάθε διεργασία αναφέρει την αρχική του κατάσταση στον σύγχρονο αλγόριθμο.

Υποθέτουμε ότι το (γ₀,γ₁,...,γ_i) είναι ένα πρόθεμα του υπολογισμού του σύγχρονου αλγορίθμου. Η διεργασία p τελειώνει τον γύρο i+1 και αλλάζει την κατάσταση του σε state_p(i+1) όταν το ρολόι του φτάσει σε τιμή 2(i+2)d, χρησιμοποιώντας το σύνολο M_p(i+1) των (i+1)-οστών μηνυμάτων που έχει λάβει μέχρι στιγμής. Για να δείξουμε ότι το στιγμιότυπο που ορίζεται ως (state_p1(i+1),...,state_pn(i+1)) επεκτείνει τον υπολογισμό αρκεί να δείξουμε οτι M_p(i+1) αποτελεί ένα σύνολο μηνυμάτων που στέλνονται στην p στον γύρο i+1.

Υποθέτουμε ότι η q στέλνει ένα μήνυμα στην p στον γύρο i+1, παράδειγμα όταν το ρολόι της q δείχνει 2(i+1)d,. Έστω σ ο ολικός χρόνος που αυτό το μήνυμα στάλθηκε, και τ ο αντίστοιχος χρόνος λήψης αυτού του μηνύματος. Καθώς CLOCK_q(σ) = 2(i+1)d και η q είναι γείτονας της p , CLOCK_p(σ)<2(i+1)d+d (Από το θεώρημα ABD.1). Προκύπτει πως τ-σ<d, CLOCK_p(τ)<2(i+1)d+d+d=2(i+2)d δηλαδή το μήνυμα λαμβάνεται από την p πριν τελειώσει ο γύρος i+1.

☐

Είναι πιθανόν μια διεργασία να λάβει ένα μήνυμα του γύρου i πριν η ίδια ξεκινήσει τον γύρο i. Στη περίπτωση αυτή το μήνυμα πρέπει να αποθηκευτεί και να επεξεργαστεί μόνο στον επόμενο γύρο. Πρέπει να είναι δυνατόν κάθε διεργασία να μπορεί να αποφασίσει για κάθε μήνυμα πότε θα πρέπει να το επεξεργαστεί. Αυτό μπορεί να γίνει αν ο αριθμός του παλμού modulo 2 αποστέλλεται μαζί με κάθε μήνυμα. Καμία πρόσθετη πληροφορία δεν χρειάζεται αν κάθε διεργασία διατηρεί στην μνήμη της την τιμή του ρολογιού στην οποία έφτασε το μήνυμα ‹START› από την κάθε διεργασία γείτονα.

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

• Η πολυπλοκότητα του αλγορίθμου μπορεί να εξεταστεί ως προς τον χρόνο και την επικοινωνία για την φάση αρχικοποίησης και την φάση της προσομοίωσης του σύγχρονου συστήματος.
• Η φάση της αρχικοποίησης απαιτεί Ο(2Ε) μηνύματα και χρειάζεται Ο(D) χρονικές μονάδες. (Ε: ακμές γραφήματος , D: αριθμός κόμβων).
• Η φάση της προσομοίωσης δεν απαιτεί ανταλλαγή περισσότερων μηνυμάτων και οι διεργασίες ολοκληρώνουν ένα γύρο εξομοίωσης κάθε 2d χρονικές μονάδες.

Μετά από μελέτη όλων των κλάσεων των συγχρονιστών για ABD δίκτυα που χρειάζονται 2Ε μηνύματα στην φάση αρχικοποίησης και καθόλου πρόσθετα στην προσομοίωση έχουν δείξει ότι ο χρόνος γύρου 2d είναι ιδανικός για αυθαίρετα δίκτυα, δίκτυα δακτυλίου και υπερκύβων. Δίκτυα αστέρα μπορούν να συγχρονιστούν με χρόνο γύρου (3/2)d και οι κλίκες με χρόνο (2-1/N)d.

Σύγκριση αλγόριθμων συγχρονισμού

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

Δρομολόγηση(Πολιτική-Ελάχιστες Μεταβάσεις)

Αλγόριθμος	AsynchBFS	SynchBFS/SimpleSynch	SynchBFS/ABD
Χρονική Πολυπλοκότητα	O(δ • n(d + l))	O(δ • (d + l))	O(δ • μ)
Πολυπλοκότητα Επικοινωνίας	O(n • m)	O(n • m2)	O(n • m)

Δρομολόγηση(Πολιτική-Συντομότερο Μονοπάτι)

Αλγόριθμος	AsynchBellmanFord	BellmanFord/SimpleSynch	BellmanFord/ABD
Χρονική Πολυπλοκότητα	O(n n+1 • (l + d))	O(n • (l + d))	O(n • μ)
Πολυπλοκότητα Επικοινωνίας	O(n n • m)	O(n2 • m2)	O(n2 • m)

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

Απόκλιση Ρολογιού και μη αμελητέος χρόνος επεξεργασίας

Για να χρησιμοποιήσουμε τα αποτελέσματα για τα ABD δίκτυα σε πραγματικές εφαρμογές οι 3 υποθέσεις για τα δίκτυα ABD πρέπει να χαλαρωθούν. Στην πράξη τα ρολόγια των διεργασιών αποκλίνουν και ο χρόνος επεξεργασίας ενός μηνύματος δεν είναι ίσος με 0.
Τα ρολόγια που αποκλίνουν μπορούν να αντιμετωπιστούν χρησιμοποιώντας με αύξηση του χρόνου γύρου σταδιακά στην φάση προσομοίωσης για να αντισταθμίσουμε την πιθανότητα αυξανόμενων αποκλίσεων ανάμεσα σε γειτονικές διεργασίες. Εάν ο χρόνος γύρου γίνει πολύ μεγάλος τότε ίσως να χρειαστεί να ξανά εκτελέσουμε την φάση συγχρονισμού μετά από ένα καθορισμένο αριθμό γύρων.
Εάν ο χρόνος επεξεργασίας των μηνυμάτων ενός γύρου και έναρξης του νέου γύρου δεν είναι αμελητέος αλλά φραγμένος από μια σταθερά έστω π, o συνχρονιστής μπορεί εύκολα να προσαρμοστεί αυξάνοντας τον χρόνο του γύρου κατά π.