Deterministic Leader Election in Anonymous Radio Networks
Article No.: 25, Pages 1 - 33
Abstract
Leader election is a fundamental task in distributed computing. It is a symmetry breaking problem, calling for one node of the network to become the leader, and for all other nodes to become non-leaders. We consider leader election in anonymous radio networks modeled as simple undirected connected graphs. Nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbours, or stay silent and listen. A node v hears a message from a neighbour w in a given round if v listens in this round and if w is its only neighbour transmitting in this round. If v listens in a round in which more than one neighbour transmits, then v hears noise that is different from any message and different from silence.
We assume that nodes are identical (anonymous) and execute the same deterministic algorithm. Under this scenario, symmetry can be broken only in one way: by different wake-up times of the nodes. In which situations is it possible to break symmetry and elect a leader using time as symmetry breaker? In order to answer this question, we consider configurations. A configuration is the underlying graph with nodes tagged by non-negative integers with the following meaning. A node can either wake up spontaneously in the round shown on its tag, according to some global clock, or can be woken up hearing a message sent by one of its already awoken neighbours. The local clock of a node starts at its wakeup and nodes do not have access to the global clock determining their tags. A configuration is feasible if there exists a distributed algorithm that elects a leader for this configuration.
Our main result is a complete algorithmic characterization of feasible configurations. More precisely, we design a centralized decision algorithm, working in polynomial time, whose input is a configuration and which decides if the configuration is feasible. Using this algorithm we also provide a dedicated deterministic distributed leader election algorithm for each feasible configuration that elects a leader for this configuration in time O(n2σ, where n is the number of nodes and σ is the difference between the largest and smallest tag of the configuration. We then ask the question whether there exists a universal deterministic distributed algorithm electing a leader for all feasible configurations. The answer turns out to be no, and we show that such a universal algorithm cannot exist even for the class of 4-node feasible configurations. We also prove that a distributed version of our decision algorithm cannot exist.
References
[1]
Dana Angluin. 1980. Local and global properties in networks of processors (Extended Abstract). In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28–30, 1980, Los Angeles, California, USA, Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton (Eds.). ACM, 82–93.
[2]
Hagit Attiya and Marc Snir. 1991. Better computing on the anonymous ring. J. Algorithms 12, 2 (1991), 204–238.
[3]
Hagit Attiya, Marc Snir, and Manfred K. Warmuth. 1988. Computing on an anonymous ring. J. ACM 35, 4 (1988), 845–875.
[4]
Reuven Bar-Yehuda, Oded Goldreich, and Alon Itai. 1992. On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. J. Comput. Syst. Sci. 45, 1 (1992), 104–126.
[5]
Paolo Boldi, Shella Shammah, Sebastiano Vigna, Bruno Codenotti, Peter Gemmell, and Janos Simon. 1996. Symmetry breaking in anonymous networks: Characterizations. In Fourth Israel Symposium on Theory of Computing and Systems, ISTCS 1996, Jerusalem, Israel, June 10–12, 1996, Proceedings. IEEE Computer Society, 16–26.
[6]
Paolo Boldi and Sebastiano Vigna. 1999. Computing anonymously with arbitrary knowledge. In Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, PODC,’99 Atlanta, Georgia, USA, May 3–6, 1999, Brian A. Coan and Jennifer L. Welch (Eds.). ACM, 181–188.
[7]
J. E. Burns. 1980. A Formal Model for Message Passing Systems. Technical Report TR-91. Computer Science Department, Indiana University.
[8]
John Capetanakis. 1979. Tree algorithms for packet broadcast channels. IEEE Trans. Inf. Theory 25, 5 (1979), 505–515.
[9]
Arnaud Casteigts, Yves Métivier, J. M. Robson, and Akka Zemmari. 2019. Deterministic leader election takes \(\Theta\)(D+log n) bit rounds. Algorithmica 81, 5 (2019), 1901–1920.
[10]
Bogdan S. Chlebus, Leszek Gasieniec, Anna Östlin, and John Michael Robson. 2000. Deterministic radio broadcasting. In Automata, Languages and Programming, 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9–15, 2000, Proceedings(Lecture Notes in Computer Science, Vol. 1853), Ugo Montanari, José D. P. Rolim, and Emo Welzl (Eds.). Springer, 717–728.
[11]
Bogdan S. Chlebus, Dariusz R. Kowalski, and Andrzej Pelc. 2012. Electing a leader in multi-hop radio networks. In Principles of Distributed Systems, 16th International Conference, OPODIS 2012, Rome, Italy, December 18–20, 2012. Proceedings(Lecture Notes in Computer Science, Vol. 7702), Roberto Baldoni, Paola Flocchini, and Binoy Ravindran (Eds.). Springer, 106–120.
[12]
Marek Chrobak, Leszek Gasieniec, and Wojciech Rytter. 2002. Fast broadcasting and gossiping in radio networks. J. Algorithms 43, 2 (2002), 177–189.
[13]
Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri. 2003. Distributed broadcast in radio networks of unknown topology. Theor. Comput. Sci. 302, 1–3 (2003), 337–364.
[14]
Artur Czumaj and Peter Davies. 2017. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25–27, 2017, Elad Michael Schiller and Alexander A. Schwarzmann (Eds.). ACM, 3–12.
[15]
Artur Czumaj and Peter Davies. 2018. Deterministic communication in radio networks. SIAM J. Comput. 47, 1 (2018), 218–240.
[16]
Dariusz Dereniowski and Andrzej Pelc. 2014. Leader election for anonymous asynchronous agents in arbitrary networks. Distributed Comput. 27, 1 (2014), 21–38.
[17]
Abdelouahid Derhab and Nadjib Badache. 2008. A self-stabilizing leader election algorithm in highly dynamic ad hoc mobile networks. IEEE Trans. Parallel Distrib. Syst. 19, 7 (2008), 926–939.
[18]
Yoann Dieudonné and Andrzej Pelc. 2016. Anonymous meeting in networks. Algorithmica 74, 2 (2016), 908–946.
[19]
Stefan Dobrev and Andrzej Pelc. 2004. Leader election in rings with nonunique labels. Fundam. Inform. 59, 4 (2004), 333–347. http://content.iospress.com/articles/fundamenta-informaticae/fi59-4-02.
[20]
Fabien Dufoulon, Janna Burman, and Joffroy Beauquier. 2018. Beeping a deterministic time-optimal leader election. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15–19, 2018(LIPIcs, Vol. 121), Ulrich Schmid and Josef Widder (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 20:1–20:17.
[21]
Michael Elkin and Guy Kortsarz. 2007. An improved algorithm for radio broadcast. ACM Trans. Algorithms 3, 1 (2007), 8:1–8:21.
[22]
Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio, and Nicola Santoro. 2004. Sorting and election in anonymous asynchronous rings. J. Parallel Distributed Comput. 64, 2 (2004), 254–265.
[23]
Greg N. Frederickson and Nancy A. Lynch. 1987. Electing a leader in a synchronous ring. J. ACM 34, 1 (1987), 98–115.
[24]
Emanuele G. Fusco and Andrzej Pelc. 2011. How much memory is needed for leader election. Distributed Comput. 24, 2 (2011), 65–78.
[25]
Iris Gaber and Yishay Mansour. 2003. Centralized broadcast in multihop radio networks. J. Algorithms 46, 1 (2003), 1–20.
[26]
Leszek Gasieniec, David Peleg, and Qin Xin. 2007. Faster communication in known topology radio networks. Distributed Comput. 19, 4 (2007), 289–300.
[27]
Christian Glacet, Avery Miller, and Andrzej Pelc. 2017. Time vs. information tradeoffs for leader election in anonymous trees. ACM Trans. Algorithms 13, 3 (2017), 31:1–31:41.
[28]
Albert G. Greenberg and Shmuel Winograd. 1985. A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. J. ACM 32, 3 (1985), 589–596.
[29]
J. Hayes. 1978. An adaptive technique for local distribution. IEEE Transactions on Communications 26, 8 (1978), 1178–1186.
[30]
Daniel S. Hirschberg and James B. Sinclair. 1980. Decentralized extrema-finding in circular configurations of processors. Commun. ACM 23, 11 (1980), 627–628.
[31]
Piotr Indyk. 2002. Explicit constructions of selectors and related combinatorial structures, with applications. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6–8, 2002, San Francisco, CA, USA, David Eppstein (Ed.). ACM/SIAM, 697–704. http://dl.acm.org/citation.cfm?id=545381.545475.
[32]
Rebecca Ingram, Tsvetomira Radeva, Patrick Shields, Saira Viqar, Jennifer E. Walter, and Jennifer L. Welch. 2013. A leader election algorithm for dynamic networks with causal clocks. Distributed Comput. 26, 2 (2013), 75–97.
[33]
Tomasz Jurdzinski, Miroslaw Kutylowski, and Jan Zatopianski. 2002. Efficient algorithms for leader election in radio networks. In Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, PODC 2002, Monterey, California, USA, July 21–24, 2002, Aleta Ricciardi (Ed.). ACM, 51–57.
[34]
Dariusz R. Kowalski and Andrzej Pelc. 2013. Leader election in ad hoc radio networks: A keen ear helps. J. Comput. Syst. Sci. 79, 7 (2013), 1164–1180.
[35]
Eyal Kushilevitz and Yishay Mansour. 1998. An omega(D log (N/D)) lower bound for broadcast in radio networks. SIAM J. Comput. 27, 3 (1998), 702–712.
[36]
Gérard Le Lann. 1977. Distributed systems - towards a formal approach. In Information Processing, Proceedings of the 7th IFIP Congress 1977, Toronto, Canada, August 8–12, 1977, Bruce Gilchrist (Ed.). North-Holland, 155–160.
[37]
Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann.
[38]
Gary L. Peterson. 1982. An O(n log n) unidirectional algorithm for the circular extrema problem. ACM Trans. Program. Lang. Syst. 4, 4 (1982), 758–762.
[39]
Boris Solomonovich Tsybakov and Viktor Alexandrovich Mikhailov. 1978. Free synchronous packet access in a broadcast channel with feedback. Problemy Peredachi Informatsii 14, 4 (1978), 32–59.
[40]
Dan E. Willard. 1986. Log-Logarithmic selection resolution protocols in a multiple access channel. SIAM J. Comput. 15, 2 (1986), 468–477.
[41]
Masafumi Yamashita and Tiko Kameda. 1989. Electing a leader when processor identity numbers are not distinct (Extended Abstract). In Distributed Algorithms, 3rd International Workshop, Nice, France, September 26–28, 1989, Proceedings(Lecture Notes in Computer Science, Vol. 392), Jean-Claude Bermond and Michel Raynal (Eds.). Springer, 303–314.
[42]
Masafumi Yamashita and Tsunehiko Kameda. 1996. Computing on anonymous networks: Part i-characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7, 1 (1996), 69–89.
Index Terms
- Deterministic Leader Election in Anonymous Radio Networks
Recommendations
Deterministic Leader Election in Anonymous Radio Networks
SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and ArchitecturesLeader election is a fundamental task in distributed computing. It is a symmetry breaking problem, calling for one node of the network to become the leader, and for all other nodes to become non-leaders. We consider leader election in anonymous radio ...
Four shades of deterministic leader election in anonymous networks
AbstractLeader election is one of the fundamental problems in distributed computing: a single node, called the leader, must be specified. This task can be formulated either in a weak way, where one node outputs leader and all other nodes output non-leader,...
Four Shades of Deterministic Leader Election in Anonymous Networks
SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and ArchitecturesLeader election is one of the fundamental problems in distributed computing: a single node, called the leader, must be specified. This task can be formulated either in a weak way, where one node outputs 'leader' and all other nodes output 'non-leader', ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
314 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 October 2022
Online AM: 26 March 2022
Accepted: 15 March 2022
Revised: 30 November 2021
Received: 20 July 2020
Published in TALG Volume 18, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Funding Sources
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- Research Chair in Distributed Computing of the Université du Québec en Outaouais
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 147Total Downloads
- Downloads (Last 12 months)34
- Downloads (Last 6 weeks)7
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format