Solving Fundamental Problems in Hostile Networks

Abstract

In this thesis we study three fundamental problems in hostile network environments. Our work lies in the area of Theoretical Computer Science and in particular in the area of Distributed Computing. We design distributed algorithms and we prove their correctness and computational complexity for the following problems. We study how identical mobile agents that move autonomously in a network and have only local information about the environment, can gather at a node of a network despite the presence of a hostile mobile agent which may prevent agents from visiting a node of the network. We also study how a number of agents that move autonomously and have only local information about the environment, might collectively decontaminate a network in which there is a virus capable of infecting an area of the network. Finally, we study how mobile agents that move autonomously in a network can learn a message initially carried by only one of the agents despite the fact that the agents cannot communicate from a distance, cannot leave messages at nodes of the network and many links of the network might unpredictably fail at any time. The above problems are often needed to be solved as an early step in order to solve other problems in distributed environments. Some of those problems have been previously studied either in safe environments or when static hostile entities are present. Here we investigate more general models in which either hostile mobile agents exist in the network, or a hostile behaviour can spread at the nodes of the network, or many unpredictable faults can occur in the network. We prove lower bounds on the number of mobile agents which are necessary in order to solve the problems and design optimal algorithms that meet those lower bounds. We show how those three important problems can be solved fast in severe hostile environments by autonomous mobile agents having very limited resources (e.g., very limited memory and no initial knowledge about the environment) and capabilities (e.g., no communication from a distance and no sensory abilities). Since in most cases our models are very weak, we hope that our techniques can be extended to handle different problems and systematically increase our knowledge in extremely malicious environments where the hostile behaviour can affect large and sometimes distant areas of the environment.

Σε αυτή τη διατριβή μελετάμε τρία βασικά προβλήματα σε περιβάλλοντα εχθρικών δικτύων. Το έργο μας βρίσκεται στον τομέα της Θεωρητικής Πληροφορικής και ειδικότερα στον τομέα των Κατανεμημένων Υπολογισμών. Σχεδιάζουμε κατανεμημένους αλγόριθμους και αποδεικνύουμε την ορθότητα και την υπολογιστική πολυπλοκότητά τους για τα ακόλουθα προβλήματα. Μελετάμε πώς πανομοιότυποι πράκτορες που κινούνται αυτόνομα σε ένα δίκτυο και έχουν μόνο τοπικές πληροφορίες για το περιβάλλον, μπορούν να συγκεντρωθούν σε έναν κόμβο ενός δικτύου παρά την παρουσία ενός εχθρικού κινητού πράκτορα που μπορεί να εμποδίσει τους πράκτορες να επισκεφθούν έναν κόμβο του δικτύου. Μελετάμε επίσης πώς ένας αριθμός πρακτόρων που κινούνται αυτόνομα και έχουν μόνο τοπικές πληροφορίες σχετικά με το περιβάλλον, ενδέχεται να καθαρίσουν συλλογικά ένα δίκτυο στο οποίο υπάρχει ένας ιός ικανός να μολύνει μια περιοχή του δικτύου. Τέλος, μελετάμε πώς πράκτορες που κινούνται αυτόνομα σε ένα δίκτυο μπορούν να μάθουν ένα μήνυμα που αρχικά το γνωρίζει μόνο ένας πράκτορας, παρά το γεγονός ότι οι πράκτορες δεν μπορούν να επικοινωνήσουν από απόσταση, δεν μπορούν να αφήσουν μηνύματα σε κόμβους του δικτύου και η οποιαδήποτε ακμή του δικτύου ενδέχεται να αποτύχει απρόβλεπτα ανά πάσα στιγμή. Τα παραπάνω προβλήματα συχνά χρειάζεται να επιλυθούν ως πρώιμο βήμα για την επίλυση άλλων προβλημάτων σε κατανεμημένα περιβάλλοντα. Μερικά από αυτά τα προβλήματα έχουν μελετηθεί προηγουμένως είτε σε ασφαλή περιβάλλοντα ή όταν υπάρχουν στατικές εχθρικές οντότητες. Εδώ διερευνούμε πιο γενικά μοντέλα στα οποία είτε υπάρχουν στο δίκτυο εχθρικοί κινητοί πράκτορες, είτε μια εχθρική συμπεριφορά μπορεί να εξαπλωθεί στους κόμβους του δικτύου ή πολλά απρόβλεπτα σφάλματα μπορούν να προκύψουν στο δίκτυο. Αποδεικνύουμε κάτω φράγματα στον αριθμό των κινητών πρακτόρων που είναι απαραίτητοι για την επίλυση των προβλημάτων και σχεδιάζουμε βέλτιστους αλγόριθμους που ικανοποιούν τα κάτω φράγματα. Δείχνουμε πώς αυτά τα τρία σημαντικά προβλήματα μπορούν να επιλυθούν αποδοτικά σε πολύ εχθρικά περιβάλλοντα από αυτόνομους κινητούς πράκτορες που έχουν πολύ περιορισμένους πόρους (π.χ. πολύ λίγη μνήμη και χωρίς αρχικές γνώσεις για το περιβάλλον) και δυνατότητες (π.χ., χωρίς επικοινωνία από απόσταση και χωρίς αισθητηριακές ικανότητες). Επειδή στις περισσότερες περιπτώσεις τα μοντέλα μας είναι πολύ αδύναμα, ελπίζουμε ότι οι τεχνικές μας μπορούν να επεκταθούν για να χειριστούν διαφορετικά προβλήματα και να αυξήσουν συστηματικά τις γνώσεις μας σε εξαιρετικά κακόβουλα περιβάλλοντα όπου η εχθρική συμπεριφορά μπορεί να επηρεάσει μεγάλες και μερικές φορές απομακρυσμένες περιοχές του περιβάλλοντος.