Προσο µ οίωση του αλγορίθ µ ου των Peterson/Dolev-Klawe-Rodeh για

Προσο µ οίωση του αλγορίθ µ ου των Peterson/Dolev-Klawe-Rodeh για

дэргэд stauros Mpasakiotis -
Хариу нийтлэлийн тоо: 0

Ο αλγόριθ µ ος των Chang & Roberts επιτυγχάνει O(NlogN) (Ν ο αριθ µ ός των

κό µ βων ) πολυπλοκότητα µ ηνυ µ άτων στη µ έση περίπτωση , αλλά στη χειρότερη

περίπτωση ό µ ως επιτυγχάνει O(N 2 ). O αλγόριθ µ ος των Peterson/Dolev-Klawe-Rodeh

επιτυγχάνει πολυπλοκότητα µ ηνυ µ άτων O(NlogN) στη χειρότερη περίπτωση

βελτιώνοντας τον αλγόριθ µ ο των Chang & Roberts για την εκλογή αρχηγού σε

δακτυλίους µ ονής κατεύθυνσης , όπου κάθε κό µ βος έχει τη δική του µ οναδική

ταυτότητα .

Ο αλγόριθ µ ος βασίζεται στην παρακάτω ιδέα . Αρχικά κάθε ταυτότητα είναι ενεργή ,

αλλά σε κάθε γύρο κάποιες ταυτότητες γίνονται παθητικές , όπως θα δείξου µ ε στη

συνέχεια Σε ένα γύρο µ ία ενεργή ταυτότητα συγκρίνει τον εαυτό της µ ε τις ενεργές

ταυτότητες των δύο γειτονικών της κό µ βων , που βρίσκονται η µ ία κατά τη φορά και

η άλλη αντίθετα από τη φορά των δεικτών του ρολογιού . Υποθέτοντας ότι εκλέγεται

η µ ικρότερη ταυτότητα , αν µ ία ενεργή ταυτότητα αποτελεί τοπικό ελάχιστο (µ ετά την

παραπάνω σύγκριση ), τότε παρα µ ένει ενεργή και προχωρά στον επό µ ενο γύρο

διαφορετικά γίνεται παθητική . Έτσι µ ετά από logN γύρους θα έχει απο µ είνει στο

δακτύλιο µ όνο µ ία ενεργή ταυτότητα και αυτή κερδίζει την εκλογή .

Η ιδέα αυτή µ πορεί να εφαρ µ οστεί απ ’ ευθείας σε δακτυλίους που είναι διπλής

κατεύθυνσης . Στους µ ονής κατεύθυνσης ό µ ως δακτυλίους τα µ ηνύ µ ατα µ πορούν να

κινούνται µ όνο κατά τη µ ία φορά (π .χ . αυτή των δεικτών του ρολογιού ), πράγ µ α που

κάνει δύσκολη την απόκτηση της ταυτότητας που βρίσκεται κατά την κατεύθυνση

κίνησης των µ ηνυ µ άτων . Ας υποθέσου µ ε ότι έχου µ ε ένα δακτύλιο όπου βρίσκονται

µ εταξύ άλλων τρεις ενεργές σε σειρά ταυτότητες r,q,p. Τότε η q µ πορεί να λάβει το

µ ήνυ µ α της r, αλλά δεν µ πορεί να λάβει το µ ήνυ µ α της p γιατί ο δακτύλιος είναι

µ ονής κατεύθυνσης και δεν πρέπει να περι µ ένει ένα ολόκληρο κύκλο για να το

παραλάβει . Για να γίνει ό µ ως η σύγκριση η q στέλνει την ταυτότητά της στην p και η

r δεν στέλνει απλώς την ταυτότητά της στην q, αλλά η q την προωθεί στην p, ώστε η

p να κάνει τη σύγκριση . Οι διεργασίες που χάνουν την εκλογή και γίνονται

παθητικές , απλώς προωθούν τα µ ηνύ µ ατα που λα µ βάνουν . Εάν µ ία διεργασία λάβει

µ ία ταυτότητα που είναι ίση µ ε τη δική της τότε ανακηρύσσεται αρχηγός , ενώ αν

λάβει µ ία ταυτότητα διαφορετική από τη δική της συγκρίνει την ταυτότητα αυτή µ ε

τη δική της και µ ε το τρέχον ελάχιστο που έχει κρατήσει από τις προηγού µ ενες

συγκρίσεις . Αν η παρεληφθείσα ταυτότητα είναι η µ ικρότερη , τότε η διεργασία

γίνεται παθητική και κρατά το νέο ελάχιστο .

Για κάθε διεργασία θα πρέπει να αποθηκεύετε την ταυτότητά της , το τρέχον

ελάχιστο , την ταυτότητα του αρχηγού και την κατάστασή της .



Παρακαλώ την βοηθειά σας!!!
Үнэлгээний дундаж: -