University of Cambridge > > Isaac Newton Institute Seminar Series > "No We Can't": Impossibility of efficient leader election by chemical reactions

"No We Can't": Impossibility of efficient leader election by chemical reactions

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact INI IT.

SDBW03 - Advances in numerical and analytic approaches for the study of non-spatial stochastic dynamical systems in molecular biology

Co-author: David Soloveichik (University of Texas, Austin)

Suppose a chemical system requires a single molecule of a certain species $L$. Preparing a solution with just a single copy of $L$ is a difficult task to achieve with imprecise pipettors. Could we engineer artificial reactions (a chemical election algorithm, so to speak) that whittle down an initially large count of $L$ to 1? Yes, with the reaction $L+L \to L+F$: whenever two candidate leaders encounter each other, one drops out of the race. In volume $v$ convergence to a single $L$ requires expected time proportional to $v$; the final reaction— two lone $L$'s seeking each other in the vast expanse of volume $v$— dominates the whole expected time.

One might hope that more cleverly designed reactions could elect a leader more quickly. We dash this hope: $L+L \to L+F$, despite its sloth, is the fastest chemical algorithm for leader election there is (subject to some reasonable constraints on the reactions). The techniques generalize to establish lower bounds on the time required to do other computational tasks, such as computing which of two species $X$ or $Y$ holds an initial majority.

Democracy works… but it's painstakingly slow.

Related Links

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2021, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity