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

Από DistrSys

LCR

Πρόβλημα: Εκλογή Αρχηγού Δίκτυο: Δακτύλιος Κλάση: Αποκεντρωτικός

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

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

Ο πρώτος αλγόριθμος που έχει εμφανιστεί για το πρόβλημα εκλογής αρχηγού ονομάζεται αλγόριθμος LCR προς τιμήν του Le Lann που διατύπωσε την πρώτη έκδοση του [L77] και των βελτιώσεων που πρότειναν οι Chang και Roberts [CR79]. Ο αλγόριθμος έχει το προτέρημα της εύκολης υλοποίησης, της επεκτασιμότητας σε άλλες τοπολογίες και της πολύ καλής απόδοσης κάτω από ορισμένες συνθήκες χρονισμού του δικτύου (βλ. σύγχρονα συστήματα).

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

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

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

Ο αλγόριθμος είναι αποκεντρωτικός: αρχικά όλες οι διεργασίες στέλνουν την ταυτότητα τους στο δίκτυο δακτυλίου. Όταν μια διεργασία λάβει μία εισερχόμενη ταυτότητα, τη συγκρίνει με τη δικιά της. Αν η εισερχόμενη ταυτότητα έχει αριθμό μεγαλύτερο από το δικό της, τότε υπάρχει πιθανότητα το μήνυμα που ήρθε να περιέχει την ταυτότητα του νικητή, οπότε την στέλνει προς την επόμενη γειτονική διεργασία. Αν αντίθετα, η ταυτότητα που περιέχει το μήνυμα είναι μικρότερη από την ταυτότητα της διεργασίας, τότε αποκλείεται να μεταφέρει την ταυτότητα του νικητή οπότε το μήνυμα αγνοείται. Αν τέλος η ταυτότητα του μηνύματος είναι ίδια με αυτή της διεργασίας, τότε η διεργασία εκλέγεται αρχηγός σε αυτόν το γύρο και η διαδικασία τερματίζεται. Με αυτόν τον τρόπο, το μήνυμα που περιέχει την μεγαλύτερη ταυτότητα πρόκειται να διατρέξει όλο το δίκτυο. Μόλις το μήνυμα επιστρέψει στην αρχική διεργασία που το έστειλε αρχικά, τότε η διεργασία αντιλαμβάνεται ότι έχει την μεγαλύτερη ταυτότητα και ανακηρύττεται αρχηγός.

Εσωτερικές μεταβλητές αρχηγός={true,false}, αρχικά είναι false κατάσταση={εκλεγμένη,μη-εκλεγμένη}, αρχικά είναι μή-εκλεγμένη

Αρχική Γνώση Οι διεργασίες γνωρίζουν την ταυτότητα τους

Λειτουργία Οι διεργασίες εκπέμπουν την ταυτότητα τους στον δεξιόστροφο γείτονα τους. Μόλις λάβουν μία ταυτότητα από τον αριστερόστροφο γείτονα, την συγκρίνουν με την δικιά τους. Αν είναι μεγαλύτερη, την προωθούν στον δεξιόστροφο γείτονα. Αν είναι μικρότερη, δεν κάνουν τίποτα. Αν είναι ίδια, μεταβαίνουν στην κατάσταση εκλεγμένη θέτοντας την μεταβλητή αρχηγός στην τιμή true.

Θεωρούμε ότι οι διεργασίες είναι αριθμημένες από το 1 έως το n με δεξιόστροφη κατεύθυνση (οι διεργασίες δεν έχουν γνώση αυτού του τρόπου αρίθμησης). Έστω i_u η ταυτότητα της διεργασίας u και έστω u_max η διεργασία με τη μεγαλύτερη ταυτότητα i_max. Τότε, στο στο τέλος του γύρου n η διεργασία u_max εκλέγεται αρχηγός και καμία άλλη διεργασία εκτός από την u_max δεν είναι σε κατάσταση εκλεγμένη.

Αρχικοποίηση δικτύου

1ος γύρος

2ος γύρος

Ας εξετάσουμε αναλυτικά το παραπάνω παράδειγμα όπου n=8. Οι ταυτότητες των διεργασιών είναι οι αριθμοί στα μπλε κουτιά. Επομένως για τη διεργασία 1 η ταυτότητα είναι i₁=6, για τη διεργασία 2 η ταυτότητα είναι i₂=9, για τη διεργασία 3 i₃=2 κοκ. Στο πρώτο γύρο όλες οι διεργασίες στέλνουν ένα μήνυμα με τη ταυτότητα τους στον δεξιόστροφο γείτονα τους. Μόλις παραλάβουν το μήνυμα, το συγκρίνουν με τη δικιά τους ταυτότητα και αν είναι μεγαλύτερο το προωθούν στην επόμενη διεργασία. Στο παράδειγμα, οι διεργασίες 3, 5, 7, 8 θα προωθήσουν το μήνυμα που έλαβαν στην επόμενες διεργασίες. Ας εξετάσουμε την περίπτωση της διεργασίας 3: έχει ταυτότητα i₃=2 και έλαβε ένα μήνυμα με ταυτότητα 9. Εφόσον η ταυτότητα 9 είναι μεγαλύτερη από τη ταυτότητα της διεργασίας 3, η διεργασία θα προωθήσει το μήνυμα στο δεξιόστροφο γείτονά της. Άρα στο δεύτερο γύρο εκπέμπουν μήνυμα μόνο αυτές οι 4 διεργασίες στο δεξιόστροφο γείτονα τους. Όπως και πριν, μόλις οι διεργασίες παραλάβουν τα μηνύματα, συγκρίνουν την ταυτότητα που περιέχουν με την δικιά τους και αν είναι μεγαλύτερη προωθούν το μήνυμα στην επόμενη διεργασία. Στο παράδειγμα, οι διεργασίες 4, 8 θα προωθήσουν το μήνυμα που έλαβαν στην επόμενες διεργασίες. Ας εξετάσουμε την περίπτωση της διεργασίες 8: έχει ταυτότητα i₈=1 και έλαβε ένα μήνυμα με ταυτότητα 8, μεγαλύτερη από την δικιά της. Άρα στον δεύτερο γύρο εκπέμπουν μήνυμα μόνο αυτές οι 2 διεργασίες στον δεξιόστροφο γείτονα τους.

3ος γύρος

4ος γύρος

5ος γύρος

Στους επόμενους δύο γύρους, δύο μηνύματα κυκλοφορούν στο δίκτυο και περιέχουν τις ταυτότητες 8 και 9. Στον γύρο 5, η διεργασία 2 θα παραλάβει το μήνυμα που περιέχει ταυτότητα 8. Εφόσον η ταυτότητα του μηνύματος είναι μικρότερη από αυτή της διεργασίας, το μήνυμα δεν θα προωθηθεί προς τον επόμενο γείτονα. Άρα από τον 5ο γύρο και μέχρι τον 8ο γύρο, μόνο ένα μήνυμα κυκλοφορεί στο δίκτυο, που περιέχει την ταυτότητα 9.

6ος γύρος

7ος γύρος

8ος γύρος

Στο τέλος του 8ο γύρου, η διεργασία 2 θα παραλάβει το μήνυμα με ταυτότητα 9 και θα διαπιστώσει ότι έχει την μεγαλύτερη ταυτότητα στον δακτύλιο. Τότε θα θέσει τις εσωτερικές μεταβλητές αρχηγός=true και κατάσταση=εκλεγμένη.

Τερματισμός

Μερικές φορές επιθυμούμε μετά την εκλογή της διεργασίας με την μεγαλύτερη ταυτότητα, όλες οι διεργασίες στο δακτύλιο να ενημερωθούν για την ταυτότητα της. Αυτό μπορεί να γίνει με την χρήση ενός ειδικού μηνύματος που περιέχει την ταυτότητα της διεργασίας. Η διεργασία που εκλέγεται αρχηγός, στέλνει ένα ειδικό μήνυμα προς τον δεξιόστροφο γείτονα της. Όταν μια διεργασία παραλάβει το ειδικό μήνυμα, προωθεί το μήνυμα στον επόμενο γείτονα και τερματίζει την λειτουργία της. Κατά αυτόν τον τρόπο το ειδικό μήνυμα θα διασχίσει όλο το δακτύλιο έως ότου φτάσει ξανά στην διεργασία αρχηγό. Όταν η διεργασία αρχηγός παραλάβει το μήνυμα, τερματίζει.

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

