Σημειώσεις:Εισαγωγή

Από DistrSys

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

Πίνακας περιεχομένων 1 Σύγκριση με Παράλληλα Συστήματα 2 Απαιτήσεις Λειτουργικότητας 2.1 Ανταλλαγή πληροφοριών 2.2 Διαμοιρασμός πόρων 2.3 Αυξημένη αξιοπιστία 2.4 Αυξημένη απόδοση μέσω παραλληλίας 2.5 Απλοποίηση του σχεδιασμού μέσω της εξειδίκευσης 3 Σχεδιαστικές Προκλήσεις 3.1 Ετερογένεια 3.2 Ανοικτότητα 3.3 Ασφάλεια 3.4 Δυνατότητα κλιμάκωσης 3.5 Ανεκτικότητα σφαλμάτων 3.6 Παραλληλία 3.7 Διαφάνεια 4 Θεωρία Κατανεμημένου Υπολογισμού 4.1 Κατανεμημένοι αλγόριθμοι και σύγκριση με κεντρικοποιημένους αλγορίθμους

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

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

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

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

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

Σύγκριση με Παράλληλα Συστήματα

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

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

• Κλιμάκωση -- Τα κατανεμημένα συστήματα έχουν εκ των πραγμάτων μεγαλύτερη δυνατότητα κλιμάκωσης απο τα παράλληλα, καθώς η κοινή μνήμη παρουσιάζει μείωση της απόδοσης όσο ο αριθμός των επεξεργαστών αυξάνεται.
• Επεκτασιμότητα και ετερογένεια -- Ένα κατανεμημένο σύστημα είναι περισσότερο επεκτάσιμο εφόσον μπορεί να προστεθεί σε αυτό ή να αφαιρεθεί μια υπολογιστική μονάδα (δηλ. ένας επεξεργαστής) με μεγάλη ευκολία. Επιπλέον, αυτή η μονάδα μπορεί να έχει εντελώς διαφορετικά τεχνικά χαρακτηριστικά από τις υπάρχοντες υπολογιστικές μονάδες.
• Γεωγραφική δομή -- Οι οντότητες ενός κατανεμημένου συστήματος μπορεί να είναι γεωγραφικά απομακρυσμένες.
• Αξιοπιστία -- Τα κατανεμημένα συστήματα έχουν την δυνατότητα βελτίωσης της αξιοπιστίας καθώς η εμφάνιση σφαλμάτων σε ένα μεμονωμένο υπολογιστή δεν επηρεάζει την διαθεσιμότητα των υπολοίπων.
• Χαμηλό κόστος -- Η διαθεσιμότητα δικτύων μεγάλου εύρους και φθηνών σταθμών εργασίας ευνοεί επίσης τον κατανεμημένο υπολογισμό και για οικονομικούς λόγους.

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

Απαιτήσεις Λειτουργικότητας

Στην ενότητα αυτή παρουσιάζουμε τους λόγους για την επιλογή εγκατάστασης και χρήσης ενός κατανεμημένου συστήματος.

Ανταλλαγή πληροφοριών

Η συνεργασία μεταξύ των ανθρώπων που αποτελούν ένα οργανισμό δημιουργεί την ανάγκη ανταλλαγής δεδομένων στο σύστημα υπολογιστών που πλαισιώνει τον οργανισμό. Η χρήση ενός τοπικού δικτύου (LAN) έχει πλέον καθιερωθεί από όλους τους οργανισμούς, ανεξαρτήτου μεγέθους, για την ικανοποίηση της ανάγκης αυτής. Παράλληλα, για αντίστοιχους λόγους συνεργασίας μεταξύ ανθρώπων διαφορετικών οργανισμών, γίνεται χρήση των επονομαζομένων wide-area networks (WANs).

Καθώς οι συσκευές που διαθέτουν υπολογιστικές ικανότητες γίνονται ολοένα μικρότερες σε μέγεθος, είναι πλέον πιθανό κάποιος άνθρωπος να χρησιμοποιεί ταυτόχρονα περισσότερες από μία υπολογιστικές μονάδες οι οποίες συνεργάζονται μέσω ενός ασύρματου προσωπικού δικτύου (personal area network (PAN)).

Διαμοιρασμός πόρων

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

Αυξημένη αξιοπιστία

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

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

Αυξημένη απόδοση μέσω παραλληλίας

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

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

Απλοποίηση του σχεδιασμού μέσω της εξειδίκευσης

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

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

Σχεδιαστικές Προκλήσεις

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

