Υλοποίηση και πειραματική αξιολόγηση ασύγχρονων κατανεμήμενων αλγορίθμων πληροφόρησης

Abstract

Τα κατανεμημένα συστήματα υπολογιστών διέρχονται μια περίοδο εκρηκτικής εξέλιξης. Οι ανάγκες για πολύπλοκους υπολογισμούς, που δεν μπορούν να διεκπεραιώσουν οι σειριακοί υπολογιστές, αυξάνονται συνεχώς. Το Διαδίκτυο έχει γίνει πλέον μια δημοφιλής πλατφόρμα παράλληλου υπολογισμού. Λόγω της μεγάλης αυτής ανάπτυξης προκύπτει το πρόβλημα της μετάδοσης της πληροφορίας σε τέτοια συστήματα, γνωστό και ως “gossip problem”. Δημιουργείται, δηλαδή, η ανάγκη για σχεδιασμό εύρωστων κατανεμημένων αλγορίθμων πληροφόρησης που να μεταδίδουν διάφορα δεδομένα στους κόμβους των συστημάτων αυτών αποτελεσματικά και αποδοτικά. Στην παρούσα Διατριβή Μάστερ παρουσιάζεται η υλοποίηση και η πειραματική αξιολόγηση δύο εύρωστων κατανεμημένων αλγορίθμων πληροφόρησης, οι οποίοι είναι προς το παρόν οι μοναδικοί που έχουν αναπτυχθεί και αυστηρότυπα αναλυθεί για ασύγχρονα κατανεμημένα συστήματα. Οι αλγόριθμοι αυτοί είναι ο EARS και ο SEARS, δύο εύρωστοι αλγόριθμοι οι οποίοι είναι αποδοτικοί ακόμα και στην παρουσία σφαλμάτων δικτύου. Αφού μελετήθηκαν αρκετά, οι εν λόγω αλγόριθμοι υλοποιήθηκαν στη γλώσσα προγραμματισμού JAVA με τη χρήση της YALPS, μιας βιβλιοθήκης που υποβοηθά την υλοποίηση κατανεμημένων αλγορίθμων και την προσομοίωση ή εκτέλεσή τους σε πραγματικό υπολογιστικό περιβάλλον. Οι αλγόριθμοι εφαρμόστηκαν πρώτα σε περιβάλλον προσομοίωσης με σκοπό να καταμετρηθούν οι επιδόσεις τους και ακολούθως στο PlanetLab, ένα πραγματικό Διαδικτυακό σύστημα, ως ισχυρό επιχείρημα για να επιβεβαιωθεί η πρακτικότητά τους. Η εμπειρική αξιολόγηση των αλγορίθμων οδήγησε στο γενικό συμπέρασμα ότι η πειραματική τους απόδοση συνάδει με τη θεωρητική αξιολόγησή τους. Και οι δύο αλγόριθμοι είναι εύρωστοι και πρακτικοί, με τον SEARS, μάλιστα, για μεγάλο αριθμό κόμβων να είναι ένας σταθερού χρόνου αλγόριθμος πληροφόρησης.