Exploiting spontaneous transmissions for broadcasting and leader election in radio networks

DOI10.1145/3087801.3087825zbMATH Open1380.68018arXiv1703.01859OpenAlexW2594542601MaRDI QIDQ5368935FDOQ5368935

Authors: P. Davies, Artur Czumaj 

Publication date: 11 October 2017

Published in: Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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 Omega(D log n/D + log^2 n) rounds in expectation, 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 slightly improved for the model with spontaneous transmissions, providing an O(D log n loglog n / log D + log^O(1) n)-time broadcasting algorithm. In this paper, we give a new and faster algorithm that completes broadcasting in O(D log n/log D + log^O(1) n) time, with high probability. This yields the first optimal O(D)-time broadcasting algorithm whenever D is polynomial in n. 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 been using broadcasting as their subroutine and their complexity have been asymptotically strictly bigger 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{loglog n, log n/D} + log^O(1) n)-time with high probability. Our new algorithm requires O(D log n / log D + log^O(1) n) time with high probability, and it achieves the optimal O(D) time whenever D is polynomial in n.

Full work available at URL: https://arxiv.org/abs/1703.01859

Recommendations

• Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
• Brief announcement: Optimal leader election in multi-hop radio networks
• Near optimal leader election in multi-hop radio networks
• Broadcasting in undirected ad hoc radio networks
• Broadcasting in undirected ad hoc radio networks

zbMATH Keywords

broadcastingleader electionradio networks

Mathematics Subject Classification ID

Distributed algorithms (68W15) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Cited In (8)

• Deterministic blind radio networks
• Beeping a deterministic time-optimal leader election
• Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election
• Brief announcement: Optimal leader election in multi-hop radio networks
• Near optimal leader election in multi-hop radio networks
• Finding the size and the diameter of a radio network using short labels
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks

This page was built for publication: Exploiting spontaneous transmissions for broadcasting and leader election in radio networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368935)