Ετερογένεια

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

Χαρακτηριστικό παράδειγμα είναι το Διαδίκτυο που ενώ αποτελείται από πολλά διαφορετικά είδη δικτύων (π.χ. Ethernet, ATM κλπ.), όλοι οι υπολογιστές, ανεξαρτήτως του τύπου δικτύου μέσω του οποίου συνδέονται στο Διαδίκτυο, μπορούν να επικοινωνήσουν μεταξύ τους. Όλα τα σύγχρονα λειτουργικά συστήματα μπορούν να συνδεθούν στο Διαδίκτυο εφόσον υλοποιούν τα πρωτόκολλα του Διαδικτύου. Παρόλα αυτά, δεν προσφέρουν την ίδια διεπαφή προγραμματισμού για την ανάπτυξη εφαρμογών σε αυτά τα πρωτόκολλα. Για παράδειγμα οι κλήσεις για ανταλλαγή μηνυμάτων σε UNIX είναι διαφορετικές από τις αντίστοιχες κλήσεις σε Windows.

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

Ένας τρόπος αντιμετώπισης των παραπάνω προκλήσεων είναι η χρήση "λογισμικού ενδιάμεσου επιπέδου". Ο όρος ενδιάμεσο επίπεδο αναφέρεται σε ένα νέο επίπεδο λογισμικού που παρεμβάλλεται μεταξύ του λειτουργικού συστήματος και της εφαρμογής (βλ. Εικ. 1.3) και επιτρέπει την αφαίρεση της ετερογένειας των υποκείμενων δικτύων, υλικών, λειτουργικών συστημάτων και γλωσσών προγραμματισμού. Η CORBA είναι ένα τέτοιο παράδειγμα λογισμικού που ορίζει κοινους τύπους δεδομένων, διεπαφών και υπηρεσιών προκειμένου να αντιμετωπιστεί η ετερογένεια των επιμέρους τμημάτων ενός κατανεμημένου συστήματος, όπου οι ιδιαιτερότητες των υποκείμενων δικτύων αντιμετωπίζονται απο διαφορετικές υλοποιήσεις της CORBA, π.χ. ORBIX. Τα ενδιάμεσα λογισμικά εκτός από το να λύνουν προβλήματα ετερογένειας, παρέχουν ένα ομογενές υπολογιστικό μοντέλο το οποίο χρησιμοποιείται από προγραμματιστές για την ανάπτυξη διακομιστών και κατανεμημένων εφαρμογών. Τα πιθανά μοντέλα περιλαμβάνουν κλήση διαδικασίας απομακρυσμένου αντικειμένου, ειδοποίηση για κάποιο γεγονός εξ αποστάσεως, εξ αποστάσεως πρόσβαση SQL και κατανεμημένη επεξεργασία συναλλαγών.

Ένας άλλος τρόπος για την αντιμετώπιση της ετερογένειας είναι η χρήση "κινητού κώδικα". Ο όρος κινητός κώδικας αναφέρεται στον κώδικα που μπορεί να σταλεί από έναν υπολογιστή σε άλλον και να εκτελεστεί στον προορισμό του – για παράδειγμα τα Java applets. Η χρήση κινητού κώδικα προϋποθέτει ένα περιβάλλον εκτέλεσης, το οποίο είναι κατάλληλο για να εκτελείται απο όλους τους υπολογιστές. Στην περίπτωση των Java applets, ο κάθε υπολογιστής έχει την δυνατότητα δημιουργίας ενός εικονικού μηχανήματος Java το οποίο παρέχει τον τρόπο να κάνει τον κώδικα εκτελέσιμο από οποιοδήποτε υλικό.

Ανοικτότητα

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

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

