×

Probabilistic algorithms for the wakeup problem in single-hop radio networks. (English) Zbl 1019.68813

Bose, Prosenjit (ed.) et al., Algorithms and computation. 13th international symposium, ISAAC 2002, Vancouver, BC, Canada, November 21-23, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2518, 535-549 (2002).
Summary: We consider the problem of waking up \(n\) processors of a completely broadcast system. We analyze this problem in both globally and locally synchronous models, with or without \(n\) being known to processors and with or without labeling of processors. The main question we answer is: how fast we can wake all the processors up with probability \(1-\varepsilon\) in each of these eight models. In 2000, L. Gasieniec et al. described a logarithmic waking algorithm for the strongest set of assumptions, while for weaker models only linear and quadratic algorithms were obtained. We prove that in the weakest model (local synchronization, no knowledge of \(n\) or labeling) the best waking time is \(O(n/\log n)\). We also show logarithmic or polylogarithmic waking algorithms for all stronger models, which in some cases gives an exponential improvement over previous results.
For the entire collection see [Zbl 1007.00050].

MSC:

68W20 Randomized algorithms
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: Link