Efficient algorithms for leader election in radio networks

ABSTRACT

We present energy efficient algorithms for leader election in single channel single-hop radio networks with no collision detection. We present a deterministic solution with sublogarithmic energy cost (the best previous result was O(log n)) and show a double logarithmic lower bound. We prove that this lower bound holds in a randomized case, in a certain sense.For the case, when the number n of active stations can be approximated in advance, we show a randomized algorithm with energy consumption O(log* n) that yields a result with high probability (the best previous result was O(log log n)).

REFERENCES

• 1: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection, Distributed Computing, v.5 n.2, p.67-71, September 1991 [doi>10.1007/BF02259748]
• 2: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
• 3: Jacir L. Bordim , JiangTao Cui , Tatsuya Hayashi , Koji Nakano , Stephan Olariu, Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks, Proceedings of the 10th International Symposium on Algorithms and Computation, p.215-224, December 16-18, 1999
• 4: I. Chlamtac, S. Kutten, On Broadcasting in Radio Networks --- Problem Analysis and Protocol Design, IEEE Trans. on Commun. 33 (1985), 1240-1246.
• 5: B. S. Chlebus, Randomized communication in radio networks, a chapter in "Handbook on Randomized Computing" P. M. Pardalos, S. Rajasekaran, J. H. Reif, J. D. P. Rolim, (Eds.), Kluwer Academic Publishers.
• 6: Anders Dessmark , Andrzej Pelc, Deterministic Radio Broadcasting at Low Cost, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.158-169, February 15-17, 2001
• 7: Pierre Fraigniaud , Andrzej Pelc , David Peleg , Stéphane Pérennes, Assigning labels in an unknown anonymous network with a leader, Distributed Computing, v.14 n.3, p.163-183, October, 2001 [doi>10.1007/PL00008935]
• 8: Leszek Gasieniec , Andrzej Lingas, On adaptive deterministic gossiping in ad hoc radio networks, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.689-690, January 06-08, 2002, San Francisco, California
• 9: Leszek Gąsieniec , Andrzej Pelc , David Peleg, The wakeup problem in synchronous broadcast systems (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.113-121, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343529]
• 10: Tatsuya Hayashi , Koji Nakano , Stephan Olariu, Randomized Initialization Protocols for Packet Radio Networks, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.544, April 12-16, 1999
• 11: Tomasz Jurdzinski , Miroslaw Kutylowski , Jan Zatopianski, Energy-Efficient Size Approximation of Radio Networks with No Collision Detection, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, p.279-289, August 15-17, 2002
• 12: T. Jurdziński, M. Kutyłowski, J. Zatopiański, Weak Communication in Radio Networks, Euro-Par'2002, Lecture Notes in Computer Science, Springer-Verlag, accepted paper.
• 13: Eyal Kushilevitz , Yishay Mansour, Computation in noisy radio networks, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.236-243, January 25-27, 1998, San Francisco, California, United States
• 14: Miroslaw Kutylowski , Krzysztof Lorys, Limitations of the QRQW and EREW PRAM Models, Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, p.310-321, December 18-20, 1996
• 15: Koji Nakano , Stephan Olariu, Randomized O (log log n)-Round Leader Election Protocols in Packet Radio Networks, Proceedings of the 9th International Symposium on Algorithms and Computation, p.209-218, December 14-16, 1998
• 16: K. Nakano, S. Olariu, Randomized leader election protocols for ad-hoc networks, Intern. Coll. on Structural Information and Communication Complexity (SIROCCO) '2000, Carleton Scientific, 253-267.
• 17: Koji Nakano , Stephan Olariu, Randomized Leader Election Protocols in Radio Networks with No Collision Detection, Proceedings of the 11th International Conference on Algorithms and Computation, p.362-373, December 18-20, 2000
• 18: Koji Nakano , Stephan Olariu, Energy-Efficient Initialization Protocols for Radio Networks with no Collision Detection, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.263, August 21-24, 2000
• 19: Koji Nakano , Stephan Olariu, Uniform Leader Election Protocols in Radio Networks, Proceedings of the 2001 International Conference on Parallel Processing, p.240-250, September 03-07, 2001
• 20: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 21: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 22: Dan E Willard, Log-logarithmic selection resolution protocols in a multiple access channel, SIAM Journal on Computing, v.15 n.2, p.468-477, May 1986 [doi>10.1137/0215032]
• 23: A. C-C. Yao, Probabilistic computations: towards a unified measure of complexity, ACM-SIAM Symposium on Foundations of Computer Science (FOCS) '77, 222-227.