Ο αλγόριθ µ ος των 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 να κάνει τη σύγκριση . Οι διεργασίες που χάνουν την εκλογή και γίνονται
παθητικές , απλώς προωθούν τα µ ηνύ µ ατα που λα µ βάνουν . Εάν µ ία διεργασία λάβει
µ ία ταυτότητα που είναι ίση µ ε τη δική της τότε ανακηρύσσεται αρχηγός , ενώ αν
λάβει µ ία ταυτότητα διαφορετική από τη δική της συγκρίνει την ταυτότητα αυτή µ ε
τη δική της και µ ε το τρέχον ελάχιστο που έχει κρατήσει από τις προηγού µ ενες
συγκρίσεις . Αν η παρεληφθείσα ταυτότητα είναι η µ ικρότερη , τότε η διεργασία
γίνεται παθητική και κρατά το νέο ελάχιστο .
Για κάθε διεργασία θα πρέπει να αποθηκεύετε την ταυτότητά της , το τρέχον
ελάχιστο , την ταυτότητα του αρχηγού και την κατάστασή της .
Παρακαλώ την βοηθειά σας!!!