Abstract
We consider a synchronous distributed system with n processes that communicate through a dynamic network guaranteeing 1-interval connectivity i.e., the network topology graph might change at each interval while keeping the graph connected at any time. The processes belonging to the distributed system are identified through a set of labels \(\mathcal{L}=\{\ell_1, \ell_2 \dots, \ell_k\}\) (with 1 ≤ k < n). In this challenging system model, the paper addresses the following problem: “counting the number of processes with the same label”. We provide a distributed algorithm that is able solve the problem based on the notion of energy transfer. Each process owns a fixed energy charge, and tries to discharge itself exchanging, at each round, at most half of its charge with neighbors. The paper also discusses when such counting is possible in the presence of failures. Counting processes with the same label in dynamic networks with homonyms is of great importance because it is as difficult as computing generic aggregating functions.
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
Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164–1188 (2000)
Angluin, D.: Local and global properties in networks of processors (extended abstract). In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC 1980, pp. 82–93. ACM (1980)
Aspnes, J., Fich, F.E., Ruppert, E.: Relationships between broadcast and shared memory in reliable anonymous distributed systems. Distributed Computing 18(3), 209–219 (2006)
Attiya, H., Snir, M., Warmuth, M.K.: Computing on an anonymous ring. J. ACM 35(4), 845–875 (1988)
Awerbuch, B., Goldreich, O., Vainish, R., Peleg, D.: A trade-off between information and communication in broadcast protocols. Journal of the ACM (JACM) 37(2), 238–256 (1990)
Baldoni, R., Bertier, M., Raynal, M., Tucci-Piergiovanni, S.: Looking for a definition of dynamic distributed systems. In: Malyshkin, V.E. (ed.) PaCT 2007. LNCS, vol. 4671, pp. 1–14. Springer, Heidelberg (2007)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. CoRR, abs/1012.0009 (2010)
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Kermarrec, A.-M., Ruppert, E., Tran-The, H.: Byzantine agreement with homonyms. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011, pp. 21–30. ACM, New York (2011)
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)
Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. In: Proceedings of 31st Annual Symposium on Foundations of Computer Science, pp. 355–361. IEEE (1990)
Di Luna, G., Baldoni, R., Bonomi, S., Chatzigiannakis, I.: Counting on Anonymous Dynamic Networks through Energy Transfer. Technical Report 1, MIDLAB, Sapienza University of Rome (2013)
Dolev, S.: Self-stabilization. MIT Press, Cambridge (2000)
Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 513–522. ACM, New York (2010)
Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Brief announcement: Naming and counting in anonymous unknown dynamic networks. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 437–438. Springer, Heidelberg (2012)
O’Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing, DIALM-POMC 2005, pp. 104–110. ACM, New York (2005)
Panaite, P., Pelc, A.: Exploring unknown undirected graphs. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 316–322. Society for Industrial and Applied Mathematics (1998)
Yamashita, M., Kameda, T.: Computing on an anonymous network. In: Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 1988, pp. 117–130. ACM, New York (1988)
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
Di Luna, G.A., Baldoni, R., Bonomi, S., Chatzigiannakis, I. (2013). Counting the Number of Homonyms in Dynamic Networks. 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_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-03089-0_22
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03088-3
Online ISBN: 978-3-319-03089-0
eBook Packages: Computer ScienceComputer Science (R0)