Οι σχεδιαστές των πρωτοκόλλων του Διαδικτύου εισήγαγαν μία σειρά εγγράφων τα οποία ονόμασαν Requests for Comments, κάθε ένα από τα οποία είναι γνωστό με έναν αριθμό. Οι λεπτομέρειες των πρωτοκόλλων επικοινωνίας του Διαδικτύου εκδόθηκαν σε αυτή τη σειρά στις αρχές της δεκαετίας του 80, ακολουθήθηκαν δε από τις λεπτομέρειες για εφαρμογές που εκτελούνται πάνω σε αυτές, όπως η μεταβίβαση φακέλων, το ηλεκτρονικό ταχυδρομείο και το telnet στα μέσα της δεκαετίας του 80. Αυτή η τακτική συνεχίστηκε και αποτέλεσε τη βάση της τεχνικής κατοχύρωσης μέσω εγγράφων του Διαδικτύου. Αυτή η σειρά περιλαμβάνει συζητήσεις και λεπτομέρειες πρωτοκόλλων. Αντίγραφα μπορούν να αναζητηθούν στο www.ietf.org. Η έκδοση των αρχικών πρωτοκόλλων επικοινωνίας του Διαδικτύου έχει επιτρέψει τη δημιουργία μίας τεράστιας ποικιλίας συστημάτων και εφαρμογών στο Διαδίκτυο, για παράδειγμα τον Ιστό, ο οποίος είναι μια σχετικά πρόσφατη προσθήκη στις υπηρεσίες του Διαδικτύου. Τα RFC δεν είναι ο μόνος τρόπος έκδοσης. Για παράδειγμα, η CORBA έχει εκδοθεί μέσω μίας σειράς τεχνικών εγγράφων, συμπεροιλαμβανόμενης μίας πλήρους σειράς λεπτομερειών για τις διεπαφές και τις υπηρεσίες που παρέχονται (www.omg.org).

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

Ασφάλεια

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

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

Επομένως, μια πρόκληση είναι η αποστολή ευαίσθητων πληροφοριών μέσω μηνυμάτων με ασφαλή τρόπο. Αλλά η ασφάλεια δεν είναι μόνο θέμα απόκρυψης του περιεχομένου των μηνυμάτων – προϋποθέτει να είναι γνωστή η ακριβής ταυτότητα του χρήστη ή του μεσάζοντα εκ μέρους του οποίου στάλθηκε ένα μήνυμα. Μια δεύτερη πρόκληση είναι η σωστή πιστοποίηση ενός χρήστη ή ενός μεσάζοντα εξ αποστάσεως. Και οι δύο αυτές προκλήσεις μπορούν να αντιμετωπιστούν με την χρήση τεχνικών κρυπτογράφησης που έχουν αναπτυχθεί για το σκοπό αυτό.

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

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

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

Δυνατότητα κλιμάκωσης

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

• Έλεγχος του κόστους των φυσικών πόρων -- Όσο αυξάνεται η απαίτηση για ένα πόρο, θα πρέπει να είναι δυνατή η επέκταση του συστήματος, με λογικό κόστος, έτσι ώστε αυτή να ικανοποιείται. Για παράδειγμα η συχνότητα πρόσβασης σε ένα φάκελο στο τοπικό δίκτυο είναι πιθανό να αυξηθεί όσο αυξάνεται ο αριθμός των χρηστών. Επομένως, πρέπει να είναι δυνατή η εγκατάσταση πρόσθετων διαχειριστών αποθηκευτικών μονάδων για να αποφευχθεί κώλυμα στην απόδοση, το οποίο θα προέκυπτε αν ένας και μόνο διακομιστής αποθηκευτικών μονάδων είχε να διαχειριστεί όλα τα αιτήματα πρόσβασης σε ένα φάκελο. Γενικά, για να έχει ένα σύστημα με n χρήστες δυνατότητα κλιμάκωσης, η ποσότητα των φυσικών πόρων που απαιτούνται για να τους υποστηρίξει θα πρέπει να είναι το πολύ O(n) – δηλαδή, ανάλογο του n. Για παράδειγμα, αν ένας μόνο διακομιστής φακέλων μπορεί να υποστηρίξει 20 χρήστες, τότε ιδανικά δύο διακομιστές θα πρέπει να είναι ικανοί να υποστηρίξουν 40 χρήστες.

• Έλεγχος της απώλειας απόδοσης -- Έστω η διαχείριση ενός συνόλου πληροφοριών του οποίου το μέγεθος είναι ανάλογο με τον αριθμό των χρηστών ή των πόρων του συστήματος, για παράδειγμα ο πίνακας με την αντιστοιχία μεταξύ των ονομασιών domain των υπολογιστών και των διευθύνσεων στο Διαδίκτυο που διατηρείται από το σύστημα ονομασίας domain, το οποίο χρησιμοποιείται κυρίως για να αναζητηθούν ονόματα όπως το www.ceid.upatras.gr. Οι αλγόριθμοι που χρησιμοποιούν ιεραρχικές δομές έχουν μεγαλύτερη δυνατότητα κλιμάκωσης από αυτούς που χρησιμοποιούν γραμμικές δομές. Αλλά ακόμα και με τις ιεραρχικές δομές, μία αύξηση στο πλήθος εγγραφών θα έχει σαν αποτέλεσμα κάποια απώλεια στην απόδοση: ο χρόνος που απαιτείται για την πρόσβαση σε ιεραρχικά δομημένη πληροφορία είναι O(log n), όπου το n είναι το μέγεθος του συνόλου των πληροφοριών. Για να διαθέτει ένα σύστημα δυνατότητα κλιμάκωσης, η μέγιστη απώλεια απόδοσης δεν πρέπει να είναι χειρότερη από αυτό.

