Ασφαλής Επικοινωνία Και Τοπολογική Γνώση

Abstract

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