Editing Open Problems (section)

= Leader election =

=== Problem context ===
Biological organisms are exemplars of self-organisation. Mathematical approaches like reaction-diffusion systems attempt to capture geometrical self-organization --- how complex patterns can arise from uniform initial conditions. Analogously we ask how well-mixed chemical systems can transform uniform initial conditions to controlled amounts of desired species. 
Having certain species present in precise counts (eg a species $L$ with exactly 1 molecule) is a prerequisite for a number of sophisticated CRNs in the literature.
For example, constructions for polynomial-time Turing machine simulation requires a "leader": a species with initial count 1, which is used to coordinate interaction among the other species in a controlled way <ref name="SCWB2008"/>.

If a CRN starts with uniform initial conditions  where only "high-count" species are initially present (e.g., count $n$ of some species $X$ in volume $n$), then it is possible to "elect" a leader through two reactions:

$X \to L$

$L + L \to L$

However, this takes expected time $O(n)$, which is "slow" compared with other basic forms of CRN computation. 
For example, for example, the reaction $X \to Y + Y$ "quickly" computes multiplication by 2 in the sense that it takes expected time $\log(n)$ to convert $n$ copies of $X$ into $2n$ copies of $Y$. 
The open question is whether a leader can be elected quickly (say in polylogarithmic time, or even sublinear time).

Algorithms for leader election have been extensively studied in the distributed computing literature. 
The possibility of fast leader election is a long standing open problem in "population protocols," a model which is formally equivalent to a subclass of CRNs.
Angluin et al ("Fast Computation by Population Protocols With a Leader") developed an algorithm which appears to elect a leader in sublinear time with high probability based on extensive numerical simulation.
Although the complexity of the population protocol has so far hindered efforts to prove correctness,
it informs our understanding of what may or may not be possible, and suggests new techniques for a positive result.
Proving either a positive or negative result would be an important development outside of the CRN literature and would engage  the larger CS theory community.

=== Problem overview ===
'''Question:''' Is there a CRN with an initial state with count $n$ of a species $X$ in volume $n$ and count 0 of everything else, that in expected time $\log^k(n)$ for some constant $k$, reaches a state $\vec{c}$ with count 1 of $L$ (and arbitrary counts of everything else), such that every state reachable from $\vec{c}$ has count 1 of $L$?

=== Interested Participants ===

* [[User:Doty | Dave Doty ]]
* [[User:dsolov | David Soloveichik ]]
* [[User:Thachuk | Chris Thachuk ]]
* [[User:Brijder | Robert Brijder ]]
* [[User:Woods | Damien Woods ]]
* [[Niranjan Srinivas]]

=== References ===


Dana Angluin, James Aspnes and David Eisenstat.
Fast Computation by Population Protocols With a Leader. Distributed Computing.
[http://cs-www.cs.yale.edu/homes/aspnes/papers/disc2006-journal.pdf]
 
Dana Angluin, James Aspnes and David Eisenstat.
A Simple Population Protocol for Fast Robust Approximate Majority. Distributed Computing.
[http://www.cs.yale.edu/homes/aspnes/papers/approximate-majority-journal.pdf]

Etienne Perron, Dinkar Vasudevan, and Milan Vojonvic.
Using Three States for Binary Consensus on Complete Graphs TR, September 2008. [http://research.microsoft.com/pubs/78881/tr-2008-114.pdf]

David Doty.
Timing in chemical reaction networks, SODA 2014. [http://www.dna.caltech.edu/~ddoty/papers/tcrn.pdf]