Μελέτη και εξομοίωση κατανεμημένων τεχνικών επίτευξης συμφωνίας (consensus) σε αδόμητα ασύρματα δίκτυα

Abstract

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

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

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

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

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

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