Σημειώσεις:Προβλήματα:Εκλογή Aρχηγού

Από DistrSys

Το πρόβλημα αυτό εμφανίζεται σε περιπτώσεις όπου μια διεργασία πρέπει να επιλεγεί για να "αναλάβει" κάποιον υπολογισμό σε επίπεδο δικτύου. Ένας τέτοιος υπολογισμός μπορεί να είναι για παράδειγμα η εκτέλεση μιας σειράς ενεργειών για την αρχικοποίηση κάποιων διεργασιών, για την έναρξη εκτέλεσης ενός κατανεμημένου υπολογισμού ή για την αρχικοποίηση του δικτύου μετά από κάποια αποτυχία (πχ δημιουργία του token σε δίκτυα token ring). Πολλοί κατανεμημένοι αλγόριθμοι (πχ BFS-Breadth First Search, MST- Minimum Spanning Tree, MIS- Maximal Independed Set) προϋποθέτουν την ύπαρξη μιας τέτοιας διεργασίας αρχηγού. Επειδή δεν είναι γνωστό από την αρχή πόσες και ποιες διεργασίες συμμετέχουν σε ένα δίκτυο, δεν μπορεί να οριστεί μια τέτοια διεργασία εκ των προτέρων, επομένως απαιτείται η ύπαρξη ενός κατάλληλου αλγορίθμου για την επιλογή μιας τέτοιας διεργασίας - αρχηγού. Το πρόβλημα αυτό πρώτος το έθεσε ο LeLann (1977), ο οποίος πρότεινε και την πρώτη λύση. Το πρόβλημα εκλογής αρχηγού αποτυπώνει τα βασικά χαρακτηριστικά μιας μεγάλης ομάδας προβλημάτων που αντιμετωπίζουν τα πραγματικά κατανεμημένα συστήματα και εμφανίζεται σε πολλές παραλλαγές.

Η εκλογή αρχηγού σε ένα δίκτυο απαιτεί την επιλογή μιας μοναδικής διεργασίας που θα βρεθεί στην κατάσταση "αρχηγός" (ή "εκλεγμένη") ενώ όλες οι άλλες διεργασίες βρίσκονται στην κατάσταση "μη-αρχηγός" (ή "μη εκλεγμένη"). Πιο συγκεκριμένα, θεωρούμε ότι κάθε διεργασία έχει μια μοναδική ταυτότητα (UID), επιλεγμένη από ένα αυστηρά διατεταγμένο σύνολο. Το πρόβλημα εκλογής αρχηγού απαιτεί ξεκινώντας από μια διαμόρφωση του δικτύου όπου όλες οι διεργασίες βρίσκονται στην ίδια κατάσταση να καταλήξουμε σε μία διαμόρφωση του δικτύου όπου μόνο μια διεργασία βρίσκεται στη κατάσταση "αρχηγός". Μερικές παραλλαγές του προβλήματος προκύπτουν ανάλογα με το αν οι υπόλοιπες διεργασίες χρειάζεται να γνωρίζουν ότι δεν είναι στην κατάσταση αρχηγός ή να γνωρίζουν την ταυτότητα της διεργασίας-αρχηγού.

Ένας αλγόριθμος επιλύει το πρόβλημα εκλογής αρχηγού όταν ικανοποιεί τις παρακάτω προδιαγραφές:

• Όλες οι διεργασίες εκτελούν τον ίδιο τοπικό αλγόριθμο.
• Ο αλγόριθμος είναι αποκεντρωτικός, δηλαδή ο υπολογισμός μπορεί να ξεκινήσει από ένα αυθαίρετο, μη κενό υποσύνολο των διεργασιών.
• Ο αλγόριθμος φτάνει σε μια τερματική διαμόρφωση σε κάθε υπολογισμό, και σε αυτή τη διαμόρφωση υπάρχει ακριβώς μια διεργασία που βρίσκεται στην κατάσταση αρχηγός και όλες οι υπόλοιπες βρίσκονται στην κατάσταση "μη-αρχηγός".

Για την επίλυση του προβλήματος εκλογής αρχηγού σε ένα δίκτυο, οι ακόλουθοι αλγόριθμοι είναι διαθέσιμοι:

Αλγόριθμοι Εκλογής Αρχηγού:

• LCR (ο αλγόριθμος των LeLann, Chang και Roberts)
• PetersonLE (ο αλγόριθμος του Peterson)
• HS (ο αλγόριθμος των Hirschberg και Sinclair)
• FloodMax (OptFloodMax),
• IR (ο αλγόριθμος των Itai και Rodeh)
• TimeSlice

Υλοποίηση Αλγόριθμων Εκλογής Αρχηγού

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

Ορίζουμε το interface LeaderElection ως εξής:

