Σημειώσεις
Από DistrSys
Στη σελίδα αυτή θα αναρτηθούν οι σημειώσεις του μαθήματος.
Πίνακας περιεχομένων |
Εισαγωγή
Στο πρώτο κεφάλαιο εξετάζουμε τα βασικά χαρακτηριστικά ενός κατανεμημένου συστήματος, παρουσιάζουμε συνοπτικά τις κεντρικές ιδέες, εντοπίζουμε τις ιδιαίτερες σχεδιαστικές ανάγκες και θέτουμε την οπτική γωνία που θα ακολουθήσουμε στο μάθημα.
Σύγχρονα Συστήματα
Στο πρώτο μέρος του μαθήματος μελετάμε τα σύγχρονα συστήματα, αφετηρία της μελέτης των κατανεμημένων συστημάτων ως προς την περιγραφή, προγραμματισμό και ανάλυση τους. Υποθέτουμε ότι κάθε διεργασία εκτελεί τις εντολές ταυτόχρονα με τις υπόλοιπες, και η εκτέλεση κάθε εντολής γίνεται με συγχρονισμένα βήματα. Σε αυτό το μοντέλο, μελετάμε κάποια θεμελιώδη προβλήματα του κατανεμημένου υπολογισμού (π.χ. εκλογή αρχηγού, συναίνεση), περιγράφουμε χαρακτηριστικές αλγοριθμικές λύσεις και αναλύουμε την απόδοση του συστήματος.
Μοντέλο Σύγχρονων Συστημάτων
Στο δεύτερο κεφάλαιο, παρουσιάζουμε αναλυτικά το μοντέλο των σύγχρονων συστημάτων πάνω στο οποίο θα μελετήσουμε μια ομάδα κατανεμημένων αλγόριθμων. Υπάρχουν πολλά διαφορετικά μοντέλα επεξεργασίας κατανεμημένων πληροφοριών τα οποία χρησιμοποιούνται συχνά στη μελέτη των κατανεμημένων αλγορίθμων. Αν και η παραδοχή της συγχρονισμένης εκτέλεσης δεν αποτυπώνει πλήρως τις πραγματικές συνθήκες λειτουργίας ενός κατανεμημένου συστήματος, η μελέτη των σύγχρονων κατανεμημένων συστημάτων διευκολύνει την κατανόηση των προβλημάτων που καλούμαστε να αντιμετωπίσουμε κατά τον σχεδιασμό πραγματικών κατανεμημένων συστημάτων.
Εκλογή Αρχηγού
Στο τρίτο κεφάλαιο, μελετάμε το θεμελιώδες πρόβλημα ελέγχου: την εκλογή αρχηγού. Η εκλογή αρχηγού σε ένα δίκτυο απαιτεί την επιλογή μίας μοναδικής διεργασίας που θα βρίσκεται σε κατάσταση αρχηγού. Εξετάζουμε την περίπτωση όπου οι μονάδες του συστήματος είναι συνδεδεμένες μέσω ενός δικτύο δακτυλίου. Σε ένα τέτοιο δίκτυο, κάθε μονάδα γνωρίζει μόνο τις μονάδες με τις οποίες συνδέεται (δηλ. μονο δυο μονάδες). Επίσης εξετάζουμε την γενικότερη περίπτωση, όπου οι μονάδες είναι συνδεδεμένες μέσω ενός δικτύου οποιαδήποτε τοπολογίας.
Κατανεμημένες Δομές
Στο τέταρτο κεφάλαιο, εξετάζουμε αλγόριθμους για την κατασκευή και χρήση κατανεμημένων δομών για την αποδοτική αντιμετώπιση πολλών προβλημάτων που συναντά κανείς σε κατανεμημένα συστήματα. Μελετάμε αλγόριθμους για την κατασκευή επικαλυπτικών δέντρων (π.χ. αλγόριθμος SpanningTree). Η μετάδοση πληροφορίας με τη χρήση ενός τέτοιου δέντρου γίνεται γρηγορότερα και αποδοτικότερα. Εξετάζουμε δομές αναζήτησης κατά εύρος (π.χ. αλγόριθμος BFS)).
Συναίνεση υπό την Παρουσία Σφαλμάτων
Στο πέμπτο κεφάλαιο, εστιάζουμε σε περιπτώσεις όπου το δίκτυο αντιμετωπίζει σφάλματα επικοινωνίας κατα την μετάδοση δεδομένων, οι διεργασίες ενδέχεται να σταματήσουν την λειτουργίας τους και το σύστημα έχει βυζαντινή συμπεριφορά. Μελετάμε το πρόβλημα της Συναίνεσης και το πρόβλημα της Επικύρωσης.
Aσύγχρονα Συστήματα
Στο δεύτερο μέρος αναλύουμε την περίπτωση όπου τα επιμέρους συστήματα εκτελούν τις εργασίες τους με οποιαδήποτε, ακαθόριστη, σειρά και κάθε σύστημα εκτελεί τις εργασίες με οποιαδήποτε, ακαθόριστη, ταχύτητα σε σχέση με τα υπόλοιπα υποσυστήματα. Στο μοντέλο των ασύγχρονων συστημάτων δεν υπάρχουν παραδοχές ως προς τον ρυθμό που εκτελεί εντολές η κάθε διεργασία ή παραδίδει μηνύματα το κάθε κανάλι επικοινωνίας. Για την μοντελοποίηση αυτής της απροσδιόριστης χρονικά συμπεριφοράς χρησιμοποιούμε ένα αυτόματο εισόδου/εξόδου.
Σε αυτό το μοντέλο, επανερχόμαστε σε ορισμένα απο τα προβλήματα που εξετάσαμε στο πρώτο μέρος, όπως το πρόβλημα εκλογής αρχηγού και εξετάζουμε αλγοριθμικές λύσεις για το ασύγχρονο μοντέλο. Στην συνέχεια μελετάμε μια ομάδα νέων προβλημάτων τα οποία εμφανίζονται στο μοντέλο των ασύγχρονων συστημάτων (π.χ. αμοιβαίος αποκλεισμός, συγχρονισμός).
Προβλήματα και Αλγόριθμοι
Τα προβλήματα που παρουσιάζονται και οι αλγόριθμοι που τα επιλύουν συνοψίζονται ως εξής:
- Εκλογή Αρχηγού (Leader Election)
- LCR (ο αλγόριθμος των LeLann, Chang και Roberts), PetersonLE (ο αλγόριθμος του Peterson), HS (ο αλγόριθμος των Hirschberg και Sinclair), FloodMax (OptFloodMax), IR (ο αλγόριθμος των Itai και Rodeh), TimeSlice
- Συναίνεση (Consensus)
- SimpleConsensus, FloodSet, OptFloodSet
- Επικύρωση (Commit)
- TwoPhaseCommit, ThreePhaseCommit
- Συγχρονισμός (Synchronization)
- GlobSynch, LocSynch, SimpleSynch, ABD (ο αλγόριθμος των Tel και Leeuwen)
- Διάταξη Γεγονότων (Ordering of Events)
- LamportTime (ο αλγόριθμος του Lamport), WelchTime
- Αμοιβαίος Αποκλεισμός (Mutual Exclusion)
- Coordinator, LamportME (ο αλγόριθμος του Lamport), RAME (ο αλγόριθμος των Ricard και Agrawala), LeLannME (ο αλγόριθμος του LeLann), ChandyME (ο αλγόριθμος του Chandy), RaymondME (ο αλγόριθμος του Raymond)
- Δρομολόγηση (Routing)
