Abstract
A system of processes is examined that communicate with beeps in multiple channels. In the beeping model, the processes have limited communication where they can detect the presence of a signal (beep), or its absence (silence). In the weak model, the processes can choose to transmit a beep on one or more channels and can detect beeps and/or silence on all channels. The processes are anonymous and they begin without names to identify themselves. The objective is to develop distributed naming algorithms for two models when n is either known or unknown, where n is the number of processes. The Multichannel Many Beeps Naming algorithm is a Las Vegas algorithm developed for the model when n is known and that has an optimal time complexity of \(\mathcal {O}{(\log {n})}\) rounds. When n is unknown, a Monte Carlo algorithm was developed, called the Unknown Multichannel Many Beeps Naming. It has an optimal time complexity of \(\mathcal {O}(\log {n})\) rounds and a probability of success that is at least \(1-(n\log {n})^{-1}\). These algorithms show an asymptotic improvement when compared to the existing naming algorithms for this model.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Afek, Y., Alon, N., Bar-Joseph, Z., Cornejo, A., Haeupler, B., Kuhn, F.: Beeping a maximal independent set. In: Peleg, D. (ed.) DISC 2011. LNCS, vol. 6950, pp. 32–50. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24100-0_3
Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Z.: A biological solution to a fundamental distributed computing problem. Science 331(6014), 183–185 (2011)
Aldawsari, L.S., Altman, T.: Naming in multichannel with beeps in the strong model. Appl. Sci. 10(20), 7164 (2020)
Andriambolamalala, N.A., Ravelomanana, V.: Energy efficient naming in beeping networks. In: Palattella, M.R., Scanzio, S., Coleri Ergen, S. (eds.) ADHOC-NOW 2019. LNCS, vol. 11803, pp. 355–369. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-31831-4_25
Andriambolamalala, N.A., Ravelomanana, V.: Fault-tolerant energy efficient consensus on ad hoc beeping networks (2020)
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)
Beauquier, J., Burman, J., Davies, P., Dufoulon, F.: Optimal multi-broadcast with beeps using group testing. In: Censor-Hillel, K., Flammini, M. (eds.) SIROCCO 2019. LNCS, vol. 11639, pp. 66–80. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-24922-9_5
Bordim, J.L., Cui, J., Ishii, N., Nakano, K.: Doubly-logarithmic energy-efficient initialization protocols for single-hop radio networks. In: Proceedings of the 16th International Parallel and Distributed Processing Symposium, IPDPS 2002, USA, p. 123. IEEE Computer Society (2002)
Brandes, P., Kardas, M., Klonowski, M., Pająk, D., Wattenhofer, R.: Approximating the size of a radio network in beeping model. In: Suomela, J. (ed.) SIROCCO 2016. LNCS, vol. 9988, pp. 358–373. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48314-6_23
Buhrman, H., Panconesi, A., Silvestri, R., Vitányi, P.M.B.: On the importance of having an identity or, is consensus really universal? Distrib. Comput. 18(3), 167–176 (2006)
Chlebus, B.S., De Marco, G., Talo, M.: Naming a channel with beeps. Fund. Inform. 153(3), 199–219 (2017)
Cornejo, A., Kuhn, F.: Deploying wireless networks with beeps. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 148–162. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15763-9_15
Czumaj, A., Davies, P.: Communicating with beeps. J. Parallel Distrib. Comput. 130, 98–109 (2019)
Dufoulon, F., Burman, J., Beauquier, J.: Beeping a deterministic time-optimal leader election. In: 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
Efremenko, K., Kol, G., Saxena, R.R.: Noisy beeps. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC 2020, pp. 418–427. Association for Computing Machinery, New York (2020)
Eǧecioǧlu, Ö., Singh, A.K.: Naming symmetric processes using shared variables. Distrib. Comput. 8(1), 19–38 (1994)
Förster, K.-T., Seidel, J., Wattenhofer, R.: Deterministic leader election in multi-hop beeping networks. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 212–226. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45174-8_15
Kutten, S., Ostrovsky, R., Patt-Shamir, B.: The las-vegas processor identity problem (how and when to be unique). J. Algorithms 37(2), 468–494 (2000)
Lipton, R.J., Park, A.: The processor identity problem. Inf. Process. Lett. 36(2), 91–94 (1990)
Myoupo, J.F.: Dynamic initialization protocols for mobile ad hoc networks. In: The 11th IEEE International Conference on Networks, ICON 2003, pp. 149–154, October 2003
Nakano, K., Olariu, S.: Energy-efficient initialization protocols for radio networks with no collision detection. In: Proceedings 2000 International Conference on Parallel Processing, pp. 263–270, August 2000
Nakano, K., Olariu, S.: Randomized initialization protocols for ad hoc networks. IEEE Trans. Parallel Distrib. Syst. 11(7), 749–759 (2000)
Navlakha, S., Bar-Joseph, Z.: Distributed information processing in biological and computational systems. Commun. ACM 58(1), 94–102 (2014)
Panconesi, A., Papatriantafilou, M., Tsigas, P., Vitányi, P.: Randomized naming using wait-free shared variables. Distrib. Comput. 11(3), 113–124 (1998)
Schneider, J., Wattenhofer, R.: What is the use of collision detection (in wireless networks)? In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 133–147. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15763-9_14
Teng, S.-H.: Space efficient processor identity protocol. Inf. Process. Lett. 34(3), 147–154 (1990)
Toh, C.-K.: Ad Hoc Mobile Wireless Networks Protocols and Systems. Prentice Hall PTR, Hoboken (2002)
Yao, A.C.: Probabilistic computations: toward a unified measure of complexity. In: 18th Annual Symposium on Foundations of Computer Science (SFCS 1977), pp. 222–227 (1977)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Aldawsari, L.S., Altman, T. (2022). Naming Processes in Multichannels with Beeps in the Weak Model. In: Arai, K. (eds) Intelligent Computing. Lecture Notes in Networks and Systems, vol 283. Springer, Cham. https://doi.org/10.1007/978-3-030-80119-9_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-80119-9_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-80118-2
Online ISBN: 978-3-030-80119-9
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)