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

Από DistrSys

TimeSlice

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

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

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

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

Μια διαφορετική απο τις προσεγγίσεις των LCR, FloodMax στη λύση του προβλήματος εκλογής αρχηγού δίνει ο αλγόριθμος TimeSlice. O αλγόριθμος πετυχαίνει πολυπλοκότητα επικοινωνίας O(n) μπορεί όμως να φτάσει σε πολύ μεγάλη χρονική πολυπλοκότητα. Ο αλγόριθμος εφαρμόζεται σε δίκτυα δακτυλίου.

Η βασική ιδέα του αλγορίθμου βρίσκεται στη διαφοροποίηση της “ταχύτητας” με την οποία τα μηνύματα “ταξιδεύουν” στο δίκτυο. Φροντίζουμε τα μηνύματα μιας διεργασίας με μικρό ID να ταξιδεύουν πιο γρήγορα από τα μηνύματα μια άλλης με μεγαλύτερο. Κρατώντας τη συνθήκη από τον LCR πως μια διεργασία εκλέγεται αρχηγός όταν το μήνυμα με την ταυτότητά της κάνει το γύρο του δικτύου και επιστρέψει στην ιδια διεργασία, βάσει του TimeSlice η διεργασία με το μικρότερο ID εκλέγεται αρχηγός. Το μήνυμα μιας διεργασίας με ταυτότητα i ταξιδεύει στο δίκτυο με καθυστέρηση 2i-1 γύρους. Οι διεργασίες ,δηλαδή, που λαμβάνουν μήνυμα με τη ταυτότητα i, προωθούν το μήνυμα αυτό στον δεξιόστροφο γείτονά τους μετά από 2i γύρους. Όποια μη-υποψήφια διεργασία λάβει μήνυμα δεν μπορεί πλέον να θέσει υποψήφια=true.

Εσωτερικές μεταβλητές εκλεγμένη={true,false}, αρχικά είναι false. υποψήφια={true,false}, αρχικά είναι false.

Αρχική Γνώση Οι διεργασίες γνωρίζουν την ταυτότητα τους.

Λειτουργία Η εκτέλεση του αλγορίθμου ξεκινάει τυχαία από κάποια διεργασία u_i. Η διεργασία αυτή θέτει υποψήφια=true και στέλνει την ταυτότητά της στον δεξιόστροφο γείτονά της. Εάν μια διεργασία λάβει μήνυμα δεν μπορεί στη συνέχεια να θέσει υποψήφια = true. Όταν μια υποψήφια διεργασία με ταυτότητα i λάβει μήνυμα από μία υποψήφια διεργασία με ταυτότητα j τότε πραγματοποιεί σύγκριση ταυτοτήτων: Εαν i < j τότε η i δεν προωθεί την ταυτότητα της j. Εαν i > j τότε η i παύει να είναι υποψήφια και προωθεί το μήνυμα της j. Εάν i = j τότε πρόκειται για την ταυτότητα της διεργασίας και η i θέτει εκλεγμένη = true.

Αρχικοποίηση δικτύου

1ος γύρος

2ος γύρος

Ας εξετάσουμε αναλυτικά το παραπάνω παράδειγμα όπου n=5 σε ένα δίκτυο δακτυλίου. Οι διεργασίες έχουν ταυτότητες 0,1,2,3,4. Στον πρώτο γύρο η 1 θέτει υποψήφια = true και στέλνει την ταυτότητά της στην δεξιόστροφη γειτονική της διεργασία. Στον δεύτερο γύρο το μήνυμα της 1 δεν έχει δικαίωμα να προωθηθεί. Ενώ στον ίδιο γύρο η 0 θέτει υποψήφια = true και προωθεί την ταυτότητά της στη 2.

3oς γύρος

4oς γύρος

5ος γύρος

Στον τρίτο γύρο το μήνυμα της 1 προωθείται στην 0. Επειδή η 0 είναι ήδη υποψήφια συγκρίνει τη δικιά της ταυτότητα με την ταυτότητα που φέρει το μήνυμα. Επειδή 0<1 η διεργασία 0 δεν θα μεταδώσει περεταίρω το μήνυμα της 1. Η διεργασία 2 προωθεί στην 3 το μήνυμα της 0. Στον 4ο γύρο η 3 προωθεί το μήνυμα της 0 στην 1 ενώ η 4 προσπαθεί να θέσει υποψήφια=true. Στο σημείο αυτό η 4 δεν μπορεί κάνει αυτή την ανάθεση καθώς σε προηγούμενο γύρο έχει προωθήσει την ταυτότητα της 1. Στον 5 γύρο προωθείται η ταυτότητα της 0.

6ος γύρος

Τερματισμός

Στον 6 και τελευταίο γύρο η ταυτότητα της 0 έχει επιστρέψει σ' αυτήν. Η διαδικασία 0 θέτει εκλεγμένη= true.

Σύμφωνα με τον αλγόριθμοo τo μήνυμα μιας διαδικασίας με ταυτότητα j θα έχει διανύσει απόσταση n/2^j-i στο χρόνο το μήνυμα μιας διαδικασία με ταυτότητα i θα έχει διανύσει απόσταση n.

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