Abstract
Angluin et al. introduced Population protocols as a model in which n passively mobile anonymous finite-state agents stably compute a predicate on the multiset of their inputs via interactions by pairs. The model has been extended by Guerraoui and Ruppert to yield the community protocol models where agents have unique identifiers but may only store a finite number of the identifiers they already heard about. The Population protocol model only computes semi-linear predicates, whereas the community protocol model provides the power of a Turing machine with a \(O(n\log n)\) space.
We consider variations on the above models and we obtain a whole landscape that covers and extends already known results. By considering the case of homonyms, that is to say the case when several agents may share the same identifier, we provide a hierarchy that goes from the case of no identifier (population protocol model) to the case of unique identifiers (community protocol model).
We obtain in particular that any Turing Machine on space \(O(\log ^{O(1)} n)\) can be simulated with at least \(O(\log ^{O(1)} n)\) identifiers, a result filling a gap left open in all previous studies.
Our results also extend and revisit in particular the hierarchy provided by Chatzigiannakis et al. on population protocols carrying Turing Machines on limited space, solving the problem of the gap left by this work between per-agent space \(o(\log \log n)\) (proved to be equivalent to population protocols) and \(O(\log n)\) (proved to be equivalent to Turing machines).
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
Notes
- 1.
These classes are defined in Sect. 3.4.
- 2.
Recall the concept of the chain defined in page 7.
References
Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distrib. Comput. 20(4), 279–304 (2007)
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. In: Twenty-Third ACM Symposium on Principles of Distributed Computing, pp. 290–299. ACM Press (2004)
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)
Arévalo, S., Fernández Anta, A., Imbs, D., Jiménez, E., Raynal, M.: Failure detectors in homonymous distributed systems (with an application to consensus). In: 2012 IEEE 32nd International Conference on Distributed Computing Systems (ICDCS), pp. 275–284 (2012)
Aspnes, J., Ruppert, E.: An introduction to population protocols. In: Bulletin of the EATCS, vol. 93, pp. 106–125 (2007)
Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., Spirakis, P.G.: Passively mobile communicating machines that use restricted space. Theoret. Comput. Sci. 412(46), 6469–6483 (2011). please check and confirm inserted volume number and page range is correct in Ref. [7]
Chatzigiannakis, I., Michail, O., Spirakis, P.G.: Algorithmic verification of population protocols. In: Dolev, S., Cobb, J., Fischer, M., Yung, M. (eds.) SSS 2010. LNCS, vol. 6366, pp. 221–235. Springer, Heidelberg (2010)
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Kermarrec, A., Ruppert, E., Tran-The, H.: Byzantine agreement with homonyms. In: 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011, pp. 21–30 (2011)
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Ruppert, E.: When birds die: making population protocols fault-tolerant. In: Gibbons, P.B., Abdelzaher, T., Aspnes, J., Rao, R. (eds.) DCOSS 2006. LNCS, vol. 4026, pp. 51–66. Springer, Heidelberg (2006)
Delporte-Gallet, C., Fauconnier, H., Tran-The, H.: Homonyms with forgeable identifiers. In: Even, G., Halldórsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 171–182. Springer, Heidelberg (2012)
Di Luna, G.A., Baldoni, R., Bonomi, S., Chatzigiannakis, I.: Counting the number of homonyms in dynamic networks. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds.) SSS 2013. LNCS, vol. 8255, pp. 311–325. Springer, Heidelberg (2013)
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)
Immerman, N.: Nondeterministic space is closed under complementation. In: Structure in Complexity Theory Conference, Third Annual, pp. 112–115. IEEE (1988)
Schönhage, A.: Storage modification machines. SIAM J. Comput. 9(3), 490–508 (1980)
Szelepcsényi, R.: The method of forced enumeration for nondeterministic automata. Acta Inf. 26(3), 279–284 (1988)
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
Bournez, O., Cohen, J., Rabie, M. (2015). Homonym Population Protocols. In: Bouajjani, A., Fauconnier, H. (eds) Networked Systems . NETYS 2015. Lecture Notes in Computer Science(), vol 9466. Springer, Cham. https://doi.org/10.1007/978-3-319-26850-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-26850-7_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26849-1
Online ISBN: 978-3-319-26850-7
eBook Packages: Computer ScienceComputer Science (R0)