Contention Resolution, With and Without a Global Clock

Abstract

In the Contention Resolution problem $n$ parties each wish to have exclusive use of a shared resource for one unit of time. The problem has been studied since the early 1970s, under a variety of assumptions on feedback given to the parties, how the parties wake up, knowledge of $n$, and so on. The most consistent assumption is that parties do not have access to a global clock, only their local time since wake-up. This is surprising because the assumption of a global clock is both technologically realistic and algorithmically interesting. It enriches the problem, and opens the door to entirely new techniques. Our primary results are: [1] We design a new Contention Resolution protocol that guarantees latency $$O\left(\left(n\log \log n{\log }^{(3)}n{\log }^{(4)}n\cdots {\log }^{({\log }^{\ast }n)}n\right)\cdot 2^{{\log }^{\ast }n}\right)\le n(\log \log n{)}^{1+o(1)}$$ in expectation and with high probability. This already establishes at least a roughly $\log n$ complexity gap between randomized protocols in GlobalClock and LocalClock. [2] Prior analyses of randomized ContentionResolution protocols in LocalClock guaranteed a certain latency with high probability, i.e., with probability $1-1/\text{poly}(n)$. We observe that it is just as natural to measure expected latency, and prove a $\log n$-factor complexity gap between the two objectives for memoryless protocols. The In-Expectation complexity is $\hat{I}˜(n\log n/\log \log n)$ whereas the With-High-Probability latency is $\hat{I}˜(n{\log }^{2}n/\log \log n)$. Three of these four upper and lower bounds are new. [3] Given the complexity separation above, one would naturally want a ContentionResolution protocol that is optimal under both the In-Expectation and With-High-Probability metrics. This is impossible! It is even impossible to achieve In-Expectation latency $o(n{\log }^{2}n/(\log \log n{)}^2)$ and With-High-Probability latency $n{\log }^{O(1)}n$ simultaneously.