Σημειώσεις:Προβλήματα:Κατανεμημένες Δομές

Από DistrSys

Πίνακας περιεχομένων 1 Επικαλυπτικά Δέντρα 2 Δέντρα Αναζήτησης Κατά Εύρος 2.1 Εκπομπή μηνυμάτων στο δίκτυο(Broadcast) 2.2 Convergecast 2.3 Καθολικός/Κατανεμημένος υπολογισμός(Global Computation) 2.4 Εκλογή αρχηγού 2.5 Υπολογισμός διαμέτρου δικτύου 3 Δέντρα Αναζήτησης Κατά Βάθος 4 Ελάχιστα Μονοπάτια 5 Maximal Independent Set 6 Υλοποίηση Αλγόριθμων Κατασκευής Κατανεμημένων Δομών

Επικαλυπτικά Δέντρα

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

Ένα επικαλυπτικό δέντρο T(G) ενός δικτύου G περιέχει όλες τις διεργασίες του δικτύου (κορυφές) και ορισμένα (ίσως όλα) κανάλια επικοινωνίας (ακμές). Η κατασκευή ενός επικαλυπτικού δέντρου προϋποθέτει την επιλογή μιας διεργασίας u₀ που θα είναι η ρίζα του δέντρου T(G). Όταν η κατασκευή ολοκληρωθεί, όλες οι διεργασίες πρέπει κατ' ελάχιστον να γνωρίζουν την διεργασία γονέα τους στο δέντρο. Σε ορισμένες εφαρμογές είναι απαραίτητο κάθε διεργασία να γνωρίζει επιπλέον στοιχεία όπως το ύψος της στο δέντρο.

Αλγόριθμοι Κατασκευής Επικαλυπτικών Δέντρων:

• SpanningTree

Δέντρα Αναζήτησης Κατά Εύρος

Σε ένα δίκτυο G, η αναζήτηση κατά εύρος απαιτεί την κατασκευή ενός επικαλυπτικού δέντρου T(G), με ρίζα την διεργασία u₀ όπου οι κορυφές που είναι σε απόσταση d από την u₀ στο G, βρίσκονται στο επίπεδο d στο δέντρο T(G). Όταν η κατασκευή ολοκληρωθεί, όλες οι διεργασίες πρέπει κατ' ελάχιστον να γνωρίζουν την διεργασία γονέα τους στο δέντρο. Σε ορισμένες εφαρμογές είναι απαραίτητο κάθε διεργασία να γνωρίζει επιπλέον στοιχεία όπως το ύψος της στο δέντρο.

Αλγόριθμοι Κατασκευής Δέντρων Αναζήτησης Κατά Εύρος:

• BFS

Η κατασκευή αυτής της δομής είναι χρήσιμη σε πολλές περιπτώσεις για την γρήγορη μετάδοση πληροφορίας, εκλογής αρχηγού, το πρόβλημα της καταμέτρησης. Ποιο αναλυτικά:

Εκπομπή μηνυμάτων στο δίκτυο(Broadcast)

Αν μία διαδικασία θέλει να εκπέμψει ένα μήνυμα K σε όλες τις διεργασίες του δικτύου, μπορεί να το πετύχει ξεκινώντας την κατασκευή ενός BFS δέντρου με ρίζα τον εαυτό της και επισυνάπτοντας το μήνυμα K στο μήνυμα αναζήτησής της(piggyback). Τότε, από την κατασκευή του αλγορίθμου, παρατηρούμε πως το μήνυμα K θα το παραλάβει και κάθε άλλη διεργασία, αφού το BFS δέντρο είναι επικαλυπτικό. Άρα μαζί με την κατασκευή του BFS δέντρου θα έχει γίνει και το broadcast του μηνύματος Κ.

