UC Davis

We study population protocols, a model of distributed computing appropriate for modeling well-mixed chemical reaction networks and other physical systems where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners.

Concretely, *population protocols*are asynchronous, complete networks that consist of computational entities called *agents* with no control over the schedule of interactions with other agents. In a population of $n$ agents, repeatedly a random pair of agents are chosen to interact, each observing the state of the other agent before updating its own state.

Population protocols are equivalent to the model of chemical reaction networks, describing abstract chemical reactions such as $A+B \rightarrow C+D$, when the latter is subject to the restriction that all reactions have two reactants and two products, and all rate constants are 1.

In this thesis, we demonstrate an algorithmic advance for the exact majority problem: starting in a population of $n$ agents, each with one of two opinions $A$ or $B$, the agents must determine whether there are more $A$, more $B$, or a tie. The proposed algorithm is \emph{nonuniform}: assume that the agents are initialized with an approximate estimate of $n$(specifically, a value that is $\geq \log n$).

We introduce *uniform* population protocols:networks of anonymous agents whose pairwise interactions are chosen at random, where each agent uses an *identical* transition algorithm that does not depend on the population size $n$. Moreover, we study almost optimal protocols that solve static counting problem: the *counting* problem is that of designing a protocol so that $n$ agents, all starting in the same state, eventually converge to states where each agent encodes in its state an exact or approximate description of population size $n$.

Finally, we introduce population protocols with dynamic size and finish this thesis with a novel counting protocol robust to an adversary who can add or remove agents.