Contention Resolution with Log-Logstar Channel Accesses
Bender, M., Kopelowitz, T., Pettie, S., & Young, M. (2016). Contention Resolution with Log-Logstar Channel Accesses. 48th ACM Symposium on Theory of Computing (STOC). Cambridge, MA.
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.
In this paper, we address these shortcomings by offering a new backoff protocol for a shared com- munications channel that guarantees expected constant throughput with only O(log(log* N)) access attempts in expectation. Central to this result are new algorithms for approximate counting and leader election with the same performance guarantees.