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

Από DistrSys

Itai-Rodeh

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

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

Χρονική: O(n) Επικοινωνίας: O(nlogn)

Στη σύνταξη του κειμένου συνεισέφερε η Ευανθία Τσιτσόκα

Το πρόβλημα της εκλογής αρχηγού διαφοροποιείται στην περίπτωση που δεν υπάρχουν διακεκριμένες ταυτότητες στο δίκτυο. Σε αυτή την περίπτωση δεν είναι δυνατόν να χρησιμοποιηθούν οι ταυτότητες των διεργασιών για την εκλογή αρχηγού καθώς είναι δυνατό να υπάρχουν περισσότερες διεργασίες που έχουν την ίδια (μέγιστη ίσως) ταυτότητα. Επομένως και οι αλγόριθμοι που μέχρι τώρα έχουν εξεταστεί (LCR, FloodMax, HR) δε μπορούν να χρησιμοποιηθούν. Στην περίπτωση αυτή διακρίνουμε την ύπαρξη μιας συμμετρίας στο δίκτυο. Οπότε το πρόβλημα εκλογής αρχηγού ανάγεται στο πρόβλημα διάσπασης αυτής της συμμετρίας. Ένας αλγόριθμος που λύνει το πρόβλημα αυτό είναι ο αλγόριθμος Itai & Rodeh, που θα περιγραφεί στη συνέχεια.

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

Γενικά ο αλγόριθμος λειτουργεί ως εξής. Κάθε διεργασία διαλέγει τυχαία μια ταυτότητα από το σύνολο {1....n}. Στη συνέχεια ψάχνουμε να βρούμε τη διεργασία με τη μεγαλύτερη ταυτότητα. Αν διαπιστωθεί ότι η μεγαλύτερη ταυτότητα δεν είναι μοναδική, επαναλαμβάνεται τη διαδικασία. Πιο αναλυτικά, ο αλγόριθμος Itai & Rodeh περιγράφεται στη συνέχεια:

Οι διεργασίες διατηρούν μια μεταβλητή αρχηγός=false και μια μεταβλητή φάση=0. Σε κάθε φάση οι διεργασίες διαλέγουν μια ταυτότητα από το σύνολο {1, . . . , n} και την στέλνουν στον δεξιόστροφο γείτονα τους ως εξής: (φάση, ταυτότητα, μετρητής, μοναδική). Αρχικά μετρητής=0 και μοναδική=true. Μόλις λάβουν μία ταυτότητα από τον αριστερόστροφο γείτονα, την συγκρίνουν με την δικιά τους. Αν είναι μεγαλύτερη, την προωθούν στον δεξιόστροφο γείτονα και αυξάνουν τον μετρητή. Αν είναι μικρότερη, δεν κάνουν τίποτα. Αν είναι ίδια, ελέγχουν τον μετρητή: αν είναι μικρότερος από n τότε θέτει την λογική μεταβλητή μοναδική=false και προωθούν το μήνυμα. Αν μετρητής ≥ n και μοναδική=false τότε διαλέγουν μια νέα ταυτότητα, θέτουν φάση++ και επαναλαμβάνουν τον αλγόριθμο. Αλλιώς μεταβαίνουν στην κατάσταση εκλεγμένη θέτοντας την μεταβλητή αρχηγός στην τιμή true.

Εσωτερικές μεταβλητές αρχηγός={true,false}, αρχικά είναι false . κατάσταση={εκλεγμένη, μη-εκλεγμένη}, αρχικά είναι μή-εκλεγμένη. φάση={0,1,...}, αρχικά είναι 0. ταυτότητα={1,..n}, επιλέγεται στην αρχή κάθε φάσης. μετρητής={0,1,...},αυξάνεται σε κάθε γύρο, αρχικά είναι 0. μοναδική={true,false}, αρχικά είναι false.

Αρχική Γνώση Το μέγεθος n του δακτυλίου.

Λειτουργία Κάθε διεργασία διαλέγει τυχαία μια ταυτότητα από το σύνολο {1....n}. Στη συνέχεια ψάχνουμε να βρούμε τη διεργασία με τη μεγαλύτερη ταυτότητα. Αν διαπιστωθεί ότι η μεγαλύτερη ταυτότητα δεν είναι μοναδική, επαναλαμβάνεται τη διαδικασία.

Τερματισμός

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

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

Η χρονική πολυπλοκότητα του αλγορίθμου είναι O(n). Ο αλγόριθμος εξελίσσεται σε φάσεις. Κάθε φάση για να ολοκληρωθεί απαιτεί το μήνυμα να κάνει το γύρο του δακτυλίου. Επομένως κάθε φάση διαρκεί O(n) γύρους. Ο αριθμός των απαιτούμενων φάσεων για την εκλογή αρχηγού μπορεί να αποδειχτεί ότι είναι δηλαδή απαιτείται σταθερός αριθμός φάσεων: O(1). Επομένως η χρονική πολυπλοκότητα είναι O(n).

Η πολυπλοκότητα επικοινωνίας του αλγορίθμου είναι O(nlogn). Για να υπολογιστεί εξετάζουμε μια φάση του αλγορίθμου:

Έστω p(i,d) η πιθανότητα το μήνυμα της διεργασίας που διάλεξε ταυτότητα i να ταξιδέψει απόσταση d.

p(i,d)= Μας ενδιαφέρει να υπολογίσουμε τη μέση απόσταση D που ταξιδεύει κάθε μήνυμα. Αυτό εξαρτάται από την ταυτότητα i. Αν i=n τότε D=n. Διαφορετικά αν i<n τότε υπολογίζεται ως εξής:

Οπότε ο μέσος αριθμός μηνυμάτων N σε μια φάση φράσσεται από:

άρα

Αρα ο αριθμός μηνυμάτων σε μία φάση είναι O(nlogn). Επειδή όμως ο αριθμός των φάσεων είναι μια σταθερά, ο συνολικός αριθμός μηνυμάτων που ανταλλάσσονται είναι O(nlogn).

Κάποια προβλήματα που πρέπει να αντιμετωπίσουμε για να εξασφαλίσουμε την ορθότητα του αλγορίθμου είναι τα εξής:

1. Καμία διεργασία δεν μπορεί να αποφασίσει μονομερώς να σταματήσει. Πρέπει να βεβαιωθεί ότι υπάρχει τουλάχιστον μια διεργασία που θα προσπαθήσει να εκλεγεί.
2. Ο επεξεργαστής δε μπορεί να διακρίνει με σιγουριά τα δικά του μηνύματα μόνο από την ταυτότητα που κουβαλάει κάθε μήνυμα μαζί του.

Τα προβλήματα αντιμετωπίζονται ως εξής:

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