Νέα μοντέλα για πρωτόκολλα πληθυσμών

Abstract

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).

Τα Ασύρματα Δίκτυα Αισθητήρων (ΑΔΑ) αποτελούν μία αρκετά πρόσφατη και πολλά υποσχόμενη νέα τεχνολογία που βρίσκει πληθώρα εφαρμογών. Λόγω της ευρύτατης εφαρμοσιμότητάς της και της προφανούς θέσης που βρίσκει στο σύγχρονο κατανεμημένο υπολογιστικό κόσμο, η επιστημονική τυπική θεμελίωση των νόμων που διέπουν αυτή τη νέα τεχνολογία καθίσταται απαραίτητη. Έτσι, έχουν προταθεί πολλά νέα υπολογιστικά μοντέλα για ΑΔΑ. Μία ειδική κατηγορία τέτοιων συστημάτων είναι τα Πρωτόκολλα Πληθυσμών (ΠΠ). Αυτά διέπονται από τρία ιδιαίτερα χαρακτηριστικά: Οι κόμβοι αίσθησης (πράκτορες) κινούνται παθητικά, δηλαδή δε μπορούν να ελέγξουν την κίνηση στην οποία υπόκεινται, η διαθέσιμη μνήμη κάθε κόμβου είναι πολύ περιορισμένη και οι πράκτορες αλληλεπιδρούν κατά ζεύγη. Έχει αποδειχθεί ότι ένα κατηγόρημα είναι υπολογίσιμο από το μοντέλο των ΠΠ εάν και μόνο εάν είναι ημιγραμμικό. Η κλάση των ημιγραμμικών κατηγορημάτων αποτελεί μία αρκετά μικρή κλάση. Στην παρούσα εργασία, βασικός μας στόχος είναι η επέκταση του μοντέλου των πρωτοκόλλων πληθυσμών με σκοπό το κέρδος σε υπολογιστική ισχύ. Πρώτα κάνουμε την παραδοχή ότι, πέρα των κόμβων αίσθησης, και οι ακμές του γραφήματος μπορούν να διατηρούν περιορισμένες καταστάσεις. Έτσι, σε ένα πλήρες γράφημα 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).