Contention resolution with log-logstar channel accesses
Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, Maxwell Young · 2016
For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices seek access to a shared resource. Surprisingly, despite this history, the performance of standard backoff is poor under worst-case scheduling of demands on the resource: (i) subconstant throughput can occur under plausible scenarios, and (ii) each of N devices requires Omega(log N) access attempts before obtaining the resource.