Σημειώσεις:Σύγχρονα Συστήματα
Από DistrSys
Στο πρώτο μέρος του μαθήματος μελετάμε τα σύγχρονα συστήματα, αφετηρία της μελέτης των κατανεμημένων συστημάτων ως προς την περιγραφή, προγραμματισμό και ανάλυση τους. Υποθέτουμε ότι κάθε διεργασία εκτελεί τις εντολές ταυτόχρονα με τις υπόλοιπες, και η εκτέλεση κάθε εντολής γίνεται με συγχρονισμένα βήματα. Σε αυτό το μοντέλο, μελετάμε κάποια θεμελιώδη προβλήματα του κατανεμημένου υπολογισμού (π.χ. εκλογή αρχηγού, συναίνεση), περιγράφουμε χαρακτηριστικές αλγοριθμικές λύσεις και αναλύουμε την απόδοση του συστήματος.
Πίνακας περιεχομένων |
Μοντέλο Σύγχρονων Συστημάτων
Στο δεύτερο κεφάλαιο, παρουσιάζουμε αναλυτικά το μοντέλο των σύγχρονων συστημάτων πάνω στο οποίο θα μελετήσουμε μια ομάδα κατανεμημένων αλγόριθμων. Υπάρχουν πολλά διαφορετικά μοντέλα επεξεργασίας κατανεμημένων πληροφοριών τα οποία χρησιμοποιούνται συχνά στη μελέτη των κατανεμημένων αλγορίθμων. Αν και η παραδοχή της συγχρονισμένης εκτέλεσης δεν αποτυπώνει πλήρως τις πραγματικές συνθήκες λειτουργίας ενός κατανεμημένου συστήματος, η μελέτη των σύγχρονων κατανεμημένων συστημάτων διευκολύνει την κατανόηση των προβλημάτων που καλούμαστε να αντιμετωπίσουμε κατά τον σχεδιασμό πραγματικών κατανεμημένων συστημάτων.
Εκλογή Αρχηγού
Στο τρίτο κεφάλαιο, μελετάμε το θεμελιώδες πρόβλημα ελέγχου: την εκλογή αρχηγού. Η εκλογή αρχηγού σε ένα δίκτυο απαιτεί την επιλογή μίας μοναδικής διεργασίας που θα βρίσκεται σε κατάσταση αρχηγού. Εξετάζουμε την περίπτωση όπου οι μονάδες του συστήματος είναι συνδεδεμένες μέσω ενός δικτύο δακτυλίου. Σε ένα τέτοιο δίκτυο, κάθε μονάδα γνωρίζει μόνο τις μονάδες με τις οποίες συνδέεται (δηλ. μονο δυο μονάδες). Επίσης εξετάζουμε την γενικότερη περίπτωση, όπου οι μονάδες είναι συνδεδεμένες μέσω ενός δικτύου οποιαδήποτε τοπολογίας.
Κατανεμημένες Δομές
Στο τέταρτο κεφάλαιο, εξετάζουμε αλγόριθμους για την κατασκευή και χρήση κατανεμημένων δομών για την αποδοτική αντιμετώπιση πολλών προβλημάτων που συναντά κανείς σε κατανεμημένα συστήματα. Μελετάμε αλγόριθμους για την κατασκευή επικαλυπτικών δέντρων (π.χ. αλγόριθμος SpanningTree). Η μετάδοση πληροφορίας με τη χρήση ενός τέτοιου δέντρου γίνεται γρηγορότερα και αποδοτικότερα. Εξετάζουμε δομές αναζήτησης κατά εύρος (π.χ. αλγόριθμος BFS)).
Συναίνεση υπό την Παρουσία Σφαλμάτων
Στο πέμπτο κεφάλαιο, εστιάζουμε σε περιπτώσεις όπου το δίκτυο αντιμετωπίζει σφάλματα επικοινωνίας κατα την μετάδοση δεδομένων, οι διεργασίες ενδέχεται να σταματήσουν την λειτουργίας τους και το σύστημα έχει βυζαντινή συμπεριφορά. Μελετάμε το πρόβλημα της Συναίνεσης και το πρόβλημα της Επικύρωσης.
