Σημειώσεις:Σύγχρονα Συστήματα:Μοντέλο

Από DistrSys

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

Πίνακας περιεχομένων 1 Σύγχρονα κατανεμημένα συστήματα 1.1 Τερματισμός 1.2 Μη κατευθυνόμενα γραφήματα 2 Σφάλματα 3 Εκτέλεση ενός κατανεμημένου αλγόριθμου 4 Μέτρηση πολυπλοκότητας

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

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

Σύγχρονα κατανεμημένα συστήματα

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

Θεωρούμε ότι οι μονάδες του συστήματος είναι συνδεδεμένες σε ένα σύγχρονο δίκτυο. Ορίζουμε το σύγχρονο δίκτυο ως ένα κατευθυνόμενο γράφημα G = (V,E)-, που αποτελείται απο ένα πεπερασμένο σύνολο V απο σημεία και μια συλλογή E από διατεταγμένα ζεύγη στοιχείων του V (E ⊆ [V]²). Τα στοιχεία του V είναι οι κορυφές (ή κόμβοι, ή σημεία) του γραφήματος G και απεικονίζουν τις υπολογιστικές μονάδες του συστήματος, τα στοιχεία του E είναι οι ακμές (ή γραμμές) και απεικονίζουν τα κανάλια επικοινωνίας του δικτύου. Συμβολίζουμε το σύνολο των κορυφών του G ως n = | V | (ονομάζεται βαθμός του G) και το σύνολο των ακμών ως m=|E|. Η ορολογία που χρησιμοποιούμε για να ορίσουμε ένα γράφημα βασίζεται στα [BB98], [RD00], [H95].

Μία κορυφή u είναι γειτνιάζουσα σε μία ακμή e αν , οπότε η e είναι μια ακμή της u. Οι δύο κορυφές που είναι γειτνιάζουσες σε μια ακμή ονομάζονται προσκείμενες στην ακμή ή άκρα και η e λέγεται ότι ενώνει τα άκρα της. Μια ακμή (x,y) μπορεί να γραφτεί και ως xy.

Μία κορυφή v ονομάζεται εξερχόμενη γειτονική της κορυφής u, εάν η (u,v) είναι μια ακμή του G, και η κορυφή u ονομάζεται εισερχόμενη γειτονική της κορυφής v. Συμβολίζουμε ως ={v|(u,v)∈E} όλες τις κορυφές που είναι εξερχόμενες γειτονικές της κορυφής u και αντίστοιχα ={v|(v,u)∈E} όλες τις κορυφές που είναι εισερχόμενες γειτονικές της u, δηλαδή τους γείτονες της μονάδας u προς (και αντίστοιχα, από) τις οποίες μπορεί να στείλει (και αντίστοιχα, λάβει) μήνυμα.

Ένας περίπατος του γραφήματος G είναι μια ακολουθία από εναλλασσόμενες κορυφές και ακμές που αρχίζει και τελειώνει με μια κορυφή, στην οποία οι ακμές είναι γειτνιάζουσες με τις δύο κορυφές που είναι αμέσως πριν και μετά. Ένας περίπατος που ενώνει το u₀- και το u_l, και μπορεί να γραφτεί και ως (οι ακμές προκύπτουν προφανώς από τις κορυφές) και καλείται περίπατος u₀ − u_l-. Ένας περίπατος u₀ − u_l- ονομάζεται κλειστός εάν u₀ = u_l-, αλλιώς ονομάζεται ανοιχτός. Τον καλούμε ίχνος εάν όλες οι ακμές είναι ξένες μεταξύ τους και τον καλούμε μονοπάτι εάν όλες οι κορυφές (και επομένως όλες οι ακμές) είναι ξένες μεταξύ τους. Ένας κλειστός περίπατος, λέμε ότι είναι κύκλος όταν οι l κορυφές είναι μοναδικές και .

Το μήκος του περιπάτου είναι l, δηλαδή ισούται με τον αριθμό των ακμών του. Η απόσταση d(u,v)- δύο κορυφών u και v στο G είναι το μήκος του συντομότερου μονοπατιού που τις ενώνει, αλλιώς . Μερικές φορές καλούμε το συντομότερο u − v μονοπάτι και ως γεωδαιτικό. Η διάμετρος diam(G)- ενός γραφήματος G είναι το μήκος του μακρύτερου γεωδαιτικού μονοπατιού.

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

