Αλγόριθμος εκλογής αρχηγού σε δακτύλιο σε c++

[fire4way]

Ο αλγόριθµος κινείται στα πλαίσια

εκείνου των Chang & Roberts µε την κύρια διαφορά ότι οι επεξεργαστές δεν είναι

αριθµηµένοι µε µοναδικό τρόπο. Κι εδώ ουσιαστικά αναζητείται ο επεξεργαστής µε

το µεγαλύτερο (ή το µικρότερο) αριθµό και τα µηνύµατα µπορούν να κινηθούν προς

µία και µόνο κατεύθυνση.

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

από το σύνολο {1,…,n} και στη συνέχεια γίνεται η εκλογή του µεγαλύτερου µε

ταυτόχρονο έλεγχο της µοναδικότητά του. Αν κάτι τέτοιο δεν είναι αλήθεια ο

αλγόριθµος επαναλαµβάνεται. Για τον έλεγχο της µοναδικότητας είναι απαραίτητη η

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

επαναλήψεις του αλγορίθµου σηµειώνονται από τον αριθµό της φάσης που όπως θα

δούµε µεταφέρεται και από τα µηνύµατα του αλγορίθµου.

Εξ αιτίας του ασυγχρονισµού του δικτύου και της οµοιοµορφίας των επεξεργαστών

απέναντι στον αλγόριθµο, παρουσιάζονται δύο προβλήµατα που καλούµαστε να

λύσουµε για να µπορέσει να λειτουργήσει σωστά ο αλγόριθµος:

1. Κανένας επεξεργαστής δεν µπορεί να αποφασίσει από µόνος του να σταµατήσει

την προσπάθεια για την εκλογή του, αν δε σιγουρευτεί πρώτα πως υπάρχει

τουλάχιστον ένας ακόµα που προσπαθεί να εκλεγεί. Σε αντίθετη περίπτωση

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

την εκλογή και ο αλγόριθµος πέφτει σε αδιέξοδο. Στην περίπτωσή µας το

πρόβληµα αντιµετωπίζεται ως εξής: σε κάθε φάση του αλγορίθµου βγαίνουν από

το παιχνίδι της εκλογής οι επεξεργαστές που καταλαβαίνουν πως είναι αδύνατον

να εκλεγούν, επειδή ακριβώς µαθαίνουν πως υπάρχει ισχυρότερος υποψήφιος. Αν

στη συγκεκριµένη φάση δεν υπάρξει µοναδικός νικητής συνεχίζουν µόνο οι

επεξεργαστές που παρέµειναν ενεργοί στο τέλος της προηγούµενης φάσης. ∆εν

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

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

τουλάχιστον µε µέγιστο νούµερο σε κάθε φάση. Έτσι δεν θα υπάρξει αδιέξοδο.

2. Ο επεξεργαστής δεν µπορεί βασισµένος µόνο στην ταυτότητα που κουβαλάει µαζί

του ένα µήνυµα να διακρίνει µε σιγουριά τα δικά του µηνύµατα, αφού η αρίθµηση

των επεξεργαστών δεν είναι εγγυηµένα µοναδική. Το πρόβληµα αυτό λύνεται αν

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

συνοδεύεται από ένα µετρητή που έχει την τιµή 1 στο ξεκίνηµα του µηνύµατος

και αυξάνεται κάθε φορά που το µήνυµα προωθείται από κάποιον επεξεργαστή.

Ένας επεξεργαστής που θα δεχτεί το µήνυµα µε το µετρητή του ίσο µε n γνωρίζει

µε βεβαιότητα πως είναι δικό του µήνυµα που συµπλήρωσε κύκλο και επέστρεψε

σε αυτόν.

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

µας. Όταν ένας κόµβος καταλάβει πως γίνεται εκλογή στο δακτύλιο και αυτό µπορεί

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

διαλέγει σαν ταυτότητά του έναν αριθµό από το σύνολο {1,…,n} και στέλνει προς

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

µήνυµα: (phv, idv, count, unique). Το phv είναι ο αριθµός της φάσης στην οποία

βρίσκεται ο αλγόριθµος και στην αρχή έχει την τιµή 1, το idv είναι η ταυτότητα του

επεξεργαστή που διάλεξε, count είναι ο µετρητής στον οποίο αναφερθήκαµε

παραπάνω και τέλος unique είναι µια λογική µεταβλητή που σηµατοδοτεί την ύπαρξη

ή όχι κάποιου µοναδικού νικητή. Σκοπός του µηνύµατος είναι η επιστροφή του στον

εκποµπό του και η ανακήρυξη του τελευταίου σε νικητή. Αυτό θα συµβεί µόνον όταν

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

και ο µοναδικός. Κατά την πορεία του στο δακτύλιο το µήνυµα περνάει από άλλους

επεξεργαστές που το προωθούν ή όχι. Αν συναντήσει κάποιο κόµβο u µε (phu, idu) >

(phv, idv) η πορεία του µηνύµατος διακόπτεται, γιατί είτε έχει µικρότερη φάση,

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

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

συµβαίνουν και τα δύο µαζί. Αν συµβαίνει το αντίθετο, τότε ο κόµβος u γίνεται µη

ενεργός, δηλαδή (phu, idu) < (phv, idv), σταµατά δηλαδή από εδώ και πέρα να

συναγωνίζεται για την εκλογή, ενηµερώνονται οι τιµές της φάσης και της ταυτότητά

του και το µήνυµά µας προωθείται. Αν τώρα (phu, idu) = (phv, idv) τότε το µήνυµα

ανήκει στη σωστή φάση και επιπλέον έχει ανακαλύψει έναν κόµβο που έχει τον ίδιο

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

τουλάχιστον στη φάση που διανύει τώρα ο αλγόριθµος. Το µήνυµα προωθείται αλλά

η µεταβλητή unique αλλάζει σε false. Αν τελικά το µήνυµα επιστρέψει στον εκποµπό

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

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

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

καινούριο αριθµό, αυξάνοντας τον αριθµό της φάσης και στέλνοντας νέο µήνυµα

 

Είναι εργασία σε κατανεμημένα συστήματα,ζητήται η επίλυσή της σε c,αν μπορεί να με βοηθήσει κάποιος θα του ήμουν ευγνώμων.Ευχαριστώ

[bxenos]

να εδώ θα βρείς άτομα για λύση http://www.insomnia.gr/forum/showthread.php?t=80906

(50% προκαταβολή υποθέτω).

 

Κάτσε ρε φίλε και δούλεψε λίγο μόνος σου, στην σχολή δεν πήγες για να μάθεις; (εκτός αν θέλεις το πτυχίο για πρόσληψη μόνο)

[Evgenios1]

Μεταφραζεις ολο αυτο το κειμενο στα αγγλικα, και πας εδω. 5-10 ευρουλακια θα σου παρει (λογου του κειμενου)

[Dr.Fuzzy]

Απίστευτο...:-D:-D

[fire4way]

 

Κάτσε ρε φίλε και δούλεψε λίγο μόνος σου, στην σχολή δεν πήγες για να μάθεις; (εκτός αν θέλεις το πτυχίο για πρόσληψη μόνο)

 

Φίλε μου είμαι 25 χρονών και δεν έχω τι διάθεση κάθε ξύπνιου που το παίζει καθηγητής κ κόβει εξάμηνα αβέρτα,μια βοήθεια ζήτησα έχω περιορισμένο χρόνο για να κάτσω να δουλέψω μόνος αν και κάθησα και μάλλον κατι δικό μου θα παραδώσω...Ευχαριστώ πάντως

[Evgenios1]

Φίλε μου είμαι 25 χρονών και δεν έχω τι διάθεση κάθε ξύπνιου που το παίζει καθηγητής κ κόβει εξάμηνα αβέρτα,μια βοήθεια ζήτησα έχω περιορισμένο χρόνο για να κάτσω να δουλέψω μόνος αν και κάθησα και μάλλον κατι δικό μου θα παραδώσω...Ευχαριστώ πάντως

 

Δεν ειναι εξυπναδα... Ποσταρεις μια εργασια δυο σελιδων, και λες θελω κωδικα. Λολ ποιος θα κατσει να ασχοληθει?

[Dr.Fuzzy]

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

 

...εσύ που είσαι "έξυπνος" λοιπόν "παίχτο" φοιτητής και κάτσε κανε την εργασία σου!

 

Αν βαριέσαι, δεν γουστάρεις, δεν μπορείς κλπ, βρες κάτι άλλο να κάνεις στην ζωή σου που να το γουστάρεις!...δεν σου φταίει ο καθηγητής...

 

[drm]

Κάτσε ρε φίλε, δέν μπορείς (ή δεν θές) να γράψεις αυτό το κομμάτι κώδικα, και φταίει ο καθηγητής που σε κόβει ? για εξήγησέ το και σε μάς λιγάκι...

[fire4way]

Κάτσε ρε φίλε, δέν μπορείς (ή δεν θές) να γράψεις αυτό το κομμάτι κώδικα, και φταίει ο καθηγητής που σε κόβει ? για εξήγησέ το και σε μάς λιγάκι...

Συμφωνω και επαυξανω με ολους τους προλαλησαντες αλλα οταν η βαση που υπαρχει δεν ειναι σωστη και δεν εχει διδαχθει απο τα μικροτερα εξαμηνα τα βασικα για να κατσω να δημιουργησω τετοιου βαθμου δυσκολιας κωδικα τοτε ποιος μου φταει??εγω πιστεψε δεν ειμαι ο μονος που δυσκολευομαι αρκετα να λυσω την ασκηση αλλα ενα 90% των 4 τμηματων τουσ συγκεκριμενου μαθηματος...ισως να αν παρακολουθει κανεις την κουβεντα να ποσταρει κ να δεις κ εσυ οτι τα πραγματα ειναι οπως τα λεω.Ναι ειναι δυσκολο να μου φτιαξει καποιος ενα κωδικα 2 σελιδων απλα εκανα το κοπω να το ποσταρω μπας κ τελειωνω τις σπουδες μου,γιατι ειναι τα τελευταια μου εργαστηρια.τεσπα ευχαριστω και πιστεψε με δεν ειμαι απο αυτους που καθονται και κωλοβαρενε και τα περιμενουν ολα ετοιμα.Ευχαριστω παντως που μπηκατε ολοι στο κοπο να απαντησετε.