How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness

DOI10.1137/1.9781611974331.CH47zbMath1410.68066OpenAlexW4255432856MaRDI QIDQ4575625

Maxwell Young, Jeremy T. Fineman, Michael A. Bender

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch47

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20)

Related Items (11)

Packet latency of deterministic broadcasting in adversarial multiple access channels ⋮ Sade: competitive MAC under adversarial SINR ⋮ Interactive communication with unknown noise rate ⋮ Adversarial multiple access channels with individual injection rates ⋮ Restrained medium access control on adversarial shared channels ⋮ Bankrupting Sybil despite churn ⋮ Windowed backoff algorithms for WiFi: theory and performance under batched arrivals ⋮ Ordered and delayed adversaries and how to work against them on a shared channel ⋮ Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses ⋮ A resource-competitive jamming defense ⋮ Singletons for simpletons revisiting windowed backoff with Chernoff bounds

This page was built for publication: How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness