Singletons for simpletons revisiting windowed backoff with Chernoff bounds

DOI10.1016/J.TCS.2022.01.026MaRDI QIDQ2078614zbMATH OpenOpenAlexFDO

Authors Qian M. Zhou, Alice Calvert, Maxwell Young

Publication date 1 March 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic simplicityexponential backoffrandomized algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Singletons for simpletons: revisiting windowed backoff with Chernoff bounds
• Simplified Chernoff bounds with powers-of-two probabilities
• A reversion of the Chernoff bound
• Slight improvements of the Singleton bound
• Efficient computation of tight approximations to Chernoff bounds
• scientific article; zbMATH DE number 437558
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• A contribution to the theory of Chernoff bounds
• Bounding the scaling window of random constraint satisfaction problems

Cites work

• A better wake-up in radio networks
• A jamming-resistant MAC protocol for multi-hop wireless networks
• A jamming-resistant MAC protocol for single-hop wireless networks
• Analysis of Backoff Protocols for Multiple Access Channels
• Analysis of practical backoff protocols for contention resolution with multiple servers
• Asynchronous shared channel
• Automata, Languages and Programming
• Balanced Allocations
• Balanced Allocations: The Heavily Loaded Case
• Balls and bins: A study in negative dependence
• Competitive and fair throughput for co-existing networks under adversarial interference
• Concentration of Measure for the Analysis of Randomized Algorithms
• Contention resolution in a non-synchronized multiple access channel
• Contention resolution on a fading channel
• Contention resolution on multiple channels with collision detection
• Contention resolution with constant expected delay
• Contention Resolution with Heterogeneous Job Sizes
• Contention resolution with log-logstar channel accesses
• Efficient Schemes for Parallel Communication
• Exponential separations in the energy complexity of leader election
• Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel
• How asymmetry helps load balancing
• How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel
• Multiple-choice balanced allocation in (almost) parallel
• Probability and Computing
• Sade: competitive MAC under adversarial SINR
• Scalable wake-up of multi-channel single-hop radio networks
• Scaling exponential backoff: constant throughput, polylogarithmic channel-access attempts, and robustness
• Stochastic Contention Resolution With Short Delays
• The cost of synchronizing multiple-access channels
• The energy complexity of broadcast
• The Wake‐Up Problem in MultiHop Radio Networks
• Tight bounds for parallel randomized load balancing, extended abstract
• Unbounded contention resolution in multiple-access channels
• Windowed backoff algorithms for WiFi: theory and performance under batched arrivals

This page was built for publication: Singletons for simpletons revisiting windowed backoff with Chernoff bounds

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