Contention Resolution, with and without a Global Clock

In the Contention Resolution problem n parties each wish to have exclusive use of a shared resource for one unit of time. A canonical example is n devices that each must broadcast a packet of information on a shared channel, but the same principles apply to other distributed systems. The problem has been studied since the early 1970s, under a variety of assumptions on feedback (collision detection, etc.) given to the parties, how the parties wake up (synchronized, adversarial, random), 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. In this paper we explore the power of the GlobalClock model and establish several new complexity separations, both between GlobalClock and the usual model, and within the LocalClock model. Our primary results are: GlobalClock vs. LocalClock. We design a new Contention Resolution protocol that guarantees latency  O((nloglognlog(3) nlog(4) n⋯ log(log* n) n)· 2log* n),   which is n(loglogn)1+o(1), in expectation and with high probability. This already establishes at least a roughly-logn complexity gap between randomized protocols in GlobalClock and LocalClock. In-Expectation vs. With-High-Probability. Prior analyses of randomized Contention Resolution protocols in LocalClock guaranteed a certain latency with high probability, i.e., with probability 1−1/poly(n). We observe that it is just as natural to measure expected latency, and prove a logn-factor complexity gap between the two objectives for memoryless protocols. The In-Expectation complexity is Θ(n logn/loglogn) whereas the With-High-Probability latency is Θ(nlog2 n/loglogn). Three of these four upper and lower bounds are new. No Universally Optimal Protocols. Given the complexity separation above, one would naturally want a Contention Resolution 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(nlog2 n/(loglogn)2) and With-High-Probability latency nlogO(1) n simultaneously.