• command result_t init(uint16_t deviceID) - αρχικοποιεί τις εσωτερικές μεταβλητές του αλγόριθμου. Η παράμετρος deviceID υποδηλώνει την ταυτότητα που θα χρησιμοποιήσει η διεργασία κατά την εκλογή αρχηγού. Το command επιστρέφει πάντα SUCCESS
• command uint16_t get() - επιστρέφει την ταυτότητα της διεργασίας που εκλέχθηκε αν η διαδικασία ολοκληρώθηκε με επιτυχία, αλλιώς UNKNOWN_LEADER.
• command uint8_t getStatus() - επιστρέφει IS_LEADER αν η διεργασία έχει εκλεχθεί, αλλιώς NOT_LEADER.
• command result_t elect() - επιχειρεί την εκκίνηση της διαδικασίας εκλογής αρχηγού. Αν η διαδικασία ξεκινήσει με επιτυχία επιστρέφει SUCCESS. Αν η διαδικασία βρίσκεται σε εξέλιξη ή έχει τερματίσει, επιστρέφει FAIL.
• event result_t electDone(uint16_t leaderID, uint8_t isLeader) - όταν ολοκληρωθεί η διαδικασία εκλογής αρχηγού δημιουργείται ένα event όπου η παράμετρος leaderID υποδηλώνει την ταυτότητα της διεργασίας που εκλέχθηκε και η παράμετρος isLeader την κατάσταση της διεργασίας (IS_LEADER αν η διεργασία έχει εκλεχθεί, αλλιώς NOT_LEADER). Το event επιστρέφει πάντα SUCCESS.

Ο κώδικας που αποτυπώνει το interface LeaderElection σε γλώσσα προγραμματισμού nesC παρουσιάζεται παρακάτω:

interface LeaderElection {
  async command result_t init(uint16_t deviceID);

  async command uint16_t get();

  async command uint8_t getStatus();

  async command result_t elect();

  event result_t electDone(uint16_t leaderID, uint8_t isLeader);
}

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

Ας υλοποιήσουμε την εφαρμογή leaderApp που θέλει να εκλέξει μια μοναδική διεργασία. Για να μπορεί ο χειριστής του συστήματος να διαγνώσει την κατάσταση που βρίσκονται οι συσκευές κατά την λειτουργία τους, η εφαρμογή χρησιμοποιεί κάποια Led ως εξής:

• Όσο εκτελείται ο αλγόριθμος εκλογής αρχηγού το κόκκινο Led είναι αναμμένο. Όταν ολοκληρωθεί η εκτέλεση και τερματίσει ο αλγόριθμος, σβήνει.
• Αν η διεργασία είναι στην κατάσταση αρχηγός (ή εκλεγμένη) το πράσινο Led είναι αναμμένο.
• Αν η διεργασία είναι στην κατάσταση μη-αρχηγός (ή μη εκλεγμένη) το κίτρινο Led είναι αναμμένο.

Επομένως, η εκτέλεση του αλγόριθμου εκλογής αρχηγού και η ενημέρωση της ολοκλήρωσης του γίνεται με την υλοποίηση ενός task και ενός event handler:

task void execLeaderElection() {
  result_t r;

  // Start the leader election process
  r = call LeaderElection.elect();

  if (r == SUCCESS) {
    call Leds.redOn();
    dbg(DBG_TEMP, "Leader Election process started.\n");

  } else
    dbg(DBG_TEMP, "Leader Election process already running.\n");
}

event result_t LeaderElection.electDone(uint16_t leaderID, uint8_t isLeader) {
  call Leds.redOff();

  dbg(DBG_TEMP, "Leader Election process completed.\n");

  if (isLeader) {
     call Leds.greenOn();
     call Leds.yellowOff();
     dbg(DBG_TEMP, "I am the leader!\n");

  } else {
     call Leds.greenOff();
     call Leds.yellowOn();
     dbg(DBG_TEMP, "Device with ID %d is the leader\n", leaderID);
  }

  return SUCCESS;
}

Εφόσον έχουμε να κάνουμε με ένα ασύγχρονο σύστημα, υπάρχει περίπτωση οι συσκευές να μη ξεκινήσουν ταυτόχρονα αλλά να υπάρχει μια χρονική καθυστέρηση. Για να εξασφαλίσουμε ότι όλες οι συσκευές του συστήματος είναι ενεργοποιημένες και συμμετέχουν στην εκλογή αρχηγού χρησιμοποιούμε ένα Timer για να καθυστερήσουμε την εκτέλεση του αλγόριθμου. Σύμφωνα με τα παραπάνω, ορίζουμε το module leaderApp ως εξής:

module leaderApp {
  provides {
    interface StdControl;
  }
  uses {
    interface LeaderElection;
    interface Leds;
    interface Timer;
  }
}
implementation {

  // Initialize the component.
  command result_t StdControl.init() {
    call Leds.init(); 
    call LeaderElection.init(TOS_LOCAL_ADDRESS); 
    return SUCCESS;
  }

  // Start things up -- set the timer to fire once after 1000ms
  command result_t StdControl.start() {
    return call Timer.start(TIMER_ONE_SHOT, 1000);
  }

  // Halt execution of the application -- disables the clock component.
  command result_t StdControl.stop() {
    return call Timer.stop();
  }

  task void execLeaderElection()  {
    // see above
  }

  event result_t LeaderElection.electDone  {
    // see above
  }

  // Start the leader election
  event result_t Timer.fired() {
    post execLeaderElection();
    return SUCCESS;
  }
}

Παρατηρήστε ότι κατά την λειτουργία του συστήματος υπάρχει περίπτωση να προκύψουν τα ακόλουθα είδη σφαλμάτων :

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

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