With recent advances in DNA computation, scientists are on the verge of developing smart molecules that can communicate, perform tasks, and control matter at the nano level. To reach this initiative, as computer scientists, we should provide the theoretical foundation needed through the abstract models of molecular computing. My work is focused on a better understanding of distributed systems that model these physical systems and capture their dynamics to help biological computation scientists achieve their goals. I am working on population protocols, an appropriate model for electronic computing scenarios such as sensor networks, and ''fast-mixing'' physical systems such as chemical reactions, gene regulatory networks, and animal populations. I've researched problems like leader election, majority and consensus, exact and approximate counting, and counting in dynamic networks in population protocols. In our papers, we use probabilistic and combinatorics techniques to design and analyze our distributed (randomized) algorithms.
Population protocols are a complete network of agents with no control over whom they will interact with; in particular, the agents communicate via a sequence of pairwise interactions among randomly chosen pairs of agents.
Dynamic size counting in population protocols
David Doty and Mahsa Eftekhari
SAND 2022: 1st Symposium on Algorithmic Foundations of Dynamic Networks
In this paper, we study the population size counting problem in the presence of an adversary who can add or remove agents arbitrarily at any time.
A time and space optimal stable population protocol solving exact majority
David Doty, Mahsa Eftekhari, Leszek Gąsieniec, Grzegorz Stachowiak, Eric Severson, and Przemysław Uznański
FOCS 2021: 62nd Annual IEEE Symposium on Foundations of Computer Science, (Feb., 2022)
BA in PODC 2021: Proceedings of the 40th ACM Symposium on Principles of Distributed Computing
We study the exact majority problem in population protocols. Assuming all agents hold one of the blue or red votes, the agents must compute which vote has more supporters.
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. In this survey paper, we describe recent algorithmic advances on the counting problem.
We study population protocols with limited agents who can send/receive constant size messages in their interactions. Although many researchers studied large state (polylog(n)) and\or constant state population protocols, as far as we know, no research considers the intermediate model with agents with large memory but limited message size.
We consider the problem of counting the number of agents in population protocols. This paper presented a polylog(n) state protocol approximating the population size (n) within a constant additive factor. The approximate counting problem is motivated by many existing protocols that assume the population size is known to the agents in advance.
We presented the first sublinear time protocol for the exact population size counting problem in which the agents must calculate the population size (n) exactly.