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

47 mins 57 secs, 698.15 MB, MPEG-4 Video 640x360, 29.97 fps, 44100 Hz, 1.94 Mbits/sec

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/2216384/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Doty, D (University of California, Davis) Tuesday 5th April 2016 - 11:00 to 11:45


Created:	2016-04-06 10:29
Collection:	Stochastic Dynamical Systems in Biology: Numerical Methods and Applications
Publisher:	Isaac Newton Institute
Copyright:	Doty, D
Language:	eng (English)
Distribution:	World (downloadable)
Explicit content:	No
Aspect Ratio:	16:9
Screencast:	No
Bumper:	UCS Default
Trailer:	UCS Default


Abstract:	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→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→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 http://web.cs.ucdavis.edu/~doty/papers/slepprlt.pdf - Paper

Abstract:

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→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→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

http://web.cs.ucdavis.edu/~doty/papers/slepprlt.pdf - Paper

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video *	640x360	1.94 Mbits/sec	698.15 MB	View	Download
WebM	640x360	596.47 kbits/sec	209.55 MB	View	Download
iPod Video	480x270	522.2 kbits/sec	183.40 MB	View	Download
MP3	44100 Hz	249.74 kbits/sec	87.80 MB	Listen	Download
Auto	(Allows browser to choose a format it supports)

Streaming Media Service Upload

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