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

Από DistrSys

DFS

Πρόβλημα: Κατανεμημένες Δομές Δίκτυο: Συνεκτικό , μορφής G=(V,E) Κλάση: Αποκεντρωτικός

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

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

Στη σύνταξη του κειμένου συνεισέφεραν οι Απόστολος Φίλιππας

Η δημιουργία μιας επικαλυπτικής δομής πάνω σε ένα δίκτυο, βρίσκει πολλές χρήσεις σε κατανεμημένα συστήματα (γρήγορη μετάδοση πληροφορίας, αντιμετώπιση άλλων προβλημάτων). H εκτέλεση του αλγορίθμου ClassicDFS έχει ως αποτέλεσμα την δημιουργία ενός επικαλυπτικού κατά βάθος δέντρου πάνω σε ένα συνεκτικό δίκτυο. Η δομή είναι πλήρως κατανεμημένη υπό την έννοια ότι δεν είναι αποθηκευμένη σε κάποιον συγκεκριμένο κόμβο, αλλά κάθε κόμβος γνωρίζει μόνο τον κόμβο-πατέρα του και (προαιρετικά) τους κόμβους-παιδιά του. Θεωρούμε πως η ρίζα του δέντρου που θα δημιουργηθεί έχει ήδη αποφασιστεί από το δίκτυο με την εφαρμογή κάποιου αλγορίθμου εκλογής αρχηγού. O αλγόριθμος κατασκευής δέντρου κατά βάθος που θα δούμε, βασίζεται στον αλγόριθμο Tarry για την κατασκευή επικαλυπτικού δέντρου πάνω σε συνεκτικά γραφήματα. Θα δούμε πρώτα τον αλγόριθμο Tarry και ύστερα τροποποιώντας τον θα καταλήξουμε στον ClassicDFS.

Tarry's Algorithm

Η ρίζα εκκινεί τον αλγόριθμο διαλέγοντας έναν γειτονικό της κόμβο για να του στείλει το token (ένα μήνυμα). Κάθε κόμβος που λαμβάνει το token ελέγχει:

1. Αν δεν έχει θέσει τον κόμβο-πατέρα του, τότε θέτει ως κόμβο-πατέρα τον κόμβο από τον οποίο έλαβε το token.
2. Aν υπάρχουν γειτονικοί του κόμβοι (εκτός του κόμβου-πατέρα) στους οποίους δεν έχει στείλει ακόμα το token, τότε, επιλέγει έναν εξ' αυτών και του στέλνει το token. Αλλιώς, αν δηλαδή δεν υπάρχουν κόμβοι στους οποίους να μην έχει στείλει το token, τότε, στέλνει το token στον κόμβο-πατέρα του.

Ο αλγόριθμος τερματίζει όταν ο κόμβος-ρίζα έχει στείλει το token σε όλους τους γειτονικούς του κόμβους. Τότε έχει κατασκευαστεί μία κατανεμημένη δομή επικαλυπτικού δέντρου.

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

Ο αλγόριθμος έχει σχεδιαστεί έτσι ώστε να ικανοποιούνται οι εξής συνθήκες:

• Συνθήκη 1: Κανένας κόμβος δεν στέλνει δύο φορές το token στον ίδιο γείτονα.
• Συνθήκη 2: Κάθε κόμβος (εκτός της ρίζας), στέλνει το token στον πατέρα του, μόνο εάν δεν μπορεί να το στείλει σε κανένα άλλο κόμβο σύμφωνα με την Συνθήκη 1.

H ικανοποίηση των συνθηκών αυτών μας εγγυάται την κατασκευή επικαλυπτικού δέντρου επί του δικτύου (βλ. Introduction to Distributed Algorithms, G.Tel , σελ. 207).

(Σκιαγράφηση Απόδειξης) Λόγω της Συνθήκης 1, κανένας κόμβος δεν μπορεί να στείλει μήνυμα δύο φορές στον ίδιο γείτονα, άρα κάθε ακμή του δικτύου χρησιμοποιείται το πολύ δύο φορές (μία από τον κάθε κόμβο που την ορίζει). Άρα η πολυπλοκότητα μηνυμάτων είναι O(2|Ε|). Αφού μόνο η διεργασία που έχει το token μπορεί να στείλει, σε κάθε χρονική στιγμή μόνο μία διεργασία μπορεί να στέλνει. Άρα τα μηνύματα ανταλλάσσονται σειριακά και η χρονική πολυπλοκότητα είναι O(2|Ε|).

ClassicDFS

Ο αλγόριθμος είναι ίδιος με τον προηγούμενο με μία τροποποίηση: Όταν ένας κόμβος λάβει το token και έχει ήδη κάποιον πατέρα (προφανώς διαφορετικό από αυτόν που του έστειλε το token), τότε ο κόμβος αυτός στέλνει κατευθείαν το token πίσω στον κόμβο από τον οποίο το έλαβε.

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

Πλέον πέραν των δύο συνθηκών που ικανοποιούνταν και πριν, ικανοποιείται και μία τρίτη συνθήκη:

• Συνθήκη 3: Όταν ένας κόμβος λαμβάνει το token, τότε το στέλνει πίσω στον κόμβο από τον οποίο το έλαβε, αν αυτό επιτρέπεται από τις συνθήκες 1 και 2.

H ικανοποίηση των τριών συνθηκών μας εγγυάται πως το επικαλυπτικό δέντρου που κατασκευάστηκε είναι και κατά βάθος. Ο λόγος φαίνεται στην παρακάτω εικόνα:

o 4 επιλέγει να στείλει στον 2

o 2 στέλνει στον 4 λόγω της Συνθήκης 3

o 4 στέλνει στον 5

Στο σχήμα παραλείπονται τα 3 πρώτα βήματα του αλγορίθμου κατά τα οποία ο κόμβος 1 έστειλε στον 2, ο 2 στον 3 και ο 3 στον 4 μήνυμα και άρα οι κόμβοι που έλαβαν έθεσαν ως γονέα τον κόμβο που τους έστειλε το μήνυμα (token).

Στην πρώτη εικόνα, ο κόμβος 4 αποφασίζει να στείλει το token στον κόμβο 2. Μπορεί να το κάνει αφού δεν παραβιάζει καμία από τις συνθήκες. Ο κόμβος 2 όμως έχει ήδη θέσει πατέρα, άρα για να ικανοποιηθεί η Συνθήκη 3 θα ξαναστείλει αμέσως το token πίσω στον κόμβο 2. Αυτός με την σειρά του θα στείλει το token στον κόμβο 5, και θα έχει δημιουργηθεί ένα spanning DFS tree.

Παρατηρώ πως αν δεν υπήρχε η Συνθήκη 3, στο δεύτερο βήμα ο κόμβος 2 θα μπορούσε να έχει επιλέξει να στείλει μήνυμα στον κόμβο 5, ο οποίος τότε θα έθετε ως πατέρα του τον κόμβο 2. Όμως το δέντρο που θα είχε τότε δημιουργηθεί δεν θα ήταν κατά βάθος. Άρα εξηγήσαμε διαισθητικά γιατί η Συνθήκη 3 μας εξασφαλίζει πως το spanning tree που θα δημιουργηθεί θα είναι και DFS.

Oι πολυπλοκότητες παραμένουν ίδιες με πριν, δηλαδή έχουμε πολυπλοκότητα μηνυμάτων τάξης O(2|Ε|) και χρονική πολυπλοκότητα τάξης O(2|Ε|).