Μια άλλη ιδέα θα ήταν να μπορούμε να χρησιμοποιήσουμε ξανά ένα BFS δέντρο που έχουμε κατασκευάσει για broadcast. Για να μπορέσει να γίνει αυτό, ακολουθούμε την διαδικασία που περιγράφεται στην υποενότητα Τερματισμός, ώστε κάθε διεργασία-γονέας να ξέρει τα παιδιά της. Άρα πλέον μπορεί να γίνει broadcast ενός μηνύματος Κ από διεργασία u χρησιμοποιώντας το BFS δέντρο με ρίζα την u και ακολουθώντας την εξής διαδικασία: η διεργασία u στέλνει το μήνυμα K στα παιδιά της, αυτά στα δικά τους παιδιά κτλ. Έτσι ο χρόνος που χρειάζεται για να γίνει broadcast ένα μήνυμα , είναι Ο(diam) και ο απαιτούμενος αριθμός μηνυμάτων είναι βέλτιστος και τάξης Ο(n).

Convergecast

Αντίστοιχα με το broadcast ενός μηνύματος από την ρίζα στους κόμβους , μπορεί να γίνει και convergecast, δηλαδή μετάδοση μηνύματος από οποιονδήποτε κόμβο προς την ρίζα. Η διαδικασία αυτή είναι παρόμοια με το broadcast, και δεν απαιτεί κάθε διεργασία να ξέρει τα παιδιά της αλλά μπορεί να γίνει μόνο αφότου ολοκληρωθεί η κατασκευή του BFS δέντρου. Ο χρόνος που χρειάζεται για να γίνει convergecast ένα μήνυμα , είναι Ο(diam) και ο απαιτούμενος αριθμός μηνυμάτων είναι στην χειρότερη περίπτωση Ο(n).

Καθολικός/Κατανεμημένος υπολογισμός(Global Computation)

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

Παράδειγμα Έστω το εξής πρόβλημα: Σε δίκτυο όπου έχει κατασκευαστεί μία BFS δομή, κάθε διεργασία έχει μία ακέραια μεταβλητή k , των οποίων το άθροισμα θέλουμε να υπολογίσουμε. Αυτό μπορεί να γίνει εύκολα και αποδοτικά με την χρήση του BFS δέντρου ως εξής: Κάθε φύλλο στέλνει την μεταβλητή k στο γονέα του. Ο γονέας περιμένει μέχρι να λάβει όλες τις μεταβλητές k των παιδιών του, προσθέτει την δική του και με την σειρά του στέλνει το αποτέλεσμα στον δικό του γονέα. Έτσι στο τέλος της διαδικασίας το άθροισμα όλων των k έχει υπολογιστεί και βρίσκεται αποθηκευμένο στην ρίζα του BFS δέντρου. Ο υπολογισμός της συνάρτησης, αφού βασίζεται στο convergecast, χρειάζεται Ο(diam) γύρους και O(n) μηνύματα.

Εκλογή αρχηγού

Όλες οι διεργασίες ξεκινούν παράλληλα τον αλγόριθμο SynchBFS με ρίζα τον εαυτό τους. Κατόπιν κάθε διεργασία χρησιμοποιεί το BFS tree που κατασκεύασε, και ακολουθώντας διαδικασία αντίστοιχη με αυτήν που περιγράψαμε στην ενότητα Καθολικός/Κατανεμημένος Υπολογισμός, αποφασίζει αν είναι ο αρχηγός, δηλαδή αν έχει την μέγιστη ταυτότητα. Παρατηρούμε πως χρειαζόμαστε Ο(diam) γύρους και O(n*m) μηνύματα, ενώ ένα πλεονέκτημα του αλγορίθμου αυτού είναι πως οι διεργασίες δεν χρειάζονται καμία γνώση της διαμέτρου ή του αριθμού των διεργασιών του δικτύου.

Υπολογισμός διαμέτρου δικτύου

