Abstract
A population protocol stably elects a leader if, for all n, starting from an initial configuration with n agents each in an identical state, with probability 1 it reaches a configuration y that is correct (exactly one agent is in a special leader state \(\ell \)) and stable (every configuration reachable from y also has a single agent in state \(\ell \)). We show that any population protocol that stably elects a leader requires \(\Omega (n)\) expected “parallel time” — \(\Omega (n^2)\) expected total pairwise interactions — to reach such a stable configuration. Our result also informs the understanding of the time complexity of chemical self-organization by showing an essential difficulty in generating exact quantities of molecular species quickly.
D. Doty—Author was supported by NSF grants CCF-1219274 and CCF-1442454 and the Molecular Programming Project under NSF grant 1317694.
D. Soloveichik—Author was supported by an NIGMS Systems Biology Center grant P50 GM081879 and NSF grant CCF-1442454.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alistarh, D., Gelashvili, R.: Polylogarithmic-time leader election in population protocols. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 479–491. Springer, Heidelberg (2015)
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distributed Computing 18, 235–253 (2006). http://dx.doi.org/10.1007/s00446-005-0138-3, preliminary version appeared in PODC 2004
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Urn automata. Tech. Rep. YALEU/DCS/TR-1280, Yale University, November 2003
Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. Distributed Computing 21(3), 183–199 (2008). preliminary version appeared in DISC 2006
Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distributed Computing 20(4), 279–304 (2007)
Angluin, D., Aspnes, J., Fischer, M.J., Jiang, H.: Self-stabilizing population protocols. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol. 3974, pp. 103–117. Springer, Heidelberg (2006)
Bower, J.M., Bolouri, H.: Computational modeling of genetic and biochemical networks. MIT press (2004)
Chen, H.-L., Cummings, R., Doty, D., Soloveichik, D.: Speed faults in computation by chemical reaction networks. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 16–30. Springer, Heidelberg (2014). http://dx.doi.org/10.1007/978-3-662-45174-8_2
Chen, H.L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Natural Computing 13(4), 517–534 (2014). preliminary version appeared in DISC 2012
Chen, Y.J., Dalchau, N., Srinivas, N., Phillips, A., Cardelli, L., Soloveichik, D., Seelig, G.: Programmable chemical controllers made from DNA. Nature Nanotechnology 8(10), 755–762 (2013)
Cunha-Ferreira, I., Bento, I., Bettencourt-Dias, M.: From zero to many: control of centriole number in development and disease. Traffic 10(5), 482–498 (2009)
Dickson, L.E.: Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. American Journal of Mathematics 35(4), 413–422 (1913)
Doty, D.: Timing in chemical reaction networks. In: SODA 2014: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 772–784, January 2014
Gillespie, D.T.: Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry 81(25), 2340–2361 (1977)
Karp, R.M., Miller, R.E.: Parallel program schemata. Journal of Computer and System Sciences 3(2), 147–195 (1969)
Petri, C.A.: Communication with automata. Tech. rep, DTIC Document (1966)
Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. Proceedings of the National Academy of Sciences 107(12), 5393 (2010). preliminary version appeared in DISC 2008
Volterra, V.: Variazioni e fluttuazioni del numero dindividui in specie animali conviventi. Mem. Acad. Lincei Roma 2, 31–113 (1926)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Doty, D., Soloveichik, D. (2015). Stable Leader Election in Population Protocols Requires Linear Time. In: Moses, Y. (eds) Distributed Computing. DISC 2015. Lecture Notes in Computer Science(), vol 9363. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48653-5_40
Download citation
DOI: https://doi.org/10.1007/978-3-662-48653-5_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48652-8
Online ISBN: 978-3-662-48653-5
eBook Packages: Computer ScienceComputer Science (R0)