Ο αλγόριθμος πραγματικά βρίσκει τη μοναδική μέγιστη ταυτότητα στο σύστημα. Αυτό διότι η μοναδική φορά κίνησης των μηνυμάτων και η τοπολογία του δακτυλίου αναγκάζουν ένα μήνυμα να περάσει από όλες τις άλλες διεργασίες πριν επιστρέψει στην διεργασία που το έστειλε αρχικά. Η φύση του αλγορίθμου επιτρέπει μόνο στο μήνυμα με την μεγαλύτερη ταυτότητα να συμπληρώσει έναν πλήρη κύκλο χωρίς να κοπεί από κάποια από τις ενδιάμεσες διεργασίες. Έτσι, μόνο η διεργασία με τη μεγαλύτερη ταυτότητα δέχεται πίσω το μήνυμα της και ανακηρύσσεται η μοναδικός αρχηγός της διαδικασίας εκλογής.

Στη συνέχεια, θεωρούμε ότι η πρόσθεση με αριθμούς διεργασιών γίνεται modulo n. Επομένως, ο αριθμός διεργασίας 0 αντιστοιχεί στην διεργασία n και ο αριθμός n+1 στη διεργασία 1. Επίσης αναφέρουμε το μήνυμα που στέλνει η διεργασία u ως send_u.

Λήμμα (LCR.1)

Η διεργασία με ταυτότητα i_max θέτει αρχηγός=true και κατάσταση=εκλεγμένη στο τέλος του γύρου n.

Απόδειξη:

Αρκεί να δείξουμε ότι μετά απο r γύρους, όπου 0≤r≤n-1, το send_{umax + r} είναι η ταυτότητα i_max. Για r=0 ισχύει, εφόσον send_umax = i_max. Το επαγωγικό βήμα βασίζεται στο γεγονός ότι στο τέλος του γύρου r, η διεργασία u_max+r λαμβάνει την ταυτότητα i_max και εφόσον είναι η μεγαλύτερη ταυτότητα θα στείλει send_umax+r = i_max. Άρα στο γύρο n η διεργασία u_max-1 θα στείλει στην u_max την ταυτότητα i_max οπότε η u_max θα θέσει τις μεταβλητές αρχηγός=true και κατάσταση=εκλεγμένη.

☐

Λήμμα (LCR.2)

Καμία διεργασία εκτός της u_max δεν θέτει αρχηγός=true και κατάσταση=εκλεγμένη.

Απόδειξη:

Παρατηρούμε ότι για κάθε διεργασία u σε οποιοδήποτε γύρο r, οι διεργασίες u_max, u_max+1, ..., u-1, u δεν θα στείλουν την ταυτότητα της u. Άρα η u δεν θα λάβει ποτέ την ταυτότητα της και επομένως δεν θα θέσει ποτέ τις μεταβλητές αρχηγός=true και κατάσταση=εκλεγμένη. Κατά αυτό το τρόπο δείχνουμε ότι για όλες τις άλλες διεργασίες αρχηγός=false και κατάσταση=μη-εκλεγμένη εφόσον καμία δεν θα καταφέρει να "περάσει" το μήνυμα με την ταυτότητα της πέρα από τη διεργασία i_max.

☐

Θεώρημα (LCR.3)

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

Απόδειξη:

Προκύπτει από τα λήμματα LCR.1 και LCR.2.

☐

Όπως ήδη έχουμε αναφέρει, σε κάθε αλγόριθμο μας ενδιαφέρει η χρονική του συμπεριφορά και ο συνολικός αριθμός των διακινούμενων μηνυμάτων (και bits). Η χρονική συμπεριφορά του αλγόριθμου εξαρτάται από τον τρόπο εκκίνησης των διεργασιών. Αν όλες οι διεργασίες αντιληφθούν ταυτόχρονα την ανάγκη εκκίνησης της διαδικασίας εκλογής και αρχίσουν μαζί την εκτέλεση του αλγορίθμου, τότε η ολοκλήρωση της εκλογής απαιτεί n γύρους, δηλαδή όσοι γύροι απαιτούνται για την συμπλήρωση ενός πλήρους κύκλου μηνυμάτων στο δακτύλιο. Στην περίπτωση όπου η διεργασία με την μεγαλύτερη ταυτότητα αντιληφθεί πρώτη την ανάγκη εκτέλεσης του αλγορίθμου, όπως είναι φανερό, θα χρειαστεί n γύρους για να συμπληρώσει το μήνυμα με την ταυτότητα της έναν κύκλο στο δακτύλιο. Αν επιθυμούμε όλες οι διεργασίες να τερματίσουν, τότε χρειάζονται επιπλέον n γύροι για να σταλεί το ειδικό μήνυμα σε όλες τις διεργασίες του δακτυλίου. Επομένως σε όλες τις περιπτώσεις, η χρονική πολυπλοκότητα είναι γραμμική ως προς το πλήθος των διεργασιών, δηλαδή O(n).

Για να αναλύσουμε την πολυπλοκότητα επικοινωνίας εξετάζουμε τρεις περιπτώσεις: την καλύτερη δυνατή (υπό την έννοια των ελάχιστων απαραίτητων μηνυμάτων για την ολοκλήρωση της εκλογής), τη χειρότερη δυνατή και τη μέση περίπτωση. Και στις τρεις περιπτώσεις θεωρούμε την ταυτόχρονη εκκίνηση όλων των διεργασιών. Αυτό σημαίνει ότι περισσότερα μηνύματα ανταλλάσσονται κατά τους πρώτους γύρους και επομένως θα καταλήξουμε σε άνω φράγματα των αντίστοιχων περιπτώσεων. Κάθε άλλος τρόπος αρχής του αλγορίθμου απαιτεί λιγότερα μηνύματα. Εφόσον υπάρχει ομοιομορφία στον τρόπο ξεκινήματος του αλγορίθμου, από την άποψη του χρόνου, η διαφοροποίηση των περιπτώσεων που εξετάζουμε έγκειται στον τρόπο κατανομής των επεξεργαστών στο δακτύλιο.

Καλύτερη περίπτωση: Οι επεξεργαστές έχουν μπει στο δακτύλιο με αύξουσα σειρά κατά τη φορά κίνησης των μηνυμάτων. Έτσι κάθε μήνυμα κάνει διαδρομή μήκους 1 αφού ο πρώτος επεξεργαστής που θα συναντήσει έχει νούμερο μεγαλύτερο από το δικό του. Από τον κανόνα εξαιρείται το μήνυμα του μεγαλύτερου σε αριθμό επεξεργαστή που θα κάνει διαδρομή μήκους n - κανένας άλλος επεξεργαστής δεν μπορεί να το σταματήσει πλην του εκπομπού του. Έτσι έχουμε συνολικά n - 1 μηνύματα διαδρομής ένα και ένα μήνυμα διαδρομής n. (Το μήκος της διαδρομής είναι επανεκπομπές του ίδιου μηνύματος και σε τελική ανάλυση εκφράζει αριθμό μηνυμάτων). Σύνολο μηνυμάτων για την καλύτερη περίπτωση του αλγόριθμού μας: n - 1 + n = 2n - 1. Επομένως στην καλύτερη περίπτωση η πολυπλοκότητα επικοινωνίας είναι O(n).

Χειρότερη περίπτωση: Οι επεξεργαστές είναι τοποθετημένοι σε φθίνουσα σειρά κατά τη φορά κίνησης των μηνυμάτων. Τώρα κάθε μήνυμα θα κάνει τη μέγιστη δυνατή του διαδρομή μέχρι να εξαλειφθεί. Για την ακρίβεια, όλα τα μηνύματα θα σταματήσουν στον επεξεργαστή με το μέγιστο νούμερο. Έτσι το μήνυμα με το μικρότερο νούμερο θα κάνει διαδρομή μήκους ένα, το αμέσως μεγαλύτερο διαδρομή μήκους 2 κ.ο.κ., ενώ πάλι το μήνυμα του νικητή θα κάνει τη μέγιστη δυνατή διαδρομή, μήκους n. Συνολικός αριθμός μηνυμάτων για την περίπτωση που εξετάζουμε:

Επομένως στην χειρότερη περίπτωση η πολυπλοκότητα επικοινωνίας είναι O(n²)

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

Όπως τονίσαμε στην αρχή του αλγόριθμου, κάθε επεξεργαστής εξετάζεται μονοσήμαντα από κάποιον αριθμό. Δεν μειώνουμε την γενικότητα του αλγόριθμου υποθέτοντας ότι τα νούμερα των n επεξεργαστών κυμαίνονται από 1 έως το n. Έστω P(i,k) είναι η πιθανότητα ότι το μήνυμα i (μήνυμα i ονομάζουμε το μήνυμα που εκπέμπεται από τον i επεξεργαστή) κάνει διαδρομή μήκους k, δηλαδή επανεκπέμπεται k - 1 φορές πριν εξαλειφθεί από κάποιο κόμβο. Σύμφωνα με τη λογική του αλγόριθμού μας η παραπάνω πιθανότητα είναι ίδια με την πιθανότητα οι k - 1 γείτονες του κόμβου i προς τη φορά κίνησης των μηνυμάτων να έχουν αριθμούς μικρότερους του i και ο k γείτονας αριθμό μεγαλύτερό του. Θεωρώντας ότι η πιθανότητα κατάληψης μιας θέσης στο δακτύλιο είναι ίδια για όλους τους επεξεργαστές μας κι ακόμα γνωρίζοντας ότι υπάρχουν i - 1 επεξεργαστές με αριθμούς μικρότερους του i και n - 1 με αριθμούς μεγαλύτερους του, θα έχουμε:

Pr{o k γείτονας του i να έχει αριθμό > i} =

όπου C(a,b) είναι οι συνδυασμοί των a πραγμάτων ανά b:

Έτσι η μέση διαδρομή για τα μηνύματα i - πλήν του n που σίγουρα έχει μήκος διαδρομής n - θα είναι:

Και ο συνολικός μέσος αριθμός των διακινούμενων μηνυμάτων:

Επομένως στην μέση περίπτωση η πολυπλοκότητα επικοινωνίας είναι O(n log n)

Ο αριθμός των διακινούμενων bits βασίζεται στον τρόπο ανάθεσης ταυτοτήτων στις διεργασίες. Έτσι για μια αρίθμηση των διεργασιών από 1 έων n χρειάζονται log n bits για την αναπαράσταση του κάθε μηνύματος. Ο αριθμός των απαιτούμενων bits είναι συνάρτηση του αριθμητικού διαστήματος στο οποίο κυμαίνονται οι ταυτότητες των διεργασιών. (Επειδή το n, το πλήθος των διεργασιών, δεν θεωρείται γνωστό δεν μπορούμε να χρησιμοποιήσουμε κάποια modulo τεχνική για αναγωγή των αριθμών των διεργασιών στο διάστημα [1,n]>). Γενικά μπορούμε να θεωρήσουμε πως ο μέςσος αριθμός των χρησιμοποιούμενων bits είναι Ω(n log²n).

Υλοποίηση Αλγόριθμου

Στην συνέχεια παρουσιάζουμε την υλοποίηση του αλγόριθμου LCR με την χρήση της γλώσσας nesC στο περιβάλλον TinyOS.

Λόγω της ασύγχρονης λειτουργίας του συστήματος, η σωστή εκτέλεση του αλγόριθμου απαιτεί την ύπαρξη μιας ουράς για τα εξερχόμενα μηνύματα. Για αυτό τον λόγο χρησιμοποιούμε το component QueuedSend που προσφέρει το ίδιο interface SendMsg με το component GenericComm αλλά τοποθετεί τα μηνύματα σε μια ουρά. Tα αρχεία που υλοποιούν το component QueuedSend είναι στον φάκελο /opt/tinyos-1.x/tos/lib/Queue. Κατά την μεταγλώττιση της εφαρμογή μας, για να συμπεριληφθεί σωστά το component QueuedSend πρέπει να εισάγουμε στο Makefile την εξής γραμμή:

 PFLAGS= -I%T/lib/Queue

Η υλοποίηση του αλγόριθμου AsynchLCR, σε υψηλό επίπεδο, αποτελείται από το module AsynchLCRM που περιέχει την λογική της διαδικασίας, το component GenericComm που χρησιμοποιείται για την παραλαβή Active Messages και το component QueuedSend που χρησιμοποιείται για την αποστολή Active Messages. Το διάγραμμα διασύνδεσης απεικονίζεται γραφικά στην παρακάτω εικόνα.

Algorithm LCR

includes LCRMsg;

configuration AsynchLCR {
  provides interface StdControl;
  provides interface LeaderElection;
}
implementation {
  components AsynchLCRM, QueuedSend, GenericComm;

  AsynchLCRM.SendMsg -> QueuedSend.SendMsg[AM_LCRMSG];
  AsynchLCRM.ReceiveMsg -> GenericComm.ReceiveMsg[AM_LCRMSG];

  StdControl = GenericComm;
  StdControl = QueuedSend;
  LeaderElection = AsynchLCRM;
}

