Στην εργασία αυτή επεκτείνουμε το μοντέλο των πρωτοκόλλων πληθυσμών που προτάθηκε από τους Angluin et al., ούτως ώστε να μοντελοποιήσουμε πιο ισχυρά δίκτυα αποτελούμενα από πολύ μικρά τεχνουργήματα περιορισμένων πόρων (πράκτορες), τα οποία είναι πιθανόν να ακολουθούν μη προβλέψιμη παθητική κίνηση. Οι πράκτορες αυτοί επικοινωνούν μόνο κατά ζεύγη σύμφωνα με τις επιλογές ενός εχθρικού δρομολογητή. Ένας κατευθυνόμενος (ή μη κατευθυνόμενος) γράφος επικοινωνίας αποτυπώνει την ακόλουθη πληροφορία: κάθε ακμή (u,υ) του γράφου υποδηλώνει ότι επιτρέπεται κατά τον υπολογισμό να συμβούν μία ή περισσότερες αλληλεπίδρασεις του u με τον υ στις οποίες ο u είναι ο μυητής και ο υ ο αποκρινόμενος. Το νέο χαρακτηριστικό του μοντέλου των πρωτοκόλλων πληθυσμών με διαμεσολαβητή το οποίο προτείνουμε στην παρούσα εργασία είναι η ύπαρξη ενός παθητικού παρόχου επικοινωνίας τον οποίο καλούμε διαμεσολαβητή. Ο διαμεσολαβητής είναι μία απλή βάση δεδομένων με δυνατότητες επικοινωνίας. Βασική δουλειά του είναι να διατηρεί τις επιτρεπόμενες αλληλεπιδράσεις σε κλάσεις επικοινωνίας, των οποίων ο αριθμός είναι σταθερός και ανεξάρτητος του μεγέθους του πληθυσμού. Για τον λόγο αυτό υποθέτουμε ότι κάθε πράκτορας του πληθυσμού έχει έναν μοναδικό προσδιοριστή (ίσως εργοστασιακό) τον οποίο ο ίδιος δεν μπορεί να γνωρίζει. Όταν δύο πράκτορες πρόκειται να αλληλεπιδράσουν αποστέλλουν τους μοναδικούς προσδιοριστές τους (ταυτότητες) στον διαμεσολαβητή ο οποίος τους κοινοποιεί την κλάση στην οποία ανήκει το μεταξύ τους κανάλι επικοινωνίας (δηλαδή, την κατάσταση του κατευθυνόμενου ή μη ζεύγους των προσδιοριστών τους) και οι πράκτορες ανανεώνουν την κατάστασή τους και την κατάσταση της μεταξύ τους ακμής βάσει μίας καθολικής συνάρτησης μετάβασης. Εάν η μεταξύ τους αλληλεπίδραση δεν επιτρέπεται ή, με άλλα λόγια, αν το ζεύγος αυτό δεν υπάρχει στη βάση δεδομένων του διαμεσολαβητή οι πράκτορες ενημερώνονται ότι θα πρέπει να ματαιώσουν την αλληλεπίδραση. Παρατηρούμε ότι με τον τρόπο αυτό αρχίζουμε να αποκτούμε κάποιον έλεγχο σχετικά με την ασφάλεια του δικτύου και επιπλέον μέσω του διαμεσολαβητή μπορούμε ανά πάσα στιγμή να γνωρίζουμε την τοπολογία του δικτύου. Ισοδύναμα, είναι σα να επιτρέπουμε στις ακμές του γράφου επικοινωνίας να διατηρούν καταστάσεις από ένα σύνολο καταστάσεων ακμών σταθερού πληθικού αριθμού. Ο εναλλακτικός αυτός τρόπος να δούμε το νέο μοντέλο έχει πολλά πλεονεκτήματα ως προς την τυπική μοντελοποίηση και τον σχεδιασμό πρωτοκόλλων, αφού μας επιτρέπει να παραβλέψουμε τις λεπτομέρειες υλοποίησης του διαμεσολαβητή. Επιπρόσθετα, επεκτείνουμε περαιτέρω το νέο μοντέλο επιτρέποντας στις ακμές να έχουν κόστη από ένα, επίσης, σταθερού πληθικού αριθμού σύνολο, τα οποία είναι μόνο προς ανάγνωση. Εν συνεχεία, επιτρέπουμε στους κανόνες μεταβάσεων των εκάστοτε πρωτοκόλλων να διαβάζουν τις καταστάσεις του ζεύγους πρακτόρων που αλληλεπιδρούν και την κατάσταση και το κόστος της ακμής μέσω της οποίας γίνεται η αλληλεπίδραση (αν, φυσικά, έχουμε ορίσει κόστη στο πρόβλημά μας) και να ανανεώνουν όλα αυτά τα στοιχεία πέραν από τα κόστη που είναι μόνο προς ανάγνωση. Παρατηρούμε, επομένως, ότι οι προδιαγραφές των πρωτοκόλλων του νέου μοντέλου συνεχίζουν, να είναι ανεξάρτητες του μεγέθους του πληθυσμού και συνεχίζουν να μην χρησιμοποιούν μοναδικούς προσδιοριστές, δηλαδή, το νέο μοντέλο διατηρεί τα χαρακτηριστικά της κλιμάκωσης, της ομοιομορφίας και της ανωνυμίας. Τα Πρωτόκολλα Πληθυσμών με Διαμεσολαβητή (Mediated Population Protocols - MPP) που προτείνουμε μπορούν να υπολογίσουν σταθερά ιδιότητες γράφων σχετικά με τον γράφο επικοινωνίας. Για να το δείξουμε αυτό παρουσιάζουμε πρωτόκολλα για το μεγιστοτικό ταίριασμα, την μεταβατική θήκη, τις ακμές ελαχίστου κόστους και το ελάχιστο μονοπάτι από τη ρίζα ως τα φύλλα ενός έξω-κατευθυνόμενου δέντρου και αποδεικνύουμε την ορθότητά τους. Εν συνεχεία, δείχνουμε ότι το μοντέλο των πρωτοκόλλων με διαμεσολαβητή αποτελεί ένα ισχυρότερο υπολογιστικά μοντέλο από το κλασικό μοντέλο των πρωτοκόλλων πληθυσμών. Πρώτα παρατηρούμε το προφανές, ότι, δηλαδή, το κλασικό μοντέλο των πρωτοκόλλων πληθυσμών είναι ειδική περίπτωση του νέου μοντέλου, άρα το νέο μοντέλο μπορεί να κάνει σίγουρα τουλάχιστον ότι και το κλασικό. Εν συνεχεία, παρουσιάζουμε ένα πρωτόκολλο με διαμεσολαβητή το οποίο υπολογίζει σταθερά το γινόμενο δύο θετικών ακέραιων στην περίπτωση που ο G (γράφος επικοινωνίας) είναι πλήρης κατευθυνόμενος και συνεκτικός. Τα κατηγορήματα που περιλαμβάνουν πολλαπλασιασμό δύο ακέραιων μεταβλητών δεν είναι ημιγραμμικά και έχει αποδειχθεί ότι τα κλασικά πρωτόκολλα πληθυσμών σε πλήρεις γράφους υπολογίζουν σταθερά μόνο ημιγραμμικά κατηγορήματα, άρα με τον τρόπο αυτό δείχνουμε ότι υπάρχει τουλάχιστον ένα κατηγόρημα που ενώ δεν υπολογίζεται σταθερά απ'' το βασικό μοντέλο υπολογίζεται σταθερά από το μοντέλο το οποίο προτείνουμε. Για τις ανάγκες της απόδειξης διατυπώνουμε και αποδεικνύουμε ένα γενικό Θεώρημα σχετικά με τη σύνθεση δύο πρωτοκόλλων πληθυσμών με διαμεσολαβητή, το ένα εκ των οποίων χρησιμοποιεί σταθεροποιούμενες εισόδους. Δείχνουμε, επίσης, ότι όλα τα κατηγορήματα που υπολογίζονται σταθερά απ'' το μοντέλο μας ανήκουν (μη ομοιόμορφα) στην κλάση NSPACE(m), όπου το m συμβολίζει το πλήθος των ακμών του γράφου επικοινωνίας. Τέλος, ορίζουμε τα πιθανοτικά πρωτόκολλα πληθυσμών με διαμεσολαβητή, στα οποία ο δρομολογητής επιλέγει σε κάθε βήμα την επόμενη αλληλεπίδραση ισοπίθανα μεταξύ των ακμών του γράφου επικοινωνίας και δείχνουμε ότι κάθε Peano κατηγόρημα που υπολογίζεται σταθερά από ένα πιθανοτικό MPP μπορεί να επαληθευτεί σε αιτιοκρατικό πολυωνυμικό χρόνο. / In this work we extend the population protocol model of Angluin et al., in order to model more powerful networks of very small resource limited artefacts (agents) that is possible to follow some unpredictable passive movement. These agents communicate in pairs according to the commands of an adversary scheduler. A directed (or undirected) communication graph encodes the following information: each edge (u,υ) denotes that during the computation it is possible for an interaction between u and υ to happen in which u is the initiator and υ the responder. The new characteristic of the proposed mediated population protocol model is the existance of a passive communication provider that we call mediator. The mediator is a simple database with communication capabilities. Its main purpose is to maintain the permissible interactions in communication classes, whose number is constant and independent of the population size. For this reason we assume that each agent has a unique identifier for whose existence the agent itself is not informed and thus cannot store it in its working memory. When two agents are about to interact they send their ids to the mediator. The mediator searches for that ordered pair in its database and if it exists in some communication class it sends back to the agents the state corresponding to that class. If this interaction is not permitted to the agents, or, in other words, if this specific pair does not exist in the database, the agents are informed to abord the interaction. Note that in this manner for the first time we obtain some control on the safety of the network and moreover the mediator provides us at any time with the network topology. Equivalently, we can model the mediator by communication links that are capable of keeping states from a edge state set of constant cardinality. This alternative way of thinking of the new model has many advantages concerning the formal modeling and the design of protocols, since it enables us to abstract away the implementation details of the mediator. Moreover, we extend further the new model by allowing the edges to keep readable only costs, whose values also belong to a constant size set. We then allow the protocol rules for pairwise interactions to modify the corresponding edge state by also taking into account the costs. Thus, our protocol descriptions are still independent of the population size and do not use agent ids, i.e. they preserve scalability, uniformity and anonymity. The proposed Mediated Population Protocols (MPP) can stably compute graph properties of the communication graph. We show this for the properties of maximal matchings (in undirected communication graphs), also for finding the transitive closure of directed graphs and for finding all edges of small cost. We demonstrate that our mediated protocols are stronger than the classical population protocols. First of all we notice an obvious fact: the classical model is a special case of the new model, that is, the new model can compute at least the same things with the classical one. We then present a mediated protocol that stably computes the product of two nonnegative integers in the case where G is complete directed and connected. Such kind of predicates are not semilinear and it has been proven that classical population protocols in complete graphs can compute precisely the semilinear predicates, thus in this manner we show that there is at least one predicate that our model computes and which the classical model cannot compute. To show this fact, we state and prove a general Theorem about the composition of two mediated population protocols, where the first one has stabilizing inputs. We also show that all predicates stably computable in our model are (non-uniformly) in the class NSPACE(m), where m is the number of edges of the communication graph. Finally, we define Randomized MPP and show that, any Peano predicate accepted by a Randomized MPP, can be verified in deterministic polynomial time.

Τα Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ) αποτελούν μία αρκετά πρόσφατη και πολλά υποσχόμενη νέα τεχνολογία που βρίσκει πληθώρα εφαρμογών. Λόγω της ευρύτατης εφαρμοσιμότητάς της και της προφανούς θέσης που βρίσκει στο σύγχρονο κατανεμημένο υπολογιστικό κόσμο, η επιστημονική τυπική θεμελίωση των νόμων που διέπουν αυτή τη νέα τεχνολογία καθίσταται απαραίτητη. Έτσι, έχουν προταθεί πολλά νέα υπολογιστικά μοντέλα για ΑΔΑ. Μία ειδική κατηγορία τέτοιων συστημάτων είναι τα Πρωτόκολλα Πληθυσμών (ΠΠ). Αυτά διέπονται από τρία ιδιαίτερα χαρακτηριστικά: Οι κόμβοι αίσθησης (πράκτορες) κινούνται παθητικά, δηλαδή δε μπορούν να ελέγξουν την κίνηση στην οποία υπόκεινται, η διαθέσιμη μνήμη κάθε κόμβου είναι πολύ περιορισμένη και οι πράκτορες αλληλεπιδρούν κατά ζεύγη. Έχει αποδειχθεί ότι ένα κατηγόρημα είναι υπολογίσιμο από το μοντέλο των ΠΠ εάν και μόνο εάν είναι ημιγραμμικό. Η κλάση των ημιγραμμικών κατηγορημάτων αποτελεί μία αρκετά μικρή κλάση. Στην παρούσα εργασία, βασικός μας στόχος είναι η επέκταση του μοντέλου των πρωτοκόλλων πληθυσμών με σκοπό το κέρδος σε υπολογιστική ισχύ. Πρώτα κάνουμε την παραδοχή ότι, πέρα των κόμβων αίσθησης, και οι ακμές του γραφήματος μπορούν να διατηρούν περιορισμένες καταστάσεις. Έτσι, σε ένα πλήρες γράφημα n κόμβων είναι σα να έχουμε προσθέσει Ο(n^2) επιπλέον θέσεις μνήμης οι οποίες διαβάζονται και γράφονται μόνο από τα άκρα της αντίστοιχης ακμής. Αποδεικνύουμε ότι το νέο μοντέλο, το οποίο καλούμε μοντέλο Πρωτοκόλλων Πληθυσμών με Διαμεσολαβητή, μπορεί να λειτουργήσει ως μία κατανεμημένη ανταιτιοκρατική μηχανή Turing (ΜΤ) που χρησιμοποιεί όλη τη διαθέσιμη μνήμη. Η μόνη διαφορά από μία συνήθη ΜΤ είναι ότι η συγκεκριμένη μηχανή υπολογίζει μόνο συμμετρικές γλώσσες. Πιο τυπικά, δείχνουμε ότι ένα κατηγόρημα είναι υπολογίσιμο από το νέο μοντέλο εάν και μόνο εάν είναι συμμετρικό και ανήκει στην NSPACE(n^2). Επιπλέον, μελετάμε και τη δυνατότητα του νέου μοντέλου να διαγιγνώσκει γλώσσες γραφημάτων (για γενικά γραφήματα). Εν συνεχεία, αγνοούμε τις καταστάσεις των ακμών και δίνουμε μία νέα βελτίωση και πάλι απευθείας απ' το μοντέλο των ΠΠ. Η υπόθεση που κάνουμε τώρα είναι ότι οι πράκτορες είναι πολυταινιακές ΜΤ με άπειρη μνήμη, που μπορούν τόσο να εκτελούν εσωτερικό υπολογισμό όσο και να αλληλεπιδρούν με άλλους πράκτορες και ορίζουμε χωρικά φραγμένους υπολογισμούς. Καλούμε το νέο αυτό μοντέλο, μοντέλο Παθητικά κινούμενων Μηχανών. Αποδεικνύουμε ότι αν χρησιμοποιείται σε κάθε πράκτορα μνήμη το πολύ f(n) για f(n)=Ω(log n) τότε ένα κατηγόρημα είναι υπολογίσιμο από το νέο μοντέλο εάν και μόνο εάν είναι συμμετρικό και ανήκει στην NSPACE(nf(n)). Δείχνουμε επίσης ότι αυτό δεν ισχύει για f(n)=o(log n). Βασιζόμενοι σε αυτά, δείχνουμε ότι για f(n)=Ω(log n) υπάρχει μία χωρική ιεραρχία ακριβώς όπως και για τις συνήθεις (συμμετρικές) ΜΤ. Δείχνουμε επίσης ότι αυτό δεν ισχύει για f(n)=o(loglog n), καθώς στην τελευταία περίπτωση η αντίστοιχη κλάση καταρρέει μέσα στην κλάση των ημιγραμμικών κατηγορημάτων, και τέλος ότι για f(n)=Ω(loglog n) η κλάση γίνεται αυστηρά μεγαλύτερη των ημιγραμμικών κατηγορημάτων. Αφήνουμε ανοικτό το πρόβλημα του τι ακριβώς συμβαίνει για χωρικά φράγματα f(n) τέτοια ώστε f(n)=Ω(loglog n) και f(n)=o(log n). / Wireless Sensor Networks (WSNs) constitute a recent and promising new technology that is widely applicable. Due to the applicability of this technology and its obvious importance for the modern distributed computational world, the formal scientific foundation of its inherent laws becomes essential. As a result, many new computational models for WSNs have been proposed. Population Protocols (PPs) are a special category of such systems. These are mainly identified by three distinctive characteristics: the sensor nodes (agents) move passively, that is, they cannot control the underlying mobility pattern, the available memory to each agent is restricted, and the agents interact in pairs. It has been proven that a predicate is computable by the PP model iff it is semilinear. The class of semilinear predicates is a fairly small class. In this work, our basic goal is to enhance the PP model in order to improve the computational power. We first make the assumption that not only the nodes but also the edges of the communication graph can store restricted states. In a complete graph of n nodes it is like having added O(n^2) additional memory cells which are only read and written by the endpoints of the corresponding edge. We prove that the new model, called Mediated Population Protocol model, can operate as a distributed nondeterministic Turing machine (TM) that uses all the available memory. The only difference from a usual TM is that this one computes only symmetric languages. More formally, we establish that a predicate is computable by the new model iff it is symmetric and belongs to NSPACE(n^2). Moreover, we study the ability of the new model to decide graph languages (for general graphs). The next step is to ignore the states of the edges and provide another enhancement straight away from the PP model. The assumption now is that the agents are multitape TMs equipped with infinite memory, that can perform internal computation and interact with other agents, and we define space-bounded computations. We call this the Passively mobile Machines model. We prove that if each agent uses at most f(n) memory for f(n)=Ω(log n) then a predicate is computable iff it is symmetric and belongs to NSPACE(nf(n)). We also show that this is not the case for f(n)=o(log n). Based on these, we show that for f(n)=Ω(log n) there exists a space hierarchy like the one for classical symmetric TMs. We also show that the latter is not the case for f(n)=o(loglog n), since here the corresponding class collapses in the class of semilinear predicates and finally that for f(n)=Ω(loglog n) the class becomes a proper superset of semilinear predicates. We leave open the problem of characterizing the classes for f(n)=Ω(loglog n) and f(n)=o(log n).