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

Από DistrSys

LubyMIS

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

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

Χρονική: - Επικοινωνίας: -

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

Δεν είναι δύσκολο να δειχθεί ότι για κάποιους γράφους, δεν είναι δυνατόν να λυθεί αν οι διεργασίες πρέπει να είναι ντετερμινιστικές. Η απόδειξη είναι αντίστοιχη με αυτή του θεωρήματος 3.1 (N. Lynch, Distributed Algorithms). Εδώ θα χρησιμοποιήσουμε randomization για να υπερπηδήσουμε τις περιορισμένες ικανότητες των ντετερμινιστικών συστημάτων. Για την ακρίβεια, ο randomized αλγόριθμός μας, θα λύσει στην πραγματικότητα ένα πιο αδύναμο πρόβλημα, δεδομένου ότι θα υπάρχει μια πιθανότητα να μην τερματίσει ποτέ (αν και η πιθανότητα είναι 0). Αυτός ο αλγόριθμος λέγεται LubyMIS, προς τιμήν του δημιουργού του.

Ο LubyMIS βασίζεται στο εξής: Ένα μή μηδενικό independent set διαλέγεται από τον γράφο G, οι κόμβοι αυτού του σετ και οι γείτονες τους αφαιρούνται από τον γράφο, και επαναλαμβάνεται η διαδικασία. Αν W ένα υποσύνολο των κόμβων ενός γράφου, τότε χρησιμοποιούμε nbrs(W) για να δείξουμε το σετ των γειτόνων του W.

Έστω το graph να είναι ένα record με πεδία nodes, edges και nbrs, έτσι ώστε να δείχνει τα αντίστοιχα στοιχεία του γράφου G. Έστω I ένα σετ από κόμβους, αρχικά άδειο.

while graph nodes != φ do
	choose a nonempty set I'(_ graph nodes that is independent in graph
	I= I U I'
	graph:= the induced subgraph of graph on graph nodes - I' - graph nbrs(I')
end while

Εύκολα βλέπουμε ότι έτσι δημιουργείται πάντα ένα MIS. Για να δούμε ότι είναι independent σημειώνουμε ότι σε κάθε βήμα, το επιλεγμένο σετ I' είναι independent, και αφαιρούμε από τον γράφο τους γείτονες των κόμβων που μπαίνουν στο I. Για να δείξουμε ότι είναι maximal, σημειώστε ότι οι μόνοι κόμβοι που αφαιρούνται είναι γείτονες των κόμβων που μπαίνουν στο I. Η σημαντική ερώτηση στην υλοποίηση αυτό το γενικό αλγόριθμο είναι το πώς επιλέγουμε το I' σε κάθε βήμα. Εδώ είναι που χρησιμοποιείται το randomization. Σε κάθε βήμα, κάθε διεργασία i επιλέγει έναν ακέραιο στο διάστημα {1,…,} στην τύχη, χρησιμοποιώντας ενιαία κατανομή. Ο λόγος που χρησιμοποιούμε το σαν όριο είναι ότι είναι αρκετά μεγάλο ώστε με μεγάλη πιθανότητα όλες οι διεργασίες του γράφου θα επιλέξουν μοναδικές τιμές. Αφού οι διεργασίες έχουν επιλέξει τις τιμές τους, ορίζουμε το I' να αποτελείται απο όλους τους κόμβους i που είναι τοπικοί νικητές, δηλαδή, οι κόμβοι εκείνοι για τους οποίους > , για κάθε γείτονα j του i. Αυτό προφανώς θα μας δώσει ένα independent set, αφού δύο γείτονες δεν γίνεται να νικήσουν ταυτόχρονα ο ένας τον άλλον.

Σε αυτή την υλοποίηση είναι πιθανόν, σε κάποιους γύρους να έχουμε κενό I'. Αυτοί οι γύροι είναι 'άχρηστοι' από την πλευρά μας καθώς δεν καταφέρνουν τίποτα. Όμως, εφόσον ο αλγόριθμος δεν φτάσει σε ένα σημείο όπου απλά επαναλαμβάνει μονίμως άχρηστους γύρους, μπορούμε να τους αγνοήσουμε και να θεωρήσουμε ότι ο LubyMIS λειτουργεί σωστά. Φυσικά, στην ανάλυση μας οι γύροι αυτοί δεν θα αγνοηθούν.

Ο αλγόριθμος LubyMIS (ανεπίσημα)

Ο αλγόριθμος δουλεύει σε stages, το καθένα από τα οποία αποτελείται από 3 γύρους.

Γύρος 1ος: Στο πρώτο γύρο ενός stage, οι διεργασίες επιλέγουν τις τιμές (val) τους και τις στέλνουν στους γείτονες τους. Στο τέλος του πρώτου γύρου,
           όταν όλα τα μηνύματα val έχουν ληφθεί, οι νικητές ξέρουν ποιές είναι.

Γύρος 2ος: Στον δεύτερο γύρο, οι νικητές ειδοποιούν τους γείτονες τους. Στο τέλος του δεύτερου γύρου, οι χαμένοι -δηλαδή οι διεργασίες που έχουν
           γείτονες πλέον στο I'- ξέρουν ποιοί είναι.

Γύρος 3ος: Στον τρίτο γύρο, ο κάθε χαμένος ειδοποιεί τους γείτονες τους. Τότε όλες οι εμπλεκόμενες διεργασίες (οι νικητές, οι χαμένοι, και οι γείτονες
           των χαμένων) αφαιρούν τους αντίστοιχους κόμβους και ακμές τους από τον γράφο. Συγκεκριμένα, αυτό σημαίνει ότι οι νικητές και οι χαμένοι σταματάνε να
           παίρνουν μέρος στον αλγόριθμο μετά από αυτό το stage, και οι γείτονες των χαμένων αφαιρούνε όλες τις ακμές που έχουν σχέση με τους κόμβους
           που αφαιρέθηκαν.

Τώρα θα περιγράψουμε τον αλγόριθμο πιο επίσημα στο μοντέλο μας. Όπως είπαμε παραπάνω, η κάθε διεργασία χρησιμοποιεί μία τυχαία συνάντηση , την οποία καλεί σε κάθε γύρο πριν τις και . Εδώ χρησιμοποιούμε την random για να δείξουμε μια τυχαία επιλογή μεταξύ του {1,…,}, χρησιμοποιώντας ενιαία κατανομή.

Ο αλγόριθμος LubyMIS (επίσημα)

states:
round e {1,2,3} initially 1
val e {1,…,n^4}, initially arbitrary
awake, a Boolean, initially true
rem-nbrs, a set of vertices, initially the neighbords in the original graph G
status e {unknown, winner, loser}, initially unknown

rand_i:
if awake and round = 1 then val = random

msgs_i:
if awake then
	case
		round=1:
		send val to all nodes in rem-nbrs
		round=2:
		if status = winner then
			send winner to all nodes in rem-nbrs
		round=3:
		if status = loser then
			send loser to all nodes in rem-nbrs
	endcase

trans_i:
if awake then
	case
		round=1:
		if val>u for all incoming values u then status := winner
		round=2:
		if a winner message arrives then status = loser
		round=3:
		if status in {winner,loser} then awake :=false
		rem-nbrs:= rem-nbrs - {j: a loser message arrives from j}
	endcase
	round:=(round+1mod3)

Σημειώνουμε ότι ο LubyMIS συνεχίζει να δουλεύει σωστά εάν, σε κάποια stages, κάποιες γειτονικές διεργασίες επιλέξουν την ίδια τυχαία τιμή.

Τερματισμός

Έχουμε ήδη αναφέρει ότι, εφόσον ο LubyMIS δεν μείνει στάσιμος εκτελώντας άχρηστα stages επ' άπειρον, θα δημιουργήσει ένα MIS. Τώρα θα αποδείξουμε ότι με πιθανότητα 1 ο αλγόριθμος δεν μένει στάσιμος. Συγκεκριμένα, θα υποστηρίξουμε ότι σε οποιοδήποτε βήμα του αλγορίθμου, ο αναμενόμενος αριθμός ακμών που θα αφαιρεθούν είναι τουλάχιστον ένας σταθερό μέρος των εναπομεινάντων ακμών. Αυτό σημαίνει ότι υπάρχει μία σταθερή πιθανότητα ότι τουλάχιστον ένα μέρος των ακμών αφαιρείται. Αυτό με τη σειρά του σημαίνει ότι ο προσδοκώμενος αριθμός γύρων μέχρι τον τερματισμό είναι O(nlogn). Επίσης σημαίνει ότι, με πιθανότητα ένα, ο αλγόριθμος πραγματικά τερματίζει.

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

Η ολοκληρωμένη ανάλυση του LubyMIS μπορεί να βρεθεί στο αρχικό paper του Luby, και προϋποθέτει αρκετές γνώσεις γράφων. Εμείς απλά παραθέτουμε το κυρίως τεχνικό λήμμα χωρίς απόδειξη, και δείχνουμε πώς χρησιμοποιείται για να λάβουμε το ζητούμενο αποτέλεσμα. Για τα επόμενα τρία λήμματα, G=(V,E) και, για έναν αυθαίρετο κόμβο i V, ορίζουμε

όπου d(j) είναι ο βαθμός του j στο G. Ορίστε το τεχνικό λήμμα:

Λήμμα (Λήμμα 1)

Έστω το I' ορισμένο σε ένα stage του αλγορίθμου LubyMIS. Έτσι, για κάθε i στον γράφο ακριβώς πριν το stage,

Χρησιμοποιώντας το παραπάνω λήμμα, λαμβάνουμε το όριο του αναμενόμενου αριθμού ακμών που θα αφαιρεθούν από τον γράφο:

Λήμμα (Λήμμα 2)

Ο αναμενόμενος αριθμών ακμών που θα αφαιρεθούν από τον γράφο G σε ένα stage του LubyMIS είναι τουλάχιστον .

Απόδειξη:

Ο αλγόριθμος διασφαλίζει ότι κάθε ακμή με τουλάχιστον μία 'σύνδεση' στο nbrs(I') αφαιρείται. Επομένως ο αναμενόμενος αριθμός ακμών που θα αφαιρεθούν είναι τουλάχιστον:

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

Στη συνέχεια χρησιμοποιούμε το όριο του πρώτου λήμματος, φτάνοντας στο συμπέρασμα ότι ο αναμενόμενος αριθμός ακμών προς αφαίρεση είναι τουλάχιστον:

Σπάζοντας το παραπάνω με βάση το ποιός όρος του min() είναι μικρότερος, αυτό είναι ίσο με:

Τώρα επεκτείνουμε τον ορισμό του sum(i) και γράφουμε το d(i) ώς άθροισμα, και έχουμε:

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

Το λήμμα 2 μπορεί να χρησιμοποιηθεί ώστε να συμπεράνουμε:

Λήμμα (Λήμμα 3)

Με πιθανότητα τουλάχιστον , ο αριθμός των ακμών που θα αφαιρεθούν απο το G σε ένα stage του LubyMIS είναι τουλάχιστον

Χρησιμοποιώντας τα λήμματα 2 και 3, συμπεραίνουμε:

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

Με πιθανότητα 1, ο LubyMIS τελικά τερματίζει. Επιπλέον, ο αναμενόμενος αριθμός γύρων μέχρι τον τερματισμό είναι O(nlogn).

Τυχαιοποιημένοι αλγόριθμοι

Η τεχνική της τυχαιοποίησης είναι μια πολυχρησιμοποιημένη μέθοδος στα κατανεμημένα συστήματα. Η κύρια χρήση της είναι να σπάσει την συμμετρία. Για παράδειγμα, τα προβλήματα leader-election και MIS δεν μπορούν να λυθούν σε γενικούς γράφους από ντετερμινιστικές διεργασίες χωρίς UID λόγω της αδυνατότητας να σπάσει η συμμετρία. Σε αντίθεση, αυτά τα προβλήματα μπορούν να λυθούν με χρήση τυχαιοποίησης. Ακόμα και εάν δεν υπάρχουν UID, η τυχαιοποίηση μπορεί να επιτρέψει το ταχύτερο σπάσιμο της συμμετρίας.

Παρόλα αυτά, ένα από τα προβλήματα της τυχαιοποίησης είναι ότι η εγγυημένη ορθότητα ή/και επίδοση πιθανόν να ισχύουν μόνο με μεγάλη πιθανότητα, και όχι με σιγουριά. Για παράδειγμα, οποιαδήποτε εκτέλεση του LubyMIS είναι εγγυάται την δημιουργία ενός independent set, ανεξάρτητα των αποτελεσμάτων των τυχαίων επιλογών. Η επίδοση όμως εξαρτάται από την τυχαιότητα των επιλογών. Υπάρχει επίσης και μία πιθανότητα (η οποία όμως είναι 0) ότι όλες οι διαδικασίες θα διαλέγουν επ' άπειρον την ίδια τιμή, και επομένως να βρεθούμε σε στασιμότητα. Το κατά πόσο και εάν αυτό αποτελεί σημαντικό μειονέκτημα του αλγορίθμου εξαρτάται από την εκάστοτε εφαρμογή.