Ο ορισμός μιας διεργασίας που εκτελείται απο την μονάδα (δηλ. κορυφή του γραφήματος) , είναι ο εξής:

• states_u- -- το σύνολο των καταστάσεων (όχι απαραίτητα πεπερασμένο)
• start_u- -- ένα μη κενό υποσύνολο των states_u- που ονομάζονται οι αρχικές καταστάσεις
• -- μία γεννήτρια εξερχόμενων μηνυμάτων
• , μία συνάρτηση αλλαγής κατάστασης

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

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

1^o Βήμα

1. Εφαρμογή της γεννήτριας μηνυμάτων στην τρέχουσα κατάσταση
2. Παραγωγή των μηνυμάτων που θα σταλούν σε όλους τους εξερχόμενους γείτονες
3. Αποστολή των μηνυμάτων μέσω των αντίστοιχων (εξερχόμενων) καναλιών.

2^o Βήμα

1. Εφαρμογή των εισερχόμενων μηνυμάτων στην τρέχουσα κατάσταση, σύμφωνα με την συνάρτηση αλλαγής κατάστασης -- μετάβαση στην επόμενη κατάσταση
2. Διαγραφή όλων των μηνυμάτων από τα (εισερχόμενα) κανάλια.

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

Τερματισμός

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

Μη κατευθυνόμενα γραφήματα

Ορισμένες φορές εξετάζουμε την εκτέλεση ενός κατανεμημένου αλγορίθμου σε ένα σύγχρονο σύστημα, στο οποίο το υποκείμενο γράφημα που απεικονίζει το δίκτυο είναι μη κατευθυνόμενο. Αυτή η περίπτωση καλύπτεται απο το μοντέλο που ορίσαμε για τα κατευθυνόμενα γραφήματα, αν θεωρήσουμε ένα κατευθυνόμενο γράφημα όπου για κάθε ακμή uv υπάρχει και η ακμή vu (δηλ. E ⊂ [V]²). Σε αυτή την περίπτωση συμβολίζουμε ως nbrs_u- όλες τις κορυφές που είναι γειτονικές της u..

Σφάλματα

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

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

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

Εκτέλεση ενός κατανεμημένου αλγόριθμου

Για να περιγράψουμε την εκτέλεση ενός κατανεμημένου αλγόριθμου, θεωρούμε μια ακολουθία μεταβάσεων της κατάστασης των διεργασιών του συστήματος με την αποστολή και παραλαβή μηνυμάτων. Συγκεκριμένα, συμβολίζουμε την κατάσταση του συστήματος την χρονική στιγμή (γύρο) i ως C_i- η οποία καθορίζεται από την κατάσταση κάθε διεργασίας. Στην συνέχεια, θεωρούμε ότι μια ανάθεση μηνυμάτων στα κανάλια του δικτύου κατά την χρονική στιγμή (γύρο) i, αποτελείται από την αποστολή ενός συνόλου μηνυμάτων M_i- (μπορεί να περιέχει και null μηνύματα) και αντίστοιχα η παραλαβή ενός συνόλου μηνυμάτων N_i-. Επομένως, η εκτέλεση ενός κατανεμημένου αλγορίθμου μπορεί να οριστεί ως μια άπειρη ακολουθία

Με άλλα λόγια, σε μια δεδομένη χρονική στιγμή i, κάθε διεργασία u του κατανεμημένου αλγόριθμου βρίσκεται σε κάποια κατάσταση που ανοίκει του states_u-, οπότε ο χαρακτηρισμός της κατάστασης όλων των διεργασιών καθορίζει την συνολική κατάσταση του συστήματος C_i-. Στην συνέχεια, οι διεργασίες εκτελούν έναν γύρο του αλγορίθμου, όπου πραγματοποιούνται ορισμένες αποστολές μηνυμάτων M_i- και στην συνέχεια κάποιες παραλαβές μηνυμάτων N_i-. Στην επόμενη χρονική στιγμή i + 1, το σύστημα λέμε ότι βρίσκεται στην κατάσταση C_{i + 1}-.

Μέτρηση πολυπλοκότητας

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

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

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

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