• Παρεμπόδιση εξάντλησης πόρων λογισμικού -- Ένα παράδειγμα πιθανής εξάντλησης των πόρων του συστήματος είναι η ονοματολογία που χρησιμοποιείται για τις διευθύνσεις των υπολογιστών στο Διαδίκτυο -- η χρήση 32 bits για το σκοπό αυτό θέτει ένα φυσικό όριο στις δυνατότητες του συστήματος. Η κατάλληλη λύση στο πρόβλημα αυτό είναι δύσκολη λόγου της αδυναμίας πρόβλεψης των απαιτήσεων των χρηστών με την πάροδο του χρόνου.

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

Ανεκτικότητα σφαλμάτων

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

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

• Ανίχνευση σφαλμάτων -- Ορισμένα σφάλματα μπορούν να ανιχνευθούν. Για παράδειγμα μπορούν να χρησιμοποιηθούν checksums για να ανιχνευθούν αλλοιωμένα δεδομένα σε ένα μήνυμα ή ένα αρχείο. Παρόλα αυτά είναι δύσκολο ή ακόμα και αδύνατον να ανιχνεύσεις άλλα σφάλματα όπως έναν κατεστραμμένο διακομιστή στο Διαδίκτυο. Η πρόκληση είναι να διαχειρίζεσαι τις αστοχίες που δεν μπορούν να ανιχνευθούν αλλά μπορούν να υποτεθούν.

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

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

• Ανοχή σφαλμάτων -- Οι περισσότερες υπηρεσίες στο Διαδίκτυο παρουσιάζουν σφάλματα – δεν θα ήταν πρακτικό να προσπαθήσουν να ανιχνεύσουν και να καλύψουν όλα τα πιθανά σφάλματα σε ένα τόσο μεγάλο δίκτυο που αποτελείται από τόσες πολλές μονάδες. Τα τερματικά μπορούν να σχεδιαστούν έτσι ώστε να ανέχονται τις αστοχίες, το οποίο με τη σειρά του υπονοεί ότι οι χειριστές τους ανέχονται τις αστοχίες. Για παράδειγμα, όταν ένας web browser δεν μπορεί να επικοινωνήσει με ένα web server, δεν αφήνει το χρήστη να περιμένει για πάντα ενώ προσπαθεί – τον ενημερώνει για το πρόβλημα αφήνοντας τον ελεύθερο να δοκιμάσει πάλι αργότερα.

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

• Πλεονασμός -- Οι υπηρεσίες μπορούν να κατασκευαστούν έτσι ώστε να ανέχονται τα σφάλματα με τη χρήση πλεον;άζοντων μονάδων όπως φαίνεται στα ακόλουθα παραδείγματα:
  • Θα πρέπει να υπάρχουν πάντα τουλάχιστον δύο διαφορετικά μονοπάτια επικοινωνίας μεταξύ δύο δρομολογητών στο Διαδίκτυο.
  • Στο σύστημα ονομασίας domain κάθε πίνακας ονομάτων αναπαράγεται σε τουλάχιστον δύο διαφορετικούς διακομιστές.
  • Μία βάση δεδομένων μπορεί να αναπαράγεται σε πολλαπλούς διακομιστές για να διασφαλιστεί ότι τα δεδομένα παραμένουν προσβάσιμα μετά τη παρουσία σφάλματος σε ένα από τους διακομιστές. Οι διακομιστές μπορούν να σχεδιαστούν έτσι ώστε να ανιχνεύουν σφάλματα στους όμοιους τους και σε τέτοια περίπτωση να κατευθύνονται τα τερματικά στους εν λειτουργία διακομιστές.

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

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

Παραλληλία

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

