Document Open Access Logo

Leader Election in Unreliable Radio Networks

Authors Mohsen Ghaffari, Calvin Newport

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.138.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Mohsen Ghaffari
Calvin Newport

Cite As Get BibTex

Mohsen Ghaffari and Calvin Newport. Leader Election in Unreliable Radio Networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 138:1-138:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.138

Abstract

The dual graph model describes a radio network that contains both reliable and unreliable links. In recent years, this model has received significant attention by the distributed algorithms community [Kuhn/Lynch/Newport/Oshman/Richa, PODC 2010; Censor-Hillel/Gilbert/Kuhn/Lynch/Newport, Dist. Comp. 2014; Ghaffari/Haeupler/Lynch/Newport, DISC 2012; Ghaffari/Lynch/Newport, PODC 2013; Ghaffir/Kantor/Lynch/Newport, PODC 2014; Newport, DISC 2014; Ahmadi/Ghodselahi/Kuhn/Molla, OPODIS 2015; Lynch/Newport, PODC 2015]. Due to results in [Ghaffari/Lynch/Newport, PODC 2013], it is known that leader election plays a key role in enabling efficient computation in this difficult setting: a leader can synchronize the network in such a manner that most problems can be subsequently solved in time similar to the classical radio network model that lacks unreliable links. The feasibility of efficient leader election in the dual graph model, however, was left as an important open question. In this paper, we answer this question. In more detail, we prove new upper and lower bound results that characterize the complexity of leader election in this setting. By doing so, we reveal a surprising dichotomy: (1) under the assumption that the network size n is in the range 1 to N, where N is a large upper bound on the maximum possible network size (e.g., the ID space), leader election is fundamentally hard, requiring ~Omega(sqrt(N)) rounds to solve in the worst-case; (2) under the assumption that n is in the range 2 to N, however, the problem can be solved in only ~O(D) rounds, for network diameter D, matching the lower bound for leader election in the standard radio network model (within log factors) [Ghaffari/Haeupler, SODA 2013].

Subject Classification

Keywords
  • Radio Networks
  • Leader Election
  • Unreliability
  • Randomized Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, and Anisur Rahaman Molla. The cost of global broadcast in dynamic radio networks. In Proceedings of the International Conference on Principles of Distributed Systems, 2015. Google Scholar
  2. N. Alon, A. Bar-Noy, N. Linial, and D. Peleg. A Lower Bound for Radio Broadcast. Journal of Computer and System Sciences, 43(2):290-298, 1991. Google Scholar
  3. Reuven Bar-Yehuda, Oded Goldreigch, and 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, 45(1):104-126, 1992. Google Scholar
  4. Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch, and Calvin Newport. Structuring unreliable radio networks. Distributed Computing, 27(1):1-19, 2014. Google Scholar
  5. I. Chlamtac and S. Kutten. On Broadcasting in Radio Networks-Problem Analysis and Protocol Design. IEEE Transactions on Communications, 33(12):1240-1246, 1985. Google Scholar
  6. A. E. F. Clementi, A. Monti, and R. Silvestri. Round Robin is Optimal for Fault-Tolerant Broadcasting on Wireless Networks. Journal of Parallel and Distributed Computing, 64(1):89-96, 2004. Google Scholar
  7. Mohsen Ghaffari and Bernhard Haeupler. Near optimal leader election in multi-hop radio networks. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2013. Google Scholar
  8. Mohsen Ghaffari, Bernhard Haeupler, Nancy Lynch, and Calvin Newport. Bounds on contention management in radio networks. In The International Symposium on Distributed Computing (DISC), 2012. Google Scholar
  9. Mohsen Ghaffari, Erez Kantor, Nancy Lynch, and Calvin Newport. Multi-message broadcast with Abstract MAC layers and unreliable links. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2014. Google Scholar
  10. Mohsen Ghaffari, Nancy Lynch, and Calvin Newport. The cost of radio network broadcast for different models of unreliable links. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2013. Google Scholar
  11. Fabian Kuhn, Nancy Lynch, and Calvin Newport. Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication. In Proceedings of the ACM Symposium on the Principles of Distributed Computing (PODC), 2009. Google Scholar
  12. Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, and Andrea Richa. Broadcasting in unreliable radio networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2010. Google Scholar
  13. E. Kushilevitz and Y. Mansour. An Ω(D$$1log(N/D)) Lower Bound for Broadcast in Radio Networks. SIAM Journal on Computing, 27(3):702-712, 1998. Google Scholar
  14. Nancy Lynch and Calvin Newport. A (truly) local broadcast layer for unreliable radio networks. In Proceedings of the ACM Conference on Distributed Computing, 2015. Google Scholar
  15. Calvin Newport. Lower bounds for radio networks made easy. In Proceedings of the International Symposium on Distributed Computing (DISC), 2014. Google Scholar
  16. Calvin Newport. Lower bounds for structuring unreliable radio networks. In Proceedings of the International Symposium on Distributed Computing (DISC), 2014. Google Scholar
  17. Calvin Newport, David Kotz, Yougu Yuan, Robert S Gray, Jason Liu, and Chip Elliott. Experimental Evaluation of Wireless Simulation Assumptions. Simulation, 83(9):643-661, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact