Editing Leader election (section)

= Outline =

We should define variants of the problem to focus on:
# deterministic versus small probability of error
# 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)
# population protocols (2-reactants, 2-products) versus allowing any reactions (the latter can be done by cheating with the reaction $2X \to 3X$)
# 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.
# 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:
# Leader election is not speed fault-free.
# 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).
# 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)
# 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.