Μπορούμε να σχεδιάσουμε μία διαδικασία η οποία διαχειρίζεται ένα διαμοιραζόμενο πόρο έτσι ώστε να μπορεί να επεξεργαστεί μόνο ένα αίτημα κάθε φορά, όμως αυτή η προσέγγιση περιορίζει τις δυνατότητες κλιμάκωσης του συστήματος. Για το λόγο αυτό οι υπηρεσίες και οι εφαρμογές επιτρέπουν γενικά την ταυτόχρονη επεξεργασία πολλαπλών αιτημάτων. Για να γίνει αυτό περισσότερο σαφές, ας υποτεθεί ότι κάθε πόρος είναι ένα αντικείμενο το οποίο δέχεται αιτήσεις οι οποίες εκτελούνται ταυτόχρονα. Στην περίπτωση αυτή είναι πιθανό κλήσεις μίας συνιστώσας λογισμικού να εκτελούνται ταυτόχρονα με άλλες κλήσεις της ίδιας συνιστώσας λογισμικού, με κίνδυνο να παραχθούν λανθασμένα αποτελέσματα. Έστω δύο ταυτόχρονες προσφορές σε μία δημοπρασία: "Άρης: $53" και "Πάνος: $88" -- αν οι αντίστοιχες λειτουργίες διαπλέκονται χωρίς έλεγχο, τότε μπορεί να αποθηκευτούν ως "Πάνος: $53" και "Άρης: $88".

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

Διαφάνεια

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

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

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

Οι δύο σημαντικότερες διαφάνειες είναι οι διαφάνειες πρόσβασης και τοποθεσίας. Η παρουσία τους ή η απουσία τους επηρεάζει σημαντικά τη χρήση των κατανεμημένων πόρων. Συχνά αναφέρονται μαζί ως διαφάνεια δικτύου.

Θεωρία Κατανεμημένου Υπολογισμού

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

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

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

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

Λόγω των σύνθετων προβλημάτων που καλείται να αντιμετωπίσει ένα κατανεμημένο σύστημα, υπάρχει ενδιαφέρον για τον ορισμό αρνητικών αποτελεσμάτων, υπό την έννοια απόδειξης κατώτερων ορίων απόδοσης και απόλυτης αδυναμίας αντιμετώπισης ενός προβλήματος. Είναι αρκετά συνήθης πρακτική η απόδειξη αδυναμίας αντιμετώπισης ενός προβλήματος, σε ένα συγκεκριμένο μοντέλο κατανεμημένου υπολογισμού ή δίχως την παρουσία ενός συγκεκριμένου συνόλου πόρων. Τέτοιου είδους αποτελέσματα έχουν ιδιαίτερη σημασία, ανάλογη κατά κάποιον τρόπο με τη γνώση ότι ένα πρόβλημα είναι NP-πλήρες: μας υποδεικνύει τα σημεία που δεν μπορούμε να επέμβουμε πέρα απο ένα όριο. Παρόλα αυτά, σε ένα κατανεμημένο σύστημα υπάρχει μεγάλο περιθώριο ελιγμών: εάν ανακαλύψουμε ότι το πρόβλημα με το οποίο ασχολούμαστε δεν έχει λύση στο συγκεκριμένο μοντέλο που μελετάμε, μπορούμε να αλλοιώσουμε οριακά το μοντέλο ή ακόμα και να ορίσουμε ελάχιστα διαφορετικά το πρόβλημα, ούτως ώστε να μπορέσουμε να ξεπεράσουμε αυτή την αδυναμία.

Κατανεμημένοι αλγόριθμοι και σύγκριση με κεντρικοποιημένους αλγορίθμους

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

• Έλλειψη γνώσης της ολικής κατάστασης -- Σε ένα κεντρικοποιημένο αλγόριθμο οι αποφάσεις μπορούν να παρθούν παρατηρώντας την κατάσταση του συστήματος. Αν και συχνά, ολόκληρη η κατάσταση δεν είναι εύκολα προσβάσιμη με μία μόνο υπολογιστική λειτουργία, μια διεργασία μπορεί να επιθεωρήσει τις μεταβλητές μία προς μία, και να πάρει μία απόφαση αφού ληφθούν υπ’ όψιν όλες οι σχετικές πληροφορίες. Εάν κανένα δεδομένο δεν τροποποιείται μεταξύ της επιτήρησης και της απόφασης, τότε μπορούν να δοθούν εγγυήσεις για την ακεραιότητα του συστήματος.
  Οι μονάδες σε ένα κατανεμημένο σύστημα έχουν πρόσβαση μόνο στη δική τους κατάσταση και όχι στην ολική κατάσταση του συστήματος. Άρα, δεν είναι δυνατόν να παίρνουν αποφάσεις ελέγχου με βάση την ολική κατάσταση του συστήματος, π.χ. εάν οι αποφάσεις που λαμβάνει μια μονάδα απαιτούν γνώση για την κατάσταση άλλων μονάδων. Σε αντίθεση με τα κεντρικοποιημένα συστήματα, οι πληροφορίες που λαμβάνονται μπορεί να είναι παλιές, εφόσον η κατάσταση μιας άλλης μονάδας μπορεί να έχει αλλάξει μεταξύ της αποστολής της πληροφορίας και της απόφασης που λήφθηκε βασισμένη σε αυτή.
  Η κατάσταση του υποσυστήματος επικοινωνίας (π.χ. ποια μηνύματα είναι σε αποστολή σε μία δεδομένη χρονική στιγμή) δεν παρατηρείται απευθείας από τις μονάδες. Αυτή η πληροφορία μπορεί να εξαχθεί έμμεσα συγκρίνοντας τις πληροφορίες που αφορούν τα μηνύματα που έχουν ληφθεί και που έχουν αποσταλεί από τις μονάδες.

