73 σ.
(EL)
Εθνικό Μετσόβιο Πολυτεχνείο--Μεταπτυχιακή Εργασία. Διεπιστημονικό-Διατμηματικό Πρόγραμμα Μεταπτυχιακών Σπουδών (Δ.Π.Μ.Σ.) “Εφαρμοσμένες Μαθηματικές Επιστήμες”
(EL)
Δημήτρης Κ. Σακαβάλας
(EL)
Τα δίκτυα επικοινωνίας αποτελούνται από πολυάριθμες συσκευές που επικοινωνούν. Αυτές οι συσκευές συχνά επιθυμούν
να συνεργαστούν για να πετύχουν κάποιον κοινό στόχο, ακόμα και αν κάποιες από αυτές τις συσκευές είναι κακόβουλες/διεφθαρμένες.
Μία τέτοια θεώρηση δημιουργεί την ανάγκη για ασφαλείς κατανεμημένους υπολογισμούς. Είναι πλέον ευρέως αποδεκτό πως ένα αναπόσπαστο μέρος ενός κατανεμημένου συστήματος, είναι ένας μηχανισμός για την επίτευξη "συμφωνίας" μεταξύ όλων
των μή διεφθαρμένωνμερών του συστήματος. Μία από τις σημαντικότερες παραλλαγές του προβλήματος είναι γνωστή στη βιβλιογραφία
ως πρόβλημα της "Ασφαλούς Εκπομπής", όπου θεωρούμε την ύπαρξη ενός καθορισμένου συμμετέχοντος, στην αρχική τιμή του οποίου
θα πρέπει να συμφωνήσει κάθε μη διεφθαρμένος συμμετέχων.
Το πρόβλημα έχει μελετηθεί εκτενώς στο μοντέλο των πλήρων δικτύων. Στην περίπτωση των μη πλήρων δικτύων, η σχετική έρευνα εισήγαγε
νέες παραμέτρους προς βελτιστοποίηση, σχετικές με την τοπολογία του δικτύου. Επιπλέον θεωρήθηκαν μοντέλα αντιπάλου με τοπολογικούς περιορισμούς και σχετικά προβλήματα παραμένουν άλυτα. Τέλος, το πρόβλημα της Ασφαλούς Εκπομπής σε ασύρματα δίκτυα εξετάζεται σε αυτήν την εργασία. Αφενός, η δομή των ασύρματων δικτύων επιτρέπει στους διεφθαρμένους συμμετέχοντες να προκαλέσουν παρεμβολές σήματος σε άλλους παραλήπτες το οποίο εισάγει νέες προκλήσεις σχετικά με τη διαχείρισή τους. Αφετέρου οι συμμετέχοντες δεσμεύονται να εκτελέσουν τοπικές εκπομπές, το οποίο διευκολύνει σε μεγάλο βαθμό την επίτευξη συμφωνίας.
(EL)
Communication networks consist of numerous interacting entities. These entities often wish to
collaborate in order to achieve a certain task even if some of them are malicious/corrupted.
Such considerations put forth the need for secure distributed computing. It is widely accepted
that an integral part of a secure distributed system is a mechanism for reaching ``agreement''
between all non-corrupted parts of a system.
One of the major variations of the agreement problem is the "Secure Broadcast" problem,
where we assume the existence of a designated participant on whose input value every
non-corrupted participant should agree.
The problem has been extensively studied in the
standard model where the communication network is assumed to be complete. In the case
of incomplete communication networks, research has introduced new parameters for
optimization, relative to the network's topology. Moreover topologically restricted corruption models
have been considered, and related problems remain open so far. Finally secure Broadcast in
wireless networks is considered in this thesis. The structure of wireless networks allows the
corrupted entities to cause interference to other receivers, which brings up new challenges
regarding their manipulation. On the other hand, participants are committed
to perform local broadcasts, which greatly facilitates achieving agreement.
(EN)
National Technical University of Athens