Μία πολύ σημαντική πληροφορία που μπορούμε να έχουμε για ένα δίκτυο και η οποία χρησιμοποιείται από πολλούς κατανεμημένους αλγορίθμους, κυρίως ως κριτήριο τερματισμού, είναι η διάμετρος του δικτύου. Η διάμετρος του δικτύου μπορεί να υπολογιστεί με την χρήση BFS δέντρων ως εξής: Όπως και πριν, όλες οι διεργασίες ξεκινούν παράλληλα τον αλγόριθμο SynchBFS με ρίζα τον εαυτό τους. Έπειτα, κάθε διεργασία χρησιμοποιεί το BFS tree που κατασκεύασε, για να βρει την μέγιστη απόστασή της από οποιαδήποτε άλλη διεργασία(η διάμετρος του BFS δέντρου που κατασκεύασε). Τέλος, κάθε διεργασία τρέχει μια συνάρτηση Καθολικού/Κατανεμημένου Υπολογισμού για να υπολογίσει την μέγιστη διάμετρο όλων των BFS δέντρων που έχουν κατασκευαστεί και άρα και την διάμετρο του δικτύου. Ο αλγόριθμος αυτός χρειάζεται Ο(diam) χρόνο και Ο(n*m) μηνύματα.

Δέντρα Αναζήτησης Κατά Βάθος

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

Αλγόριθμοι Κατασκευής Δέντρων Αναζήτησης Κατά Βάθος:

• DFS

Ελάχιστα Μονοπάτια

Έστω το ισχυρά συνεκτικό, κατευθυνόμενο δίκτυο G=(V,E), όπου e(i,j)≠e(j,i) . Σε κάθε ακμή e(i,j) αντιστοιχίζουμε ένα μη αρνητικό βάρος το οποίο συμβολίζουμε με weight(e) ή weight_i,j . Ορίζουμε ως βάρος του δικτύου το άθροισμα των βαρών κάθε ακμής του δικτύου.

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

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

Αλγόριθμοι Εύρεσης Ελάχιστων Μονοπατιών:

• BellmanFord

Maximal Independent Set

Το Maximal Independent Set πρόβλημα έχει να κάνει με την αναζήτηση ενός MIS (βέλτιστο ανεξάρτητο σετ) από κόμβους ενός μή κατευθυντικού γράφου. Ένα σετ από κόμβους λέγεται ανεξάρτητο όταν δεν περιέχει κανένα ζεύγος γειτονικών κόμβων, και ένα ανεξάρτητο σετ θεωρείται βέλτιστο όταν δεν μπορεί να αυξηθεί ώστε να δημιουργηθεί ένα μεγαλύτερο independent set με την πρόσθεση κόμβων. Αξίζει να σημειωθεί ότι σε έναν γράφο μπορεί να υπάρχουν πολλά διαφορετικά MIS. Δεν ζητούμε το μεγαλύτερο MIS του γράφου, αλλά οποιοδήποτε MIS μας αρκεί.

Έστω G=(V,E) ένας μή κατευθυντικός γράφος. Ένα σετ από κόμβους λέγεται independent όταν για όλους τους κόμβους . Ένα independent set I είναι και maximal όταν κανένα σετ I' που περιέχει το I δεν είναι independent. Ο στόχος μας είναι να υπολογίσουμε ένα MIS του G. Πιο συγκεκριμένα, κάθε process του οποίου το index είναι στο I τελικά πρέπει να έχει ως έξοδο winner, δηλαδή θα πρέπει να θέσει μια ειδική μεταβλητή status στη τιμή 'winner'. και όλες οι διεργασίες που δεν είναι στο I θα πρέπει να έχει έξοδο loser. Θεωρούμε ότι το n, δηλαδή ο αριθμός των κόμβων, είναι γνωστός σε όλες τις διεργασίες. Εναλλακτικά θα μπορούσαμε να θέσουμε ένα upper bound στο n. Δεν υποθέτουμε την ύπαρξη UIDs.

Αλγόριθμοι αναζήτησης MIS:

• LubyMIS

Υλοποίηση Αλγόριθμων Κατασκευής Κατανεμημένων Δομών

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

