Abstract
We consider the task of electing a leader in a distributed manner in ad hoc multi-hop radio networks. Radio networks represent the class of wireless networks in which one frequency is used for transmissions, network’s topology can be represented by a simple undirected graph with some n nodes, and there is no collision detection. We give a randomized algorithm electing a leader in \(\mathcal{O}(n)\) expected time and prove that this time bound is optimal. We give a deterministic algorithm electing a leader in \(\mathcal{O}(n\log^{3/2}n \sqrt{\log\log n})\) time. By way of application, we show how to perform gossiping with combined messages in \(\mathcal{O}(n\log^{3/2} n \sqrt{\log\log n})\) time by a deterministic algorithm, and in \(\mathcal{O}(n)\) expected time by a randomized algorithm.
The work of the first author was supported by the NSF Grant 1016847. The work of the second author was Supported by the Engineering and Physical Sciences Research Council [grant number EP/G023018/1]. The work of the third author was Supported by a NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.
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
Afek, Y., Gafni, E.: Time and message bounds for election in synchronous and asynchronous complete networks. SIAM J. on Computing 20(2), 376–394 (1991)
Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd edn. John Wiley (2004)
Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems. In: Proceedings of the 19th ACM Symposium on Theory of Computing, STOC, pp. 230–240 (1987)
Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Journal of Computer and System Sciences 45(1), 104–126 (1992)
Censor-Hillel, K., Gilbert, S., Kuhn, F., Lynch, N.A., Newport, C.C.: Structuring unreliable radio networks. In: Proceedings of the 30th ACM Symposium on Principles of Distributed Computing, PODC, pp. 79–88 (2011)
Chlebus, B.S., Kowalski, D.R., Pelc, A., Rokicki, M.A.: Efficient Distributed Communication in Ad-Hoc Radio Networks. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 613–624. Springer, Heidelberg (2011)
Chlebus, B.S., Kowalski, D.R., Radzik, T.: Many-to-many communication in radio networks. Algorithmica 54(1), 118–139 (2009)
Clementi, A.E.F., Monti, A., Silvestri, R.: Distributed broadcast in radio networks of unknown topology. Theoretical Computer Sciences 302(1-3), 337–364 (2003)
Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. Journal of Algorithms 60(2), 115–143 (2006)
De Marco, G.: Distributed broadcast in unknown radio networks. SIAM Journal on Computing 39(6), 2162–2175 (2010)
Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems 5(1), 66–77 (1983)
Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. on Computing 27(1), 302–316 (1998)
Gąsieniec, L.: On Efficient Gossiping in Radio Networks. In: Kutten, S., Žerovnik, J. (eds.) SIROCCO 2009. LNCS, vol. 5869, pp. 2–14. Springer, Heidelberg (2010)
Gąsieniec, L., Pagourtzis, A., Potapov, I., Radzik, T.: Deterministic communication in radio networks with large labels. Algorithmica 47(1), 97–117 (2007)
Jurdziński, T., Kutyłowski, M., Zatopiański, J.: Efficient algorithms for leader election in radio networks. In: Proceedings of the 21st ACM Symposium on Principles of Distributed Computing, PODC, pp. 51–57 (2002)
Kowalski, D.R., Pelc, A.: Broadcasting in undirected ad hoc radio networks. Distributed Computing 18(1), 43–57 (2005)
Kowalski, D.R., Pelc, A.: Leader Election in Ad Hoc Radio Networks: A Keen Ear Helps. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol. 5556, pp. 521–533. Springer, Heidelberg (2009)
Kuhn, F., Lynch, N.A., Newport, C.C., Oshman, R., Richa, A.W.: Broadcasting in unreliable radio networks. In: Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, PODC, pp. 336–345 (2010)
Kuhn, F., Lynch, N.A., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC, pp. 513–522 (2010)
Kushilevitz, E., Mansour, Y.: An Ω(D log(N/D)) lower bound for broadcast in radio networks. SIAM Journal on Computing 27(3), 702–712 (1998)
Martel, C.U.: Maximum finding on a multiple access broadcast network. Information Processing Letters 52(1), 7–15 (1994)
Nakano, K., Olariu, S.: A survey on leader election protocols for radio networks. In: Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN, pp. 63–68 (2002)
Newport, C.C., Lynch, N.A.: Modeling radio networks. Distributed Computing 24(2), 101–118 (2011)
Vaya, S.: Faster gossiping in bidirectional radio networks with large labels. CoRR abs/1105.0479 (2011)
Willard, D.E.: Log-logarithmic selection resolution protocols in a multiple access channel. SIAM Journal on Computing 15(2), 468–477 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chlebus, B.S., Kowalski, D.R., Pelc, A. (2012). Electing a Leader in Multi-hop Radio Networks. In: Baldoni, R., Flocchini, P., Binoy, R. (eds) Principles of Distributed Systems. OPODIS 2012. Lecture Notes in Computer Science, vol 7702. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35476-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-35476-2_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35475-5
Online ISBN: 978-3-642-35476-2
eBook Packages: Computer ScienceComputer Science (R0)