Abstract
Loose stabilization is a relaxed notion of self-stabilization, which guarantees algorithms to converge and keep some desired behavior from any initial configuration, but allows the algorithms to drop out of it after a sufficiently long period. In this paper, we investigate the complexity of the loosely-stabilizing leader election problem in the population protocol model under the probabilistic scheduler. The primary contribution is to give lower bounds for the expected length of convergence periods and the memory space. Precisely, for any loosely-stabilizing leader election algorithm with stabilization periods of length \(\Omega(\exp(N))\) in expectation, each agent needs Ω(logN)-bit memory space, and the expected convergence length is Ω(Nn), where n is the (unknown) number of agents, and N is the upper bound knowledge for n available to the algorithm. We also show the matching upper bounds by proposing a new loosely-stabilizing leader election algorithm, which slightly improves the expected convergence length of the previously known algorithm by Sudo et al. [15] without any degradation of the memory usage or the stabilization length.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alistarh, D., Gelashvili, R.: Polylogarithmic-time leader election in population protocols. In: Halldórsson, M.M., Iwama, K., Kobayashi, N. (eds.) ICALP 2015, Part II. 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(4), 235–253 (2006)
Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. Distributed Computing 21(3), 183–199 (2008)
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. ACM Transactions on Autonomous Adaptive Systtems 3(4), 1–28 (2008)
Beauquier, J., Blanchard, P., Burman, J.: Self-stabilizing leader election in population protocols over arbitrary communication graphs. In: Baldoni, R., Nisse, N., van Steen, M. (eds.) OPODIS 2013. LNCS, vol. 8304, pp. 38–52. Springer, Heidelberg (2013)
Beauquier, J., Burman, J., Clement, J., Kutten, S.: On utilizing speed in networks of mobile agents. In: Proc. of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 305–314 (2010)
Beauquier, J., Burman, J., Kutten, S.: Making population protocols self-stabilizing. In: Guerraoui, R., Petit, F. (eds.) SSS 2009. LNCS, vol. 5873, pp. 90–104. Springer, Heidelberg (2009)
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)
Cai, S., Izumi, T., Wada, K.: How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model. Theory of Computing Systems 50(3), 433–445 (2012)
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)
Flajolet, P.: Approximate counting: A detailed analysis. BIT 25(1), 113–134 (1985)
Izumi, T., Kinpara, K., Izumi, T., Wada, K.: Space-efficient self-stabilizing counting population protocols on mobile sensor networks. Theoretical Computer Science 552, 99–108 (2014)
Ogata, M., Yamauchi, Y., Kijima, S., Yamashita, M.: A randomized algorithm for finding frequent elements in streams using o(loglogN) space. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 514–523. Springer, Heidelberg (2011)
Sudo, Y., Nakamura, J., Yamauchi, Y., Ooshita, F., Kakugawa, H., Masuzawa, T.: Loosely-stabilizing leader election in a population protocol model. Theoretical Computer Science 444, 100–112 (2012)
Sudo, Y., Ooshita, F., Kakugawa, H., Masuzawa, T.: Loosely-stabilizing leader election on arbitrary graphs in population protocols. In: Aguilera, M.K., Querzoni, L., Shapiro, M. (eds.) OPODIS 2014. LNCS, vol. 8878, pp. 339–354. Springer, Heidelberg (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Izumi, T. (2015). On Space and Time Complexity of Loosely-Stabilizing Leader Election. In: Scheideler, C. (eds) Structural Information and Communication Complexity. SIROCCO 2015. Lecture Notes in Computer Science(), vol 9439. Springer, Cham. https://doi.org/10.1007/978-3-319-25258-2_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-25258-2_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25257-5
Online ISBN: 978-3-319-25258-2
eBook Packages: Computer ScienceComputer Science (R0)