Αξιόπιστη επικοινωνία υπό συνθήκες περιορισμένης γνώσης

Abstract

As communication networks grow in size, they become increasingly vulnerable to component failures. These networks consist of numerous interacting entities (agents). Since distributed systems have become popular and widely used in contemporary networking, the provided solutions need to cope with erroneous and malicious components in the underlying communication network. Security and reliability issues that arise have been objects of extensive research in the fields of Secure Multiparty Computations and Distributed Computing. In our work we contribute to the realization of fundamental communication primitives (Reliable Broadcast and Reliable Message Transmission) in an adversarial distributed environment, by investigating the impact of the network structure and the agents' topology knowledge level on the achievability of these tasks. We consider a worst-case (Byzantine) adversary, which makes the agents misbehave arbitrarily,Initially, we consider the t-locally bounded adversary model, introduced in 2004 by Koo, where a fixed upper bound on the number of corruptions in each agent's neighborhood is imposed. We explore the tradeoff between the level of topology knowledge and the solvability of the problem by developing a versatile technique which allows us to obtain impossibility results for every level of topology knowledge. Checking the necessary conditions for the solvability of the problem proves to be NP-hard but along the way we obtain an efficient 2-approximation algorithm for the ad hoc case (where agents only know their local neighborhood). On the positive, we generalize the algorithmic idea behind the simple, yet powerful Certified Propagation Algorithm (CPA), also introduced by Koo in 2004, and propose algorithms, that match the obtained bounds (unique algorithms) in every case. Thus, we exactly characterize the classes of graphs in which reliable communication is possible with respect to topology knowledge. In order to achieve these we introduced the Partial Knowledge Model in which each agent knows a part of the network, namely a connected subgraph containing itself. As a part of the latter contribution, we manage to settle an open question of Pelc and Peleg (2005) in the affirmative, by showing that in ad hoc networks, CPA is unique, that is, it can tolerate as many local corruptions as any other Broadcast algorithm.Furthermore, we manage to generalize our results in the General Adversary model of Hirt and Maurer (1997), which subsumes earlier models by adapting our techniques and algorithms from the t-locally bounded model. Thus, we devise the first optimally resilient algorithms for Reliable Broadcast/Message transmission under restricted knowledge and general adversaries. We also study the efficiency of RMT protocols by introducing an algorithmic property which implies that a protocol scheme is as efficient as any other for a certain problem with respect to polynomial time. To obtain our latter results we employ, among others, a novel notion of joining operation on adversary structures, appropriate notions of separators in unreliable networks, and a self-reducibility property of the RMT problem.Finally, we study energy-efficient Broadcast in wireless networks, where simultaneous transmissions lead to signal interference which prevents message propagation. In particular, we examine the $k$-shot wireless network model, in which a bound k on the number of transmissions for every player is given. We prove a lower bound on the Broadcast time of any protocol.

Καθώς τα σύγχρονα δίκτυα επικοινωνιών αυξάνονται σε μέγεθος, γίνονται συνεχώς πιο ευάλωτα σε δυσλειτουργίες των συστατικών τους. Τα δίκτυα αυτά αποτελούνται από οντότητες (συμμετέχοντες ή παίκτες) που αλληλεπιδρούν μεταξύ τους για την επίτευξη κάποιου κοινού στόχου. Τα κατανεμημένα συστήματα χρησιμοποιούνται ευρέως στις σημερινές δικτυακές υποδομές, καθώς είναι ιδανικά για την μοντελοποίηση τέτοιων περιπτώσεων συνεργατικών υπολογισμών. Επομένως, οι παρεχόμενες λύσεις πρέπει να είναι σε θέση να αντιμετωπίσουν εσφαλμένες και κακόβουλες συμπεριφορές εκ μέρους των συμμετεχόντων. Τα ζητήματα ασφάλειας και αξιοπιστίας που προκύπτουν, αποτελούν αντικείμενο μελέτης στους τομείς των Ασφαλών Υπολογισμών πολλών Συμμετεχόντων και των Κατανεμημένων Υπολογισμών. Η παρούσα εργασία, συμβάλλει στην μελέτη θεμελιωδών αρχών επικοινωνίας (Αξιόπιστη Εκπομπή και Αξιόπιστη Μετάδοση Μηνύματος) σε μη αξιόπιστα κατανεμημένα συστήματα, με τη διερεύνηση των επιπτώσεων της δομής του δικτύου και της τοπολογικής γνώσης των συμμετεχόντων στον βαθμό που μπορούν αν επιτευχθούν αυτές οι βασικές εργασίες. Θεωρούμε την χειρότερη περίπτωση αντιπάλου (Βυζαντινός αντίπαλος), ο οποίος διαφθείρει μέρος των συμμετεχόντων και τους αναγκάζει να αποκλίνουν αυθαίρετα από τους προκαθορισμένους κανόνες. Αρχικά, θεωρούμε ότι το μοντέλο t-τοπικά περιορισμένου αντιπάλου, το οποίο εισήχθη το 2004 από Koo, όπου ο αριθμός των διεφθαρμένων παικτών στην γειτονιά κάθε παίκτη περιορίζεται από ένα άνω φράγμα. Διερευνούμε την σχέση μεταξύ του επιπέδου της τοπολογικής γνώσης και της επιλυσιμότητας του προβλήματος αναπτύσσοντας μιας ευέλικτη τεχνική που μας επιτρέπει την εξαγωγή αναγκαίων συνθηκών που καθιστούν το πρόβλημα επιλύσιμο, για κάθε επίπεδο γνώσης της τοπολογίας. Ο έλεγχος της ισχύος αυτών των συνθηκών αποδεικνύεται ότι είναι NP-δύσκολο πρόβλημα, αλλά στην πορεία προτείνουμε ένα αποδοτικό 2-προσεγγιστικό αλγόριθμο για την περίπτωση των δικτύων άγνωστης τοπολογίας (ad hoc). Ως προς την επίλυση του προβλήματος, γενικεύουμε την αλγοριθμική ιδέα στην οποία στηρίζεται ο απλός αλλά ιδιαίτερα χρήσιμος Αλγόριθμος Πιστοποιημένης Διάδοσης (CPA), που προτάθηκε από τον Koo to 2004, και σχεδιάζουμε αλγορίθμους οι οποίοι επιλύουν το πρόβλημα όποτε ισχύουν οι αναγκαίες συνθήκες (``μοναδικοί" αλγόριθμοι) σε κάθε περίπτωση τοπολογικής γνώσης. Έτσι, επιτυγχάνουμε τον ακριβή χαρακτηρισμό των γραφημάτων στα οποία είναι δυνατή η αξιόπιστη επικοινωνία σε σχέση με το επίπεδο γνώσης της τοπολογίας. Προκειμένου να επιτευχθούν τα παραπάνω, εισάγουμε το Μοντέλο Μερικής Γνώσης, στο οποίο κάθε παίκτης γνωρίζει ένα οποιοδήποτε τμήμα του δικτύου που αναπαρίσταται από ένα υπογράφημα. Στη μελέτη μας, καταφέρνουμε να απαντήσουμε στο ανοιχτό ερώτημα των Pelc και Peleg (2005) καταφατικά, αποδεικνύοντας την μοναδικότητα του CPA σε δίκτυα άγνωστης τοπολογίας, δηλαδή, ότι ο CPA μπορεί να ανεχθεί όσες τοπικές διαφθορές ανέχεται και οποιοσδήποτε άλλος αλγόριθμος.Επιπλέον, καταφέρνουμε να γενικεύσουμε τα αποτελέσματά μας στο μοντέλο Γενικού Αντιπάλου των Hirt και Maurer (1997), το οποίο αποτελεί γενίκευση όλων των γνωστών μοντέλων αντιπάλου, με την προσαρμογή των τεχνικών και αλγορίθμων μας από το μοντέλο t-τοπικά φραγμένου αντιπάλου. Έτσι, σχεδιάζουμε τους πρώτους αλγορίθμους βέλτιστης ανεκτικότητας, που πετυχαίνουν αξιόπιστη επικοινωνία υπό περιορισμένη τοπολογική γνώση και ύπαρξη γενικού αντιπάλου. Μελετάμε επίσης την αποδοτικότητα πρωτοκόλλων αξιόπιστης επικοινωνίας, εισάγοντας μια αλγοριθμική ιδιότητα που δηλώνει ότι ένα αλγοριθμικό σχήμα είναι όσο αποδοτικό όσο και οποιοδήποτε άλλο ως προς πολυωνυμικές παραμέτρους. Για την εξαγωγή των τελευταίων συμπερασμάτων, χρησιμοποιούμε, μεταξύ άλλων , μια νέα έννοια συνδυασμού γνώσης σχετικά με την δομή του αντιπάλου, κατάλληλες έννοιες διαχωριστών σε μη αξιόπιστα δίκτυα και μια ιδιότητα αυτο-αναγωγής του προβλήματος. Τέλος, μελετάμε την ενεργειακά αποδοτική εκπομπή σε ασύρματα δίκτυα, όπου ταυτόχρονες μεταδόσεις οδηγούν σε παρεμβολή σήματος η οποία αποτρέπει την διάδοση του μηνύματος. Συγκεκριμένα, εξετάζουμε το ασύρματο μοντέλο δικτύου k-μεταδόσεων, στο οποίο δίνεται ένα άνω φράγμα k στον αριθμό των μεταδόσεων του κάθε παίκτη. Σε αυτό το μοντέλο αποδεικνύουμε ένα κάτω φράγμα στο χρόνο που απαιτείται για το διαμοιρασμό του μηνύματος σε όλο το δίκτυο από οποιοδήποτε πρωτόκολλο.