Abstract
Population protocol (PP) is a distributed computing model for passively mobile systems, in which a computation is executed by interactions between two agents. This paper is concerned with an extended model, population protocol based on interactions of at most k agents (PP k ). Beauquier et al. (2012) recently introduced the model, and showed a hierarchy of computational powers of PP k with respect to k; a PP k + 1 is strictly more powerful than a PP k . Motivated by a further understanding of the model, this paper investigates the space complexity of PP k for self-stabilizing leader election (SS-LE), which is a fundamental problem for a distributed system. Cai et al. (2012) showed that the space complexity of SS-LE for n agents by a PP (i.e., PP2) is exactly n. This paper shows that the space complexity of SS-LE for n agents by a PP k is exactly ⌈(n − 1)/(k − 1)⌉ + 1.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angluin, D., Aspnes, J., Chan, M., Fischer, M.J., Jiang, H., Peralta, R.: Stably computable properties of network graphs. In: Prasanna, V.K., Iyengar, S.S., Spirakis, P.G., Welsh, M. (eds.) DCOSS 2005. LNCS, vol. 3560, pp. 63–74. Springer, Heidelberg (2005)
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distributed Computing 18, 235–253 (2006)
Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. Distributed Computing 21, 183–199 (2008)
Angluin, D., Aspnes, J., Fischer, M.J., Jiang, H.: Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems 3, Article 13 (2008)
Aspnes, J., Ruppert, E.: An introduction to population protocols. Bulletin of the EATCS 93, 98–117 (2007)
Beauquier, J., Burman, J., Rosaz, L., Rozoy, B.: Non-deterministic population protocols. In: Baldoni, R., Flocchini, P., Binoy, R. (eds.) OPODIS 2012. LNCS, vol. 7702, pp. 61–75. Springer, Heidelberg (2012)
Beauquier, J., Clement, J., Messika, S., Rosaz, L., Rozoy, B.: Self-stabilizing counting in mobile sensor networks. In: Proc. of PODC 2007, pp. 396–397 (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, 433–445 (2012)
Canepa, D., Potop-Butucaru, M.G.: Stabilizing leader election in population protocols. INRIA Rocquencourt, RR-6269 (2007), http://hal.inria.fr/inria-00166632/en/
Chatzigiannakis, I., Michail, O., Spirakis, P.G.: Mediated population protocols. Theoretical Computer Science 412, 2434–2450 (2011)
Chatzigiannakis, I., Michail, O., Spirakis, P.G.: Recent advances in population protocols. In: Královič, R., Niwiński, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 56–76. Springer, Heidelberg (2009)
Devismes, S., Tixeuil, S., Yamashita, M.: Weak vs. self vs. probabilistic stabilization. In: Proc. of ICDCS 2008, pp. 681–688 (2008)
Dijkstra, E.W.: Self stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery 17, 643–644 (1974)
Fischer, M., Jiang, H.: Self-stabilizing leader election in networks of finite-state anonymous agents. In: Shvartsman, A. (ed.) OPODIS 2006. LNCS, vol. 4305, pp. 395–409. Springer, Heidelberg (2006)
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, Part II. LNCS, vol. 5556, pp. 484–495. Springer, Heidelberg (2009)
Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Mediated population protocols. Theoretical Computer Science 412, 2434–2450 (2011)
Mizoguchi, R., Ono, H., Kijima, S., Yamashita, M.: On space complexity of self-stabilizing leader election in mediated population protocol. Distributed Computing 25, 451–460 (2012)
Schrijver, A.: Combinatorial Optimization. Springer (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Xu, X., Yamauchi, Y., Kijima, S., Yamashita, M. (2013). Space Complexity of Self-Stabilizing Leader Election in Population Protocol Based on k-Interaction. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2013. Lecture Notes in Computer Science, vol 8255. Springer, Cham. https://doi.org/10.1007/978-3-319-03089-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-03089-0_7
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03088-3
Online ISBN: 978-3-319-03089-0
eBook Packages: Computer ScienceComputer Science (R0)