Date of Award
Spring 2023
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Computer Science
First Advisor
Aspnes, James
Abstract
The population protocol model introduced by Angluin et al. in 2006 offers a theoretical framework for designing and analyzing distributed algorithms among limited-resource mobile agents. The original model elegantly abstracts computation in complex systems of simple devices. However, some of these simplifications detract from the pragmatism of the theory in properly modeling real-world systems. In this work, we study various adaptations of the original population protocol model that are inspired by the networks that these algorithms aim to simulate. We focus on three such modifications to the model. First, we consider the separation of agent memory into two components: an externally visible "message" and an internally hidden state. This distinction is inspired by the difference between computational and communication bandwidth in sensors and other limited-resource devices. We design a synchronous broadcast primitive which we then implement to perform more complex computations. We show that symmetric functions can be computed by population protocols with exactly 1-bit messages when the internal state space is unbounded. Then, we show that 1-bit messages are sufficient to stably simulate Turing machine computations with known time and space complexity under a uniform random scheduler. Next, we formalize private input computation in the population protocol model with probabilistic scheduling. While the original population protocol model considers the concept of anonymity, the issue of privacy is not investigated thoroughly. However, there is a need for time- and space-efficient privacy-preserving techniques in the population protocol model if these algorithms are to be implemented in settings handling sensitive data, such as within wireless sensor networks or systems of medical wearables. In this work, we introduce various formal definitions of privacy and apply these definitions to both existing and novel protocols. We show that the Remainder-computing protocol from Delporte-Gallet et al. in 2007 (which is proven to satisfy output independent privacy under adversarial scheduling) is not information-theoretically private under probabilistic scheduling. In contrast, we provide a new algorithm and show that it correctly and information-theoretically privately computes Remainder in populations with probabilistic scheduling. Finally, we introduce and study a variation of the population protocol model wherein certain states are persistent. This modification to the original model is motivated by applications of population protocols in chemical reaction networks. We formally define a variant of the population protocol model where some number of agents are understood to never change their state, and the remaining agents in the population aim to compute some function over these persistent states. We show that for total population size N, Parity cannot be computed in this new model in fewer than Ω(N²) steps, and a lower bound of Ω(√N) on the initial input margin is needed to compute Majority in O(N log N) steps. We also study the effect of spontaneous state changes on the computation of the Majority problem in the presence of persistent states. We prove that an adaptation of third-state dynamics can be used to solve Approximate Majority in the presence of catalysts and leaks, both separately and together. Lastly, we form a comparison between the effects of leaks and that of previously studied Byzantine processes on population protocols.
Recommended Citation
Amir, Talley, "Messages, Secrets, and Catalysts in Population Protocols with Probabilistic Scheduling" (2023). Yale Graduate School of Arts and Sciences Dissertations. 887.
https://elischolar.library.yale.edu/gsas_dissertations/887
