Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/12648
Title: Ασφαλής Επικοινωνία Και Τοπολογική Γνώση
Authors: Παναγιωτάκος Γεώργιος
Παγουρτζής Αριστείδης
Keywords: αξιόπιστη μετάδοση
βυζαντινοί στρατηγοί
τοπικά περιορισμένος αντίπαλος
γενικός αντί- παλος
τοπολογική γνώση
ad hoc δίκτυα
Issue Date: 15-Dec-2014
Abstract: Η αξιόπιστη μετάδοση είναι ένα από τα βασικά προβλήματα στα δίκτυα επικοινωνίας.Μελετάμε αυτό το πρόβλημα σε γενικά δίκτυα ενάντια σε Βυζαντινό αντίπαλο και σε σχέσημε την τοπολογική γνώση των παικτών. Θεωρούμαι ότι ο αντίπαλος περιγράφεται είτε απότο τοπικά περιορισμένο μοντέλο του Koo (2004) είτε από το μοντέλο γενικού αντιπάλουτων Hirt και Maurer (1997) και διερευνούμε την σχέση μεταξύ του επιπέδου γνώσης τηςτοπολογίας και της επιλυσιμότητας του προβλήματος.Βελτιώνουμε την τεχνική του τοπικού ζεύγους διαχωριστών των Pelc και Peleg (2005)έτσι ώστε να αποκτήσουμε αποτελέσματα μη επιλυσιμότητας για κάθε επίπεδο τοπολογικήςγνώσης και για κάθε τύπο αντιπάλου. Στην θετική πλευρά κατασκευάζουμε πρωτόκολλαπου ταιριάζουν σε αυτά τα όρια μη επιλυσιμότητας, και έτσι χαρακτηρίζουμε πλήρως τηνκλάση των γραφημάτων στα οποία η αξιόπιστη μετάδοση είναι δυνατή.Ανάμεσα στα άλλα, δείχνουμε ότι το πρωτόκολλο Certified Propagation Algorithm(CPA) του Koo είναι μοναδικό ενάντια σε τοπικά περιορισμένους αντιπάλους σε ad-hocδίκτυα, δηλαδή μπορεί να αντέξει όσο δυνατούς τοπολογικά περιορισμένους αντιπάλους όσοοποιοσδήποτε άλλος αλγόριθμος. Αυτό το αποτέλεσμα δίνει απάντηση και σε μια ανοιχτήερώτηση των Pelc και Peleg. Επίσης κατασκευάζουμε μια προσαρμογή του CPA ενάντιασε γενικούς αντιπάλους και δείχνουμε την μοναδικότητα του. Απ όσο γνωρίζουμε αυτόςείναι ο πρώτος βέλτιστος αλγόριθμος για αξιόπιστη μετάδοση σε ad-hoc δίκτυα ενάντια σεγενικούς αντιπάλους.
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/12648
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File SizeFormat 
DT2014-0354.pdf717.19 kBAdobe PDFView/Open


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