Ασφαλής Επικοινωνία και Τοπολογική γνώση - Παναγιωτάκος, Γεώργιος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Λογικής και Επιστήμης Υπολογισμών, 2014)
Η αξιόπιστη μετάδοση είναι ένα από τα βασικά προβλήματα στα δίκτυα επικοινωνίας. Μελετάμε αυτό το πρόβλημα σε γενικά δίκτυα ενάντια σε Βυζαντινό αντίπαλο και σε σχέση με την τοπολογική γνώση των παικτών. Θεωρούμαι ότι ο αντίπαλος περιγράφεται είτε από το τοπικά περιορισμένο μοντέλο του Koo (2004) είτε από το μοντέλο γενικού αντιπάλου των Hirt και Maurer (1997) και διερευνούμε την σχέση μεταξύ του επιπέδου γνώσης της τοπολογίας και της επιλυσιμότητας του προβλήματος. Βελτιώνουμε την τεχνική του τοπικού ζεύγους διαχωριστών των Pelc και Peleg (2005) έτσι ώστε να αποκτήσουμε αποτελέσματα μη επιλυσιμότητας για κάθε επίπεδο τοπολογικής γνώσης και για κάθε τύπο αντιπάλου. Στην θετική πλευρά κατασκευάζουμε πρωτόκολλα που ταιριάζουν σε αυτά τα όρια μη επιλυσιμότητας, και έτσι χαρακτηρίζουμε πλήρως την κλάση των γραφημάτων στα οποία η αξιόπιστη μετάδοση είναι δυνατή. Ανάμεσα στα άλλα, δείχνουμε ότι το πρωτόκολλο Certified Propagation Algorithm (CPA) του Koo είναι μοναδικό ενάντια σε τοπικά περιορισμένους αντιπάλους σε ad-hoc δίκτυα, δηλαδή μπορεί να αντέξει όσο δυνατούς τοπολογικά περιορισμένους αντιπάλους όσο οποιοσδήποτε άλλος αλγόριθμος. Αυτό το αποτέλεσμα δίνει απάντηση και σε μια ανοιχτή ερώτηση των Pelc και Peleg. Επίσης κατασκευάζουμε μια προσαρμογή του CPA ενάντια σε γενικούς αντιπάλους και δείχνουμε την μοναδικότητα του. Απ ́ όσο γνωρίζουμε αυτός είναι ο πρώτος βέλτιστος αλγόριθμος για αξιόπιστη μετάδοση σε ad-hoc δίκτυα ενάντια σε γενικούς αντιπάλους.