Πρωτόκολλα πληθυσμών

• Κύριος συγγραφέας: Μιχαήλ, Όθων
• Άλλοι συγγραφείς: Σπυράκης, Παύλος
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2009
• Θέματα: Πρωτόκολλα πληθυσμών; Πράκτορες πεπερασμένων καταστάσεων; Διάχυτος υπολογισμός; Διακοπτόμενη επικοινωνία; Population protocols; Finite-state agents; Diffuse computation; Intermittent communication; 006.3

Στην εργασία αυτή επεκτείνουμε το μοντέλο των πρωτοκόλλων πληθυσμών που προτάθηκε από τους Angluin et al., ούτως ώστε να μοντελοποιήσουμε πιο ισχυρά δίκτυα αποτελούμενα από πολύ μικρά τεχνουργήματα περιορισμένων πόρων (πράκτορες), τα οποία είναι πιθανόν να ακολουθούν μη προβλέψιμη παθητική κίνηση. Οι πράκτορες αυτοί επικοινωνούν μόνο κατά ζεύγη σύμφωνα με τις επιλογές ενός εχθρικού δρομολογητή. Ένας κατευθυνόμενος (ή μη κατευθυνόμενος) γράφος επικοινωνίας αποτυπώνει την ακόλουθη πληροφορία: κάθε ακμή (u,υ) του γράφου υποδηλώνει ότι επιτρέπεται κατά τον υπολογισμό να συμβούν μία ή περισσότερες αλληλεπίδρασεις του u με τον υ στις οποίες ο u είναι ο μυητής και ο υ ο αποκρινόμενος. Το νέο χαρακτηριστικό του μοντέλου των πρωτοκόλλων πληθυσμών με διαμεσολαβητή το οποίο προτείνουμε στην παρούσα εργασία είναι η ύπαρξη ενός παθητικού παρόχου επικοινωνίας τον οποίο καλούμε διαμεσολαβητή. Ο διαμεσολαβητής είναι μία απλή βάση δεδομένων με δυνατότητες επικοινωνίας. Βασική δουλειά του είναι να διατηρεί τις επιτρεπόμενες αλληλεπιδράσεις σε κλάσεις επικοινωνίας, των οποίων ο αριθμός είναι σταθερός και ανεξάρτητος του μεγέθους του πληθυσμού. Για τον λόγο αυτό υποθέτουμε ότι κάθε πράκτορας του πληθυσμού έχει έναν μοναδικό προσδιοριστή (ίσως εργοστασιακό) τον οποίο ο ίδιος δεν μπορεί να γνωρίζει. Όταν δύο πράκτορες πρόκειται να αλληλεπιδράσουν αποστέλλουν τους μοναδικούς προσδιοριστές τους (ταυτότητες) στον διαμεσολαβητή ο οποίος τους κοινοποιεί την κλάση στην οποία ανήκει το μεταξύ τους κανάλι επικοινωνίας (δηλαδή, την κατάσταση του κατευθυνόμενου ή μη ζεύγους των προσδιοριστών τους) και οι πράκτορες ανανεώνουν την κατάστασή τους και την κατάσταση της μεταξύ τους ακμής βάσει μίας καθολικής συνάρτησης μετάβασης. Εάν η μεταξύ τους αλληλεπίδραση δεν επιτρέπεται ή, με άλλα λόγια, αν το ζεύγος αυτό δεν υπάρχει στη βάση δεδομένων του διαμεσολαβητή οι πράκτορες ενημερώνονται ότι θα πρέπει να ματαιώσουν την αλληλεπίδραση. Παρατηρούμε ότι με τον τρόπο αυτό αρχίζουμε να αποκτούμε κάποιον έλεγχο σχετικά με την ασφάλεια του δικτύου και επιπλέον μέσω του διαμεσολαβητή μπορούμε ανά πάσα στιγμή να γνωρίζουμε την τοπολογία του δικτύου. Ισοδύναμα, είναι σα να επιτρέπουμε στις ακμές του γράφου επικοινωνίας να διατηρούν καταστάσεις από ένα σύνολο καταστάσεων ακμών σταθερού πληθικού αριθμού. Ο εναλλακτικός αυτός τρόπος να δούμε το νέο μοντέλο έχει πολλά πλεονεκτήματα ως προς την τυπική μοντελοποίηση και τον σχεδιασμό πρωτοκόλλων, αφού μας επιτρέπει να παραβλέψουμε τις λεπτομέρειες υλοποίησης του διαμεσολαβητή. Επιπρόσθετα, επεκτείνουμε περαιτέρω το νέο μοντέλο επιτρέποντας στις ακμές να έχουν κόστη από ένα, επίσης, σταθερού πληθικού αριθμού σύνολο, τα οποία είναι μόνο προς ανάγνωση. Εν συνεχεία, επιτρέπουμε στους κανόνες μεταβάσεων των εκάστοτε πρωτοκόλλων να διαβάζουν τις καταστάσεις του ζεύγους πρακτόρων που αλληλεπιδρούν και την κατάσταση και το κόστος της ακμής μέσω της οποίας γίνεται η αλληλεπίδραση (αν, φυσικά, έχουμε ορίσει κόστη στο πρόβλημά μας) και να ανανεώνουν όλα αυτά τα στοιχεία πέραν από τα κόστη που είναι μόνο προς ανάγνωση. Παρατηρούμε, επομένως, ότι οι προδιαγραφές των πρωτοκόλλων του νέου μοντέλου συνεχίζουν, να είναι ανεξάρτητες του μεγέθους του πληθυσμού και συνεχίζουν να μην χρησιμοποιούν μοναδικούς προσδιοριστές, δηλαδή, το νέο μοντέλο διατηρεί τα χαρακτηριστικά της κλιμάκωσης, της ομοιομορφίας και της ανωνυμίας. Τα Πρωτόκολλα Πληθυσμών με Διαμεσολαβητή (Mediated Population Protocols - MPP) που προτείνουμε μπορούν να υπολογίσουν σταθερά ιδιότητες γράφων σχετικά με τον γράφο επικοινωνίας. Για να το δείξουμε αυτό παρουσιάζουμε πρωτόκολλα για το μεγιστοτικό ταίριασμα, την μεταβατική θήκη, τις ακμές ελαχίστου κόστους και το ελάχιστο μονοπάτι από τη ρίζα ως τα φύλλα ενός έξω-κατευθυνόμενου δέντρου και αποδεικνύουμε την ορθότητά τους. Εν συνεχεία, δείχνουμε ότι το μοντέλο των πρωτοκόλλων με διαμεσολαβητή αποτελεί ένα ισχυρότερο υπολογιστικά μοντέλο από το κλασικό μοντέλο των πρωτοκόλλων πληθυσμών. Πρώτα παρατηρούμε το προφανές, ότι, δηλαδή, το κλασικό μοντέλο των πρωτοκόλλων πληθυσμών είναι ειδική περίπτωση του νέου μοντέλου, άρα το νέο μοντέλο μπορεί να κάνει σίγουρα τουλάχιστον ότι και το κλασικό. Εν συνεχεία, παρουσιάζουμε ένα πρωτόκολλο με διαμεσολαβητή το οποίο υπολογίζει σταθερά το γινόμενο δύο θετικών ακέραιων στην περίπτωση που ο G (γράφος επικοινωνίας) είναι πλήρης κατευθυνόμενος και συνεκτικός. Τα κατηγορήματα που περιλαμβάνουν πολλαπλασιασμό δύο ακέραιων μεταβλητών δεν είναι ημιγραμμικά και έχει αποδειχθεί ότι τα κλασικά πρωτόκολλα πληθυσμών σε πλήρεις γράφους υπολογίζουν σταθερά μόνο ημιγραμμικά κατηγορήματα, άρα με τον τρόπο αυτό δείχνουμε ότι υπάρχει τουλάχιστον ένα κατηγόρημα που ενώ δεν υπολογίζεται σταθερά απ'' το βασικό μοντέλο υπολογίζεται σταθερά από το μοντέλο το οποίο προτείνουμε. Για τις ανάγκες της απόδειξης διατυπώνουμε και αποδεικνύουμε ένα γενικό Θεώρημα σχετικά με τη σύνθεση δύο πρωτοκόλλων πληθυσμών με διαμεσολαβητή, το ένα εκ των οποίων χρησιμοποιεί σταθεροποιούμενες εισόδους. Δείχνουμε, επίσης, ότι όλα τα κατηγορήματα που υπολογίζονται σταθερά απ'' το μοντέλο μας ανήκουν (μη ομοιόμορφα) στην κλάση NSPACE(m), όπου το m συμβολίζει το πλήθος των ακμών του γράφου επικοινωνίας. Τέλος, ορίζουμε τα πιθανοτικά πρωτόκολλα πληθυσμών με διαμεσολαβητή, στα οποία ο δρομολογητής επιλέγει σε κάθε βήμα την επόμενη αλληλεπίδραση ισοπίθανα μεταξύ των ακμών του γράφου επικοινωνίας και δείχνουμε ότι κάθε Peano κατηγόρημα που υπολογίζεται σταθερά από ένα πιθανοτικό MPP μπορεί να επαληθευτεί σε αιτιοκρατικό πολυωνυμικό χρόνο.