• Έλλειψη ολικού χρονοδιαγράμματος -- Τα γεγονότα τα οποία συντελούν στην εκτέλεση ενός κεντρικοποιημένου αλγόριθμου είναι εξολοκλήρου τοποθετημένα σε σειρά με φυσικό τρόπο που προκύπτει από την χρονική τους εμφάνιση. Για ένα ζευγάρι γεγονότων, το ένα προκύπτει νωρίτερα ή αργότερα από τον άλλο. Η χρονική σχέση των γεγονότων που προκύπτουν από την εκτέλεση ενός κατανεμημένου αλγόριθμου δεν είναι απόλυτη, για ορισμένα ζεύγη γεγονότων μπορεί να υπάρχει ένας λόγος που θα αποφασίσει ότι το ένα προκύπτει πριν το άλλο, ενώ για άλλα ζεύγη υπάρχει πιθανότητα κανένα από τα γεγονότα να μην προκύπτει πριν το άλλο.
  Ο αμοιβαίος αποκλεισμός μπορεί να επιτευχθεί σε ένα συγκεντρωτικό σύστημα όταν απαιτείται το εξής: αν η πρόσβαση της διαδικασίας p του πόρου αρχίσει αργότερα από την πρόσβαση της διαδικασίας q, τότε η πρόσβαση της διαδικασίας p πρέπει να αρχίσει αφού έχει τελειώσει η πρόσβαση της διαδικασίας q. Πράγματι, τέτοια γεγονότα (η αρχή και το τέλος της πρόσβασης των διαδικασιών p και q) μπορούν να τοποθετηθούν σε σειρά με βάση τη χρονική τους σχέση. Παρόλα αυτά σε ένα κατανεμημένο σύστημα μπορεί αυτό να μην είναι εφικτό. Οι διαδικασίες p και q μπορούν να αρχίσουν να έχουν πρόσβαση στον πόρο, ενώ κανενός η εκτέλεση δεν προηγείται χρονικά της άλλης.

• Παρουσία τυχαιότητας – Για μια κεντρικοποιημένη διεργασία μπορούμε να περιγράψουμε την εξέλιξή της εύκολα, δεδομένης μιας συγκεκριμένης αρχικής κατάστασης εισόδου. Δοθείσης μιας διεργασίας και συγκεκριμένης πληροφορίας εισόδου, η έκβαση της διεργασίας είναι εκ των προτέρων γνωστή. Αντίθετα, η εκτέλεση ενός κατανεμημένου συστήματος συχνά δεν μπορεί να είναι γνωστή εξ’ αρχής, εξαιτίας των πιθανών διαφορών στην ταχύτητα εκτέλεσης των διεργασιών από τις μονάδες του συστήματος.
  Ας εξετάσουμε την περίπτωση όπου μία διεργασία λαμβάνει μηνύματα από άλλες διεργασίες. Η διεργασία δεν μπορεί να αναστείλει την επεξεργασία των μηνυμάτων έως ότου ληφθούν όλα τα μηνύματα, γιατί δεν είναι γνωστό εκ των προτέρων πόσα μηνύματα θα φτάσουν. Άρα, κάθε μήνυμα πρέπει να επεξεργαστεί άμεσα, και η σειρά επεξεργασίας είναι η σειρά με την οποία φτάνει κάθε μήνυμα. Η σειρά με την οποία οι μονάδες στέλνουν τα αιτήματά τους μπορεί να είναι γνωστή, αλλά μια και δεν είναι γνωστές οι καθυστερήσεις στη μετάδοση, τα μηνύματα μπορεί να φτάσουν σε διαφορετική σειρά.

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