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

Από DistrSys

BFS

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

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

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

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

Η εφαρμογή του αλγορίθμου Bellman-Ford σ' ένα ισχυρά συνεκτικό δίκτυο διεργασιών έχει σαν αποτέλεσμα την παραγωγή ενός επικαλυπτικού δέντρου που αποτελείται από συντομότερα μονοπάτια. Για να επιτευχθεί αυτό, κάθε κανάλι (ακμή του γραφήματος) χαρακτηρίζεται από ένα θετικό αριθμό : το βάρος. Το άθροισμα των βαρών των καναλιών (ακμών) που καθορίζουν το μονοπάτι είναι το βάρος του μονοπατιού. Η κατασκευή ενός τέτοιοι επικαλυπτικού δέντρου έχει ως κύριο σκοπό την ελαχιστοποίηση του μέγιστου κόστους κατά τη μετάδοση πληροφορίας μέσα στο δίκτυο. Η φυσική έννοια του βάρους μπορεί να ποικίλει: ταχύτητα μετάδοσης, κόστος μετάδοσης κ.λπ. Οι υποθέσεις που κάνουμε για την εφαρμογή του αλγορίθμου είναι πως οι διεργασίες πέρα από την ταυτότητά τους και το πλήθος των διεργασιών του δικτύου γνωρίζουν τα βάρη των καναλιών που τις συνδέουν με τις γειτονικές τους διεργασίες. Κατά την εκτέλεση του αλγορίθμου οι διεργασίες ανταλλάσουν μηνύματα μεταφέροντας την απόστασή τους από τη ρίζα του επικαλυπτικού δέντρου. Μια διεργασία επιλέγει για γονέα της τη γειτονική της διεργασία για την οποία το άθροισμα απόσταση + βάρος είναι το ελάχιστο.

Εσωτερικές μεταβλητές απόσταση={0,1,2,...}, αρχικά είναι ∞ γονέας=<ταυτότητα>, αρχικά είναι 0

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

Λειτουργία Σε κάθε γύρο οι διεργασίες στέλνουν τη τιμή της μεταβλητής απόσταση σε όλους τους γείτονές τους. Κάθε διεργασία u εντοπίζει το μήνυμα της v για το οποίο το άθροισμα απόστασηv + βάροςvu είναι το ελάχιστο. Στη συνέχεια θέτει απόσταση =απόστασηv + βάροςvu και γονέας=v. Μετά απο n-1 γύρους τιμή της μεταβλήτής απόσταση είναι η ελάχιστη δυνατή ενώ το μονοπάτι που συνδέει τη u με τη ρίζα είναι το συντομότερο.

Σε ένα δίκτυο που τα βάρη των καναλιών είναι μεταξύ τους ίδια τότε ο Bellman-Ford παράγει ένα BFS επικαλυπτικό δέντρο.

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

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

1ος γύρος- 1o βήμα

1ος γύρος- 2ο βήμα

Ας εξετάσουμε το παραπάνω παράδειγμα όπου n=5 με m=5 κανάλια επικοινωνίας. Το βάρος του κάθε καναλιού αναγράφεται στο δίπλα από αυτό. Κάθε διεργασία διατηρεί τις μεταβλητές απόσταση, γονέας μέσα στο λευκό κουτί. Η διεργασία 1 ξεκινά την κατασκευή του επικαλυπτικού δέντρου: Θεωρεί τον εαυτό της παιδί της με μηδενική απόσταση από τη ρίζα (0,1) ενώ στη συνέχεια στέλνει την απόστασή της από τον εαυτό της (0) στους γείτονές της. Οι υπόλοιπες διεργασίες στέλνουν στις γειτονικές τους καθώς δεν γνωρίζουν ακόμα τον γονέα τους. (1ος γύρος-1ο βήμα). Οι διεργασίες 2 και 5 θέτουν γονέας=1 με απόσταση_21=5 και αποταση_51=1. (2ος γύρος-2ο βήμα)

2ος γύρος - 1ο βήμα

2ος γύρος - 2ο βήμα

Στην αρχή του 2ου γύρου η διεργασία 1 δεν έχει αλλάξει απόσταση -καθώς είναι η ρίζα του δέντρου- οπότε επαναλαμβάνει την ίδια αποστολή μηνύματος: στέλνει απόσταση 0 στους γείτονές της. Η διεργασία 2 έχοντας θέσει για γονέα της την 1 έχει τώρα απόσταση από τη ρίζα ίση με 5. Στέλνει το αντίστοιχο μήνυμα στους γείτονές της. Η 5 στέλνει απόσταση 1στους γείτονές της. Οι διεργασίες 3,4 δεν έχουν ακόμα εισαχθεί στο δέντρο έτσι στέλνουν στου γείτονές τους μήνυμα με απόσταση=∞. (2ος γύρος-1ο βήμα). Μετά την αποστολή των μηνυμάτων οι διεργασίες 3,4 θέτουν ως γονέα τους την 5 με απόσταση_35=9 και απόσταση_45=6.(2ος γύρος-2ο βήμα). Οι αποστολές επαναλαμβάνονται στον 3ο γύρο. Όλες οι διεργασίες στέλνουν στις γειτονικές τους τις αποστάσεις τους από τη ρίζα: Η διεργασία 1 στέλνει 0, η διεργασία 2,5 , η διεργασία 3,9 κ.ο.κ. (3ος γύρος-1ο βήμα).

3ος γύρος - 1ο βήμα

3ος γύρος - 2ο βήμα

Κατά τον 3ο γύρο η διεργασία 3 λαμβάνει μήνυμα από την 4. Κατά την σύγκριση της απόστασής της από τη ρίζα προκύπτει πως απόσταση_35 > απόσταση_34. Έτσι η 3 θέτει γονέας=4 και απόσταση_34=7 (3ος γύρος-2ο βήμα). Η αποστολή επαναλαμβάνεται στον 4ο γύρο: Η διεργασία 1 στέλνει 0, η διεργασία 2,5 , η διεργασία 3,7 κ.ο.κ. (4ος γύρος-1ο βήμα). Στο τέλος του 4ου γύρου καμία αλλαγή στη δομή του δέντρου δεν χρειάζεται να γίνει. (4ος γύρος-2ο βήμα)

4ος γύρος - 1ο βήμα

4ος γύρος - 2ο βήμα

Τελική δομή

Μετά το τέλος του 4ου γύρου η δομή του δέντρου είναι και η τελική. Τα μονοπάτια που έχουν δημιουργηθεί είναι τα συντομότερα. (Τελικό δίκτυο).

Τερματισμός

Είναι εμφανές ότι μετά από n-1 γύρους η μεταβλητή απόσταση έχει διανύσει την επιθυμητή απόσταση. Η απόδειξη της ορθότητα γίνεται με επαγωγή στον αριθμό των γύρων: μετά από γ γύρους οι μεταβλητές απόσταση_u και γονέας_u μιας διεργασίας u αντιστοιχούν στο συντομότερο μονοπάτι που την συνδέει με την ρίζα του δέντρου u_0. Εάν δεν υπάρχει κάποιο μονοπάτι μήκους γ τότε η διεργασία u δεν έχει μπει στο δέντρο και γονέας_u=0 απόσταση_u=∞.

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