English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study two fundamental communication primitives: broadcasting and leaderelection in the classical model of multi-hop radio networks with unknowntopology and without collision detection mechanisms.  It has been known for almost 20 years that in undirected networks with nnodes and diameter D, randomized broadcasting requires Omega(D log n/D + log^2n) rounds in expectation, assuming that uninformed nodes are not allowed tocommunicate (until they are informed). Only very recently, Haeupler and Wajc(PODC'2016) showed that this bound can be slightly improved for the model withspontaneous 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 fasteralgorithm 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 broadcastingalgorithm whenever D is polynomial in n.  Furthermore, our approach can be applied to design a new leader electionalgorithm that matches the performance of our broadcasting algorithm.Previously, all fast randomized leader election algorithms have been usingbroadcasting as their subroutine and their complexity have been asymptoticallystrictly bigger than the complexity of broadcasting. In particular, the fastestpreviously 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 withhigh 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 ispolynomial in n.

Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks