Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Exploiting spontaneous transmissions for broadcasting and leader election in radio networks

Tools
- Tools
+ Tools

Czumaj, Artur and Davies, Peter (2021) Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. Journal of the ACM, 68 (2). 13. doi:10.1145/3446383 ISSN 0004-5411. [ 🗎 Public]. [ (✓) hoa:511 ]

[img]
Preview
PDF
WRAP-exploiting-spontaneous-transmissions-broadcasting-leader-election-networks-Czumaj-2020.pdf - Accepted Version - Requires a PDF viewer.

Download (1397Kb) | Preview
Official URL: https://doi.org/10.1145/3446383

Request Changes to record.

Abstract

We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology and without collision detection mechanisms. It has been known for almost 20 years that in undirected networks with n nodes and diameter D, randomized broadcasting requires Ω(D log n/D + log2 n) rounds, assuming that uninformed nodes are not allowed to communicate (until they are informed). Only very recently, Haeupler and Wajc (PODC'2016) showed that this bound can be improved for the model with spontaneous transmissions, providing an O(D log n log log n/log D + logO(1) n)-time broadcasting algorithm. In this article, we give a new and faster algorithm that completes broadcasting in O(D log n/log D + logO(1) n) time, succeeding with high probability. This yields the first optimal O(D)-time broadcasting algorithm whenever n is polynomial in D.

Furthermore, our approach can be applied to design a new leader election algorithm that matches the performance of our broadcasting algorithm. Previously, all fast randomized leader election algorithms have used broadcasting as a subroutine and their complexity has been asymptotically strictly larger than the complexity of broadcasting. In particular, the fastest previously known randomized leader election algorithm of Ghaffari and Haeupler (SODA'2013) requires O(D log n/D min {log log n, log n/D} + logO(1) n)-time, succeeding with high probability. Our new algorithm again requires O(D log n/log D + logO(1) n) time, also succeeding with high probability.

Item Type: Journal Article
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title: Journal of the ACM
Publisher: Association for Computing Machinery, Inc.
ISSN: 0004-5411
Official Date: January 2021
Dates:
DateEvent
January 2021Published
19 December 2019Accepted
Volume: 68
Number: 2
Article Number: 13
DOI: 10.1145/3446383
Status: Peer Reviewed
Publication Status: Published
Reuse Statement (publisher, data, author rights): "© ACM, 2020. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Journal of the ACM, VOL 68, ISS 2, (Jan 2021) http://doi.acm.org/10.1145/3446383
Access rights to Published version: Restricted or Subscription Access
Date of first compliant deposit: 17 March 2020
Date of first compliant Open Access: 17 March 2020
Related URLs:
  • Publisher
  • Related item in WRAP

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us