Leader election

Outline

We should define variants of the problem to focus on:

1. deterministic versus small probability of error
2. uniform initial state ($n$ copies of $X$ in volume $n$) versus the CRN must handle all initial configurations with $n$ molecules (the latter proved to be impossible to handle)
3. population protocols (2-reactants, 2-products) versus allowing any reactions (the latter can be done by cheating with the reaction $2X \to 3X$)
4. how do we count the expected time until "done":
   • last time the leader changes (when it changes from 0 or 2 to 1)
   • time at which the CRN enters a state from which it is impossible to change the count of $L$ (which may happen much later than the last time $L$ changes)
   • first time at which the leader gets count 1: we can consider CRNs with expected time $O(log^k n)$ delay between the configurations reaching $L$ of count 1. In this case, downstream CRNs can use the species $L$ as a leader in intervals of $O(log^k n)$ time with high probability.
5. is there only 1 leader species, or do we allow a set $\mathcal{L}=\{L_1,\ldots,L_k\}$ of leader species, so long as eventually exactly one $L_i$ is present

In each of the options, exactly one option makes the leader election problem easier to solve, so that is the option we should choose if trying to show leader election is possible, and the other option should be chosen if we want to show it is impossible.

Insights we had:

1. Leader election is not speed fault-free.
2. If the stabilization must happen simultaneously with the last time the leader count changes, that reaction must be $\Omega(n)$ (assuming there is exactly one leader species; this does not apply if we allow a set $\mathcal{L}$ of several leader species). The lesson is that to prove leader election is impossible, one should focus not on the last reaction to change $L$, but instead on the reaction that stabilizes $\# L$ (or focus on something else).
3. It seems leader election can be done if one allows the number of species to grow with $n$ ($O(\log n)$ species seemed to suffice)
4. Leader election can be done in expected time (close to) $O(\sqrt{n})$ with a non-uniform initial state with $n F_1$ and $\frac{\sqrt{n}}{n^{1/4}} F_2$. This violates the hypothesis of a uniform initial state, but it served as a counter-example to several ideas for how to prove leader election is impossible, since those ideas if correct would work on this CRN as well.

Report

Variants of the leader election problem. We identified several variants of the leader election problem. In particular, there are several binary choices to be made, in which one option makes the problem easier to solve (hence should be chosen if attempting to prove fast leader election is possible, and the other option should be chosen if attempting to prove it is impossible, so as to make the task easier). In particular:

1. Deterministic versus randomized: The deterministic variant of the problem (harder to solve) requires that it should be impossible to reach a state in which the leader cannot be elected (i.e., the leader has stabilized to some count other than 1, or the CRN has reached a state $\vec{c}$ such that every state reachable from $\vec{c}$ is not stable, where "stable" means that $\# L$ cannot change. The randomized variant allows a small probability of error.
2. Initial state: The "standard" requirement is that the CRN should be able to handle, for every $n\in\mathbb{N}$, the "uniform" initial state with $n X$ (where $X$ is some possibly non-leader species) and 0 count of everything else. A stronger requirement would be that for each $n\in\mathbb{N}$, the CRN must handle all initial configurations with $n$ molecules. This requirement seems too strong: we were able to prove that no CRN can deterministically elect a leader from any possible initial state.
3. Reactions: We focused on population protocols (all reactions are 2 reactants and 2 products) versus allowing any sort of reactions. Allowing any reaction appears to be too strong: there is a small CRN that uses the reaction $2Y \to 3Y$ (which is pathological in the sense that $\# Y$ goes to $\infty$ in constant time, in order to produce a single $L$ and then "kill" the $X$'s before another $L$ can be produced, via $X \to Y + L$, $2Y \to 3Y$, $Y + X \to Y$, which (assuming we set rate constants correctly) creates exactly 1 L and then consumes all $n-1$ remaining copies of $X$ before a second $L$ cna be created (this has not been fleshed out completely but it seems that allowing such reactions does give too much power). Therefore we focused on population protocols.
4. Definition of expect expected time until "done": The are two reasonable possibilities, based on the observation that the reaction that last affects $\# L$ may be different from the reaction that causes the CRN to stabilize (i.e., enter a state from which it is impossible to change $\# L$.
5. Single versus multiple leader species: While we require that the count of the leader eventually reaches exactly 1, this leaves open the possibility that we allow a set $\mathcal{L}=\{L_1,\ldots,L_k\}$ of different leader species, so long as eventually exactly one $L_i$ is present. This is in fact how the proposed fast leader election of [Angluin et al.] works. Allowing several leader species makes the task easier, so to prove an impossibility result it may help to require a single leader species.

Progress. Unsurprisingly, we were unable to resolve the leader election problem during the workshop. However, several insights were gained:

We were able to resolve the problem positively or negatively by changing the assumptions. This gave us insight into what the "shape" of a solution to the problem must look like.

1. Leader election is not speed-fault free: In this variant, we strengthen the requirement on speed. Instead of requiring that the expected time be fast, even though there could be a low probability of executing a "slow" reaction such as $L+A\to \ldots$ when $\# L = \# A = 1$, we require that every reachable state has the property that there is some sequence of reactions electing a leader, none of which are "slow" in the previous sense (i.e., none of them are bimolecular reactions between two $O(1)$-count species). This requirement makes the leader election problem impossible. In other words, even if the CRN deterministically elects a leader, there is always a reachable state $\vec{c}$ with the property that for every stable state $\vec{o}$ with $\vec{o}(L)=1$, every sequence of reactions reaching from $\vec{c}$ to $\vec{o}$ has a bimolecular reaction $X+Y\to$ with $\# X,\# Y = O(1)$, hence executing that reaction would take linear time. This result follows from recent work by Chen, Cummings, Doty, and Soloveichik ("Speed faults in computation by chemical reaction networks, in submission).
2. If we make the strong requirement that the reaction that last changes $\# L$ is also the reaction that stabilizes $\# L$, then leader election is impossible. This is because that reaction must necessarily be a slow bimolecular reaction. Hence, if we want to focus on one particular reaction in order to prove that the reason leader election CRNs must be slow is because that one reaction must be slow, it is not sufficient to focus on the last reaction that changes $\# L$: we must consider the last reaction that stabilizes $\# L$. For example, we could have the final reaction changing $\# L$ be $Y + L \to \emptyset$ be fast because $\# Y = \Theta(n)$, but the final reaction that stabilizes $\# L$ could be $Y \to \emptyset$, which stabilizes $\# L$ when $\# Y = 1$.
3. If we allow a non-uniform initial state, then leader election can be done in sublinear time. In particular, the following CRN takes expected time $\sqrt{n}$ to elect a leader when started from initial state $\{ n F_1, \frac{\sqrt{n}}{n^{1/4}} F_2 \}$: $$ F_2 + F_2 \to L + K \\ K + F_1 \to 2 K \\ K + F_2 \to 2 K \\ L + L \to L $$ The first reaction produces one copy of $L$ and one of $K$ in expected time $\sqrt{n}$. The second and third reactions convert all $F_1$ and $F_2$ to $K$ in expected time $O(\log n)$, which is very likely to complete before the first reaction can execute a second time. The final reaction handles the low-probability case that the first reaction executes two or more times and guarantees that eventually a single leader is elected no matter what. The probability that the final reaction is needed is so low that its contribution to the total expected time is negligible. This CRN served as a source of counterexamples to several reasonable-sounding (but ultimately flawed) proof ideas. In particular, it has the property that the time $\# L$ last changes (which is the first time the first reaction happens, assuming no errors) is separate from the time $\# L$ stabilizes (which is the final time reaction $K + F_2 \to 2K$ happens).
4. If we allow the number of species to grow with $n$ then a certain kind of leader election can be done in polylogarithmic time. Suppose we start the following CRN with $\{n/2 \ L_\lambda, n/2\ N_\lambda$}, and require the system to quickly converge to a state with one molecule of any of the "$L$" species. For all binary strings $x, y$ such that $|x|, |y| < c \log{n}$, add reactions: $$ L_x \to L_{x0} \\ L_x \to L_{x1} \\ L_x + N_y \to L_x + N_x \ (y < x) \\ N_x + N_y \to 2 N_x \ (y < x) \\ L_x + N_y \to 2 N_y \ (y > x) \\ L_x + L_x \to L_x + N_x \ (y \leq x) $$ Intuitively, after logarithmic time the first two reactions create a diversity of the $L$ species labeled by binary string $x$, and the following two reactions propagate the largest (dictionary order) $x$ to $\Omega(n)$ of the population. The 5th reaction destroys all smaller leaders. The last reaction ensures that even if two leaders with the same bit string are formed, they will get eliminated (slowly). Since the probability of this happening decreases exponentially with $|x|$, with high probability a leader can be elected quickly, and the whole process remains deterministic.