Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/8506
Title: Ασφαλής Εκπομπή Σε Γενικά Και Ασύρματα Δίκτυα
Authors: Δημήτρης Σακαβάλας
Παγουρτζής Αριστείδης
Keywords: byzantine agreement
byzantine generals
broadcast
secure broadcast
byzantine adversary
distributed computing
Issue Date: 22-Oct-2013
Abstract: Τα περιβάλλοντα κατανεμημένων υπολογισμών αποτελούνται από πολυάριθμες ανεξάρτητες υπολογιστικές συσκευές που συνεργάζονται για την επίτευξη ενός κοινούστόχου. Για το σκοπό αυτό οι συσκευές αυτές διατάσσονται σε ένα δίκτυο επικοινωνίας. Για να είναι αποτελεσματικά σε κρίσιμες εφαρμογές (όπως συστήματα ελέγχουπτήσης και συστήματα ελέγχου σε πυρηνικούς σταθμούς παραγωγής ενέργειας), τα περιβάλλοντα κατανεμημένων υπολογισμών πρέπει να είναι σε θέση να αντιμετωπίσουν τη δυσλειτουργία κάποιων συσκευών. Για παράδειγμα, κάποια συσκευή μπορεί να αρνείται να παραδώσει αναγκαίες πληροφορίες σε άλλα μέρη του συστήματος. Ακόμα χειρότερα η συσκευή μπορεί να στέλνει αντικρουόμενες και ασυνεπείς πληροφορίες σε άλλα μέρη του συστήματος. Η τελευταία μορφή δυσλειτουργίας καλείται ενεργητική βλάβη (ή Βυζαντινή βλάβη). Μια βολική θεώρηση για την μελέτη των δυσλειτουργιών ορισμένων συσκευών του συστήματος, είναι η υπόθεση ύπαρξης ενός κακόβουλου αντιπάλου ο οποίος διαφθείρει κάποιους από τους συμμετέχοντες (συσκευές) του κατανεμημένου συστήματος. Είναι πλέον ευρέως αποδεκτό πως ένα αναπόσπαστο μέρος ενός κατανεμημένου συστήματος, σε περιβάλλον όπου υποθέτουμε την ύπαρξη ενός αντιπάλου, είναι ένας μηχανισμός για την επίτευξη ‘συμφωνίας’ μεταξύ των μη-διεφθαρμένων μερών του συστήματος. Σε έναν τέτοιο μηχανισμό όλοι οι μη-διεφθαρμένοι συμμετέχοντες πρέπει να είναι σε θέση να συμφωνήσουν σε κοινή τιμή χωρίς να ξέρουν ποια μέρη είναι διεφθαρμένα. Τα διάφορα προβλήματα συμφωνίας έχουν προσελκύσει την έρευνα από τις αρχέςτις δεκαετίας του 1980. Μία από τις σημαντικότερες παραλλαγές του προβλήματος είναι γνωστή στη βιβλιογραφία ως το πρόβλημα της Ασφαλούς Εκπομπής (ή το πρόβλημα των Βυζαντινών Στρατηγών). Στο πρόβλημα αυτό, θεωρούμε την ύπαρξη ενός καθορισμένου συμμετέχοντος, στην αρχική τιμή του οποίου θα πρέπει να συμφωνήσει κάθε μη-διεφθαρμένος συμμετέχον. Το πρόβλημα έχει μελετηθεί εκτενώςστο μοντέλο όπου είναι εξασφαλισμένη η διμερής επικοινωνία μεταξύ κάθε ζευγαριού συμμετεχόντων (πλήρες δίκτυο επικοινωνίας). Η περίπτωση των μη πλήρων δικτύωνεπικοινωνίας έχει μελετηθεί σε κάποιο βαθμό. Η έρευνα σε αυτήν την κατεύθυνση εισήγαγε νέες παραμέτρους για βελτιστοποίηση η οποίες αφορούν την τοπολογία τουδικτύου και σχετικά προβλήματα παραμένουν άλυτα. Επιπλέον, θεωρήθηκαν μοντέλα αντιπάλου με τοπολογικούς περιορισμούς στο πλαίσιο των οποίων μελετώνται τα σχετικά όρια τα οποία καθιστούν το πρόβλημα επιλύσιμο. Τέλος, το πρόβληματης Ασφαλούς Εκπομπής σε ασύρματα δίκτυα επικοινωνίας εξετάστηκε για πρώτη φορά το 2004, και έχει μελετηθεί κυρίως σε πολύ ειδικές τοπολογίες δικτύων, π.χ. δίκτυα πλέγματος. Η εξέταση του προβλήματος στα ασύρματα δίκτυα δημιουργεί νέες ανάγκες και προκλήσεις για εφαρμογές ασφαλών κατανεμημένων υπολογισμών. Αφενός, η δομή αυτών των δικτύων επιτρέπει στους διεφθαρμένους συμμετέχοντεςνα δημιουργούν παρεμβολές σήματος σε άλλους παραλήπτες (δέκτες) μηνυμάτων, το οποίο έχει ως αποτέλεσμα την επιδείνωση της ποιότητας επικοινωνίας. Αφετέρου, οισυμμετέχοντες δεσμεύονται να εκτελούν τοπικές εκπομπές, το οποίο διευκολύνει σε μεγάλο βαθμό την επίτευξη συμφωνίας. Ενα ακόμα σημαντικό ζήτημα, είναι η μελέτητοπικών κριτηρίων τα οποία μπορούν να χρησιμοποιηθούν από τους συμμετέχοντες για την επίτευξη Ασφαλούς Εκπομπής σε δίκτυα άγνωστης τοπολογίας.
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/8506
Appears in Collections:Μεταπτυχιακές Εργασίες - M.Sc. Theses

Files in This Item:
File SizeFormat 
MT2013-0001.pdf1.68 MBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.