Tsvi Kopelowitz: A Class of $O(\log\log^* N)$ Problems in Distributed Computing: Contention Resolution, Counting, and Leader Election

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 talk, we will  address these shortcomings by offering a new backoff protocol for a shared communications 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.

This is joint work with Michael Bender, Seth Pettie, and Maxwell Young.