Abstract
We study the problems of leader election and population size counting for population protocols: networks of finite-state anonymous agents that interact randomly under a uniform random scheduler. We provide simple protocols for approximate counting of the size of the population and for leader election. We show a protocol for leader election that terminates in \(O(\frac{\log ^2{n}}{\log {m}})\) parallel time, where \(1 \le m \le n\) is a parameter, using \(O(\max \{m,\log n\})\) states. By adjusting the parameter m between a constant and n, we obtain a single leader election protocol whose time and space can be smoothly traded off between \(O(\log ^2 n)\) to \(O(\log n)\) time and \(O(\log n)\) to O(n) states. We also give a protocol which provides an upper bound \(\hat{n}\) of the size n of the population, where \(\hat{n}\) is at most \(n^a\) for some constant \(a>1\). This protocol assumes the existence of a unique leader in the population and stabilizes in \(\varTheta {(\log {n})}\) parallel time, using constant number of states in every node, except from the unique leader which is required to use \(\varTheta {(\log ^2{n})}\) states.
All authors were supported by the EEE/CS initiative NeST. The last author was also supported by the Leverhulme Research Centre for Functional Materials Design. This work was partially supported by the EPSRC Grant EP/P02002X/1 on Algorithmic Aspects of Temporal Graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235–253 (2006)
Michail, O., Spirakis, P.G.: Simple and efficient local codes for distributed stable network construction. Distrib. Comput. 29(3), 207–237 (2016)
Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. Distrib. Comput. 21(3), 183–199 (2008)
Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7, 615–633 (2008)
Chen, H.-L., Doty, D., Soloveichik, D.: Deterministic function computation with chemical reaction networks. Nat. Comput. 7, 517–534 (2014)
Doty, D.: Timing in chemical reaction networks. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 772–784 (2014)
Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distrib. Comput. 20(4), 279–304 (2007)
Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., Spirakis, P.G.: Passively mobile communicating machines that use restricted space. Theor. Comput. Sci. 412(46), 6469–6483 (2011)
Michail, O., Chatzigiannakis, I., Spirakis, P.G.: New models for population protocols. In: Lynch, N.A. (ed.) Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool (2011)
Guerraoui, R., Ruppert, E.: Names trump malice: tiny mobile agents can tolerate byzantine failures. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5556, pp. 484–495. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02930-1_40
Aspnes, J., Ruppert, E.: An introduction to population protocols. In: Garbinato, B., Miranda, H., Rodrigues, L. (eds.) Middleware for Network Eccentric and Mobile Applications. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-89707-1_5
Michail, O., Spirakis, P.G.: Elements of the theory of dynamic networks. Commun. ACM 61(2), 72 (2018)
Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC). ACM (1980)
Attiya, C., Snir, M., Warmuth, M: Computing on an anonymous ring. In: PODC 1985. ACM (1985)
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). https://doi.org/10.1007/978-3-662-47666-6_38
Gasieniec, L., Stachowiak, G.: Fast space optimal leader election in population protocols. In: SODA 2018, ACM-SIAM Symposium on Discrete Algorithms (2018, to appear)
Fischer, M., Jiang, H.: Self-stabilizing leader election in networks of finite-state anonymous agents. In: Shvartsman, M.M.A.A. (ed.) OPODIS 2006. LNCS, vol. 4305, pp. 395–409. Springer, Heidelberg (2006). https://doi.org/10.1007/11945529_28
Di Luna, G.A., Flocchini, P., Izumi, T., Izumi, T., Santoro, N., Viglietta, G.: Population protocols with faulty interactions: the impact of a leader. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 454–466. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57586-5_38
Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: PODC 2006, New York. ACM Press (2006)
Doty, D., Soloveichik, D.: Stable leader election in population protocols requires linear time. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 602–616. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48653-5_40
Belleville, A., Doty, D., Soloveichik, D.: Hardness of computing and approximating predicates and functions with leaderless population protocols. In: ICALP 2017, Leibniz International Proceedings in Informatics (LIPIcs), vol. 80. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)
Alistarh, D., Aspnes, J., Eisenstat, D., Gelashvili, R., Rivest, R.L.: Time-space trade-offs in population protocols. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2560–2579. SIAM (2017)
Mizoguchi, R., Ono, H., Kijima, S., Yamashita, M.: On space complexity of self-stabilizing leader election in mediated population protocol. Distrib. Comput. 25(6), 451–460 (2012)
Das, S., Di Luna, G.A., Flocchini, P., Santoro, N., Viglietta, G.: Mediated population protocols: leader election and applications. In: Gopal, T.V., Jäger, G., Steila, S. (eds.) TAMC 2017. LNCS, vol. 10185, pp. 172–186. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-55911-7_13
Beauquier, J., Clement, J., Messika, S., Rosaz, L., Rozoy, B.: Self-stabilizing counting in mobile sensor networks with a base station. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 63–76. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75142-7_8
Beauquier, J., Burman, J., Clavière, S., Sohier, D.: Space-optimal counting in population protocols. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 631–646. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48653-5_42
Aspnes, J., Beauquier, J., Burman, J., Sohier, D.: Time and space optimal counting in population protocols. In: OPODIS 2016, vol. 70 (2017)
Michail, O.: Terminating distributed construction of shapes and patterns in a fair solution of automata. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 37–46 (2015). Also in Distributed Computing (2017)
Doty, D., Eftekhari, M., Michail, O., Spirakis, P.G., Theofilatos, M.: Exact size counting in uniform population protocols in nearly logarithmic time. CoRR, abs/1805.04832 (2018)
Izumi, T., Kinpara, K., Izumi, T., Wada, K.: Space-efficient self-stabilizing counting population protocols on mobile sensor networks. Theor. Comput. Sci. 552, 99–108 (2014)
Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd ACM Symposium on Theory of computing (STOC), pp. 513–522. ACM (2010)
Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Naming and counting in anonymous unknown dynamic networks. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds.) SSS 2013. LNCS, vol. 8255, pp. 281–295. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03089-0_20
Di Luna, G.A., Baldoni, R., Bonomi, S., Chatzigiannakis, I.: Counting in anonymous dynamic networks under worst-case adversary. In: IEEE 34th International Conference on Distributed Computing Systems (ICDCS) (2014)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emerg. Distrib. Syst. 27(5), 387–408 (2012)
Acknowledgments
We would like to thank David Doty and Mahsa Eftekhari for their valuable comments and suggestions during the development of this research work.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Michail, O., Spirakis, P.G., Theofilatos, M. (2018). Simple and Fast Approximate Counting and Leader Election in Populations. In: Izumi, T., Kuznetsov, P. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2018. Lecture Notes in Computer Science(), vol 11201. Springer, Cham. https://doi.org/10.1007/978-3-030-03232-6_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-03232-6_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03231-9
Online ISBN: 978-3-030-03232-6
eBook Packages: Computer ScienceComputer Science (R0)