Το αρχείο LCRMsg.h ορίζει την δομή των μηνυμάτων του αλγόριθμου και τις απαραίτητες σταθερές. Η δομή του μηνύματος LCRMsg είναι πολύ απλή:

• Το πεδίο id χρησιμοποιείται για την αποθήκευση της ταυτότητας που πρόκειται να σταλεί.
• Το πεδίο isLeader χρησιμοποιείται για τα μηνύματα τερματισμού που στέλνει η εκλεγμένη διεργασία (με τιμή IS_LEADER).

typedef struct LCRMsg {
  uint16_t id;
  uint8_t isLeader;
} LCRMsg;

enum {
  AM_LCRMSG = 14,
  UNKNOWN_LEADER = 65534,
  IS_LEADER = 1,
  NOT_LEADER = 0	
};

Το module AsynchLCRM χρησιμοποιεί τα interface SendMsg και ReceiveMsg για την αποστολή και παραλαβή μηνυμάτων και προσφέρει το interface LeaderElection.

module AsynchLCRM {
  provides {
    interface LeaderElection;
  }
  uses {
    interface SendMsg;
    interface ReceiveMsg;
  }
}

Οι διεργασίες διατηρούν (α) μια μεταβλητή uint16_t m_ID με την ταυτότητα της διεργασίας, (β) μια μεταβλητή uint8_t m_isLeader με την κατάσταση εκλεγμένη/μη-εκλεγμένη, (γ) μια μεταβλητή uint16_t m_leaderID με την ταυτότητα της μοναδικής διεργασίας που εκλέχθηκε, και (δ) μια μεταβλητή TOS_Msg m_msg για την αποστολή μηνυμάτων.

implementation {
  uint16_t m_ID;
  uint16_t m_leaderID;
  uint8_t  m_isLeader;
  TOS_Msg  m_msg;

  // ...

Η αρχικοποίηση του αλγόριθμου γίνεται ως εξής:

  // Initialize the leader election process.
  async command result_t LeaderElection.init(uint16_t deviceID) {
    atomic {
      m_isLeader = NOT_LEADER;
      m_ID = deviceID;
      m_leaderID = UNKNOWN_LEADER;
    }

    dbg(DBG_BOOT, "AsynchLCR: initialized.\n");
    return SUCCESS;
  }

και οι δύο συναρτήσεις get του interface LeaderElection υλοποιούνται απλά:

  // Get current leader ID. 
  async command uint16_t LeaderElection.get() {
    return m_leaderID;
  }

  // Get current status. 
  async command uint8_t LeaderElection.getStatus() {
    return m_isLeader;
  }

Η υλοποίηση της elect ελέγχει κατά πόσο έχει ήδη ολοκληρωθεί η διαδικασία, δηλ. αν η leaderID δεν έχει τιμή UNKNOWN_LEADER αλλά το ID της μοναδικής διεργασίας. Σε περίπτωση που δεν έχει ολοκληρωθεί η διαδικασία, η διεργασία στέλνει ένα μήνυμα με την ταυτότητα της. Παρατηρήστε ότι η χρήση της καθολικής μεταβλητής γίνεται με το πρόθεμα atomic.

  // Start the leader election process.
  async command result_t LeaderElection.elect() {
    uint16_t leaderID;
    atomic leaderID = m_leaderID;

    // Check if already finished
    if (leaderID != UNKNOWN_LEADER)
      return FAIL;

    dbg(DBG_USR1, "AsynchLCR: started\n");

    // Send first message (with deviceID)
    post sendMessage();
    return SUCCESS;
  }

Τέλος, το interface LeaderElection ορίζει και την χρήση του event electDone. Η δημιουργία νέων event γίνεται από το task reportElectDone. Παρατηρήστε τον τρόπο δημιουργίας νέων event με το πρόθεμα signal. Παρατηρήστε ότι η χρήση των καθολικών μεταβλητών γίνεται με το πρόθεμα atomic και την αντιγραφή τους σε τοπικές μεταβλητές.

  // Generate the event of the completion of the leader election process
  task void reportElectDone() {
    uint16_t leaderID;
    uint8_t isLeader = NOT_LEADER;

    atomic {
      leaderID = m_leaderID;
      if (m_leaderID == m_ID) {
        m_isLeader = IS_LEADER;
        isLeader = IS_LEADER;
      }
    }

    dbg(DBG_BOOT, "AsynchLCR: terminated.\n");
    signal LeaderElection.electDone(leaderID, isLeader);
  }