• command result_t init(uint16_t deviceID) - αρχικοποιεί τις εσωτερικές μεταβλητές του αλγόριθμου. Η παράμετρος deviceID υποδηλώνει την ταυτότητα που θα χρησιμοποιήσει η διεργασία κατα την κατασκευή του επικαλυπτικού δέντρου. Το command επιστρέφει πάντα SUCCESS.
• command result_t start() -- ξεκινά τη διαδικασία κατασκευής του επικαλυπτικού δένδρου. Επιστρέφει πάντα SUCCESS.
• command uint16_t getParentID() -- επιστρέφει την ταυτότητα του κόμβου-γονέα στο δένδρο, αλλιώς UNKNOWN_PARENT. Για την ρίζα του δέντρου επιστρέφει την ταυτότητα της διεργασίας.
• command uint8_t getStatus() -- επιστρέφει JOINED αν η διεργασία έχει συνδεθεί στο δέντρο, αλλιώς NOT_JOINED.
• command uint16_t getHeight() -- επιστρέφει το ύψος του κόμβου στο επικαλυπτικό δένδρο (0 αν είναι η ρίζα, αυξάνεται όσο πλησιάζουμε προς τα φύλλα).
• event result_t joined(uint16_t parentID, uint16\_t height) -- όταν ο κόμβος συνδεθεί στο επικαλυπτικό δέντρο, δημιουργείται ένα event όπου η παράμετρος parentID δηλώνει την ταυτότητα του κόμβου-γονέα στο δέντρο και η παράμετρος height δηλώνει το ύψος του κόμβου στο δένδρο. Το event επιστρέφει πάντα SUCCESS.

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

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

  async command uint16_t getParentID();

  async command uint8_t getStatus();

  async command uint16_t getHeight();

  async command result_t start();

  event result_t joined(uint16_t parentID, uint16_t height);
}

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

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

• Το κόκκινο Led ανάβει στη ρίζα όταν αρχίσει να εκτελείται ο αλγόριθμος. Όταν ολοκληρωθεί η εκτέλεση και τερματίσει ο αλγόριθμος, το πράσινο Led ανάβει.
• Όσο κατασκευάζεται το επικαλυπτικό δένδρο, στους υπόλοιπους κόμβους, το κίτρινο Led είναι αναμμένο. Όταν η διεργασία συνδεθεί στο δέντρο, το πράσινο Led ανάβει.

Εφόσον έχουμε να κάνουμε με ένα ασύγχρονο σύστημα, υπάρχει περίπτωση οι συσκευές να μη ξεκινήσουν ταυτόχρονα αλλά να υπάρχει μια χρονική καθυστέρηση. Για να εξασφαλίσουμε ότι όλες οι συσκευές του συστήματος είναι ενεργοποιημένες και συμμετέχουν στην κατασκευή του επικαλυπτικού δέντρου χρησιμοποιούμε ένα Timer για να καθυστερήσουμε την εκτέλεση του αλγόριθμου. Επομένως, η εκτέλεση του αλγόριθμου εκλογής αρχηγού και η ενημέρωση της ολοκλήρωσης του γίνεται με την υλοποίηση ενός task (το οποίο όμως καλεί τη SpanningTreeControl.start() μόνο στον κόμβο 0) και ενός event handler. Σύμφωνα με τα παραπάνω, ορίζουμε το module treeApp ως εξής:

module treeAppM {
  provides {
    interface StdControl;
  }
  uses {
    interface SpanningTreeControl;
    interface Leds;
    interface Timer;
  }
}
implementation {

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

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

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

  task void startTreeConstruction() {
    // Start the tree construction process
    if (TOS_LOCAL_ADDRESS == 0) {
      call SpanningTreeControl.start();
      call Leds.redOn();
      dbg(DBG_TEMP, "Tree construction process started.\n");
    }
      else {
      call Leds.yellowOn();
    }
  }

  event result_t SpanningTreeControl.joined(uint16_t parentID, uint16_t height) {

    dbg(DBG_TEMP, "Node %d joined the tree under Node %d with height %d.\n", 
                  TOS_LOCAL_ADDRESS, parentID, height);

    call Leds.yellowOff();
    call Leds.greenOn();

    return SUCCESS;
  }


  // Start the whole process
  event result_t Timer.fired() {
    post startTreeConstruction();
    return SUCCESS;
  }
}

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