Abstract
We show that the asymptotic gain in the time complexity when using collision detection depends heavily on the task by investigating three prominent problems for wireless networks, i.e. the maximal independent set (MIS), broadcasting and coloring problem. We present lower and upper bounds for all three problems for the Growth-Bounded Graph such as the Unit Disk Graph. We prove that the benefit of collision detection ranges from an exponential improvement down to no asymptotic gain at all. In particular, for the broadcasting problem our deterministic algorithm is running in time O(Dlogn). It is an exponential improvement over prior work, if the diameter D is polylogarithmic in the number of nodes n, i.e. D ∈ O(logc n) for some constant c.
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
Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Comput. Syst. Sci. 43(2) (1991)
Chlebus, B., Gcasieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in unknown radio networks. In: Symp. on Discrete Algorithms, SODA (2000)
Clementi, A.E.F., Monti, A., Silvestri, R.: Distributed broadcast in radio networks of unknown topology. Theor. Comput. Sci. 302(1-3) (2003)
Czyzowicz, J., Gasieniec, L., Kowalski, D.R., Pelc, A.: Consensus and mutual exclusion in a multiple access channel. In: Int. Symposium on Distributed Computing, DISC (2009)
Dessmark, A., Pelc, A.: Broadcasting in geometric radio networks. Journal of Discrete Algorithms 5 (2007)
Erdoes, P., Frankl, P., Fiiredi, Z.: Families of finite sets in which no set is covered by the union of r others. Israel J. of Math. 51 (1985)
Greenberg, A.G., Winograd, S.: A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. J. ACM 32(3) (1985)
Ilcinkas, D., Kowalski, D.R., Pelc, A.: Fast radio broadcasting with advice. Theor. Comput. Sci. 411(14-15) (2010)
Jurdziński, T., Stachowiak, G.: Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 535–549. Springer, Heidelberg (2002)
Kowalski, D.R., Pelc, A.: Broadcasting algorithms in radio networks with unknown topology. In: Distributed Computing, vol. 18 (2005)
Kowalski, D.R., Pelc, A.: Leader election in ad hoc radio networks: A keen ear helps. In: ICALP (2) (2009)
Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 273–287. Springer, Heidelberg (2005)
Kushilevitz, E., Mansour, Y.: An omega(d log(n/d)) lower bound for broadcast in radio networks. In: Symp. on Principles of Distributed Computing (PODC) (1993)
Moscibroda, T., Wattenhofer, R.: Maximal Independent Sets in Radio Networks. In: Symp. on Principles of Distributed Computing, PODC (2005)
Schneider, J., Wattenhofer, R.: A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs. In: Symp. on Principles of Distributed Computing PODC (2008)
Schneider, J., Wattenhofer, R.: Coloring Unstructured Wireless Multi-Hop Networks. In: Symp. on Principles of Distributed Computing, PODC (2009)
Schneider, J., Wattenhofer, R.: What Is the Use of Collision Detection (in Wireless Networks). TIK Technical Report 322 (2010), ftp://ftp.tik.ee.ethz.ch/pub/publications/TIK-Report-322.pdf
Tobagi, F.A., Kleinrock, L.: Packet Switching in Radio Channels: Part II - The Hidden Terminal Problem in Carrier Sense Multiple Access and the Busy Tone Solution. COM 23(12) (1975)
Willard, D.E.: Log-logarithmic selection resolution protocols in a multiple access channel. SIAM Journal on Computing 15 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schneider, J., Wattenhofer, R. (2010). What Is the Use of Collision Detection (in Wireless Networks)?. In: Lynch, N.A., Shvartsman, A.A. (eds) Distributed Computing. DISC 2010. Lecture Notes in Computer Science, vol 6343. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15763-9_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-15763-9_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15762-2
Online ISBN: 978-3-642-15763-9
eBook Packages: Computer ScienceComputer Science (R0)