Linear-latency contention resolution in the GlobalClock model

From papers

Consider randomized acknowledgment-based protocols in the GlobalClock\textsf{GlobalClock}{} model. In the finite setting, latency concerns completing contention resolution for the participating parties; in the unbounded setting, utilization at rate λ\lambda means that there is a potential function Φ\Phi such that waking up nn' parties increases Φ\Phi by at most n/λn'/\lambda, sufficiently large potential decreases by 1+ϵ1+\epsilon in expectation per further time step for some ϵ>0\epsilon>0, and bounded potential leaves only O(1)O(1) unsuccessful parties.

GlobalClock contention-resolution conjecture. In the finite setting, there exists a protocol with latency O(n)O(n) with high probability against an adaptive adversary. In the unbounded setting, there exists a protocol that utilizes the shared resource at some rate λ\lambda, even against an adaptive adversary.

The conjecture proposes that the current n(loglogn)1+o(1)n(\log\log n)^{1+o(1)} high-probability latency bound in the GlobalClock model can be improved to linear latency, while retaining robustness against adaptive adversaries. The source does not provide evidence that either assertion has been resolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Zixi Cai, Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie and Ben Plosk, “Contention Resolution, With and Without a Global Clock”, arXiv:2602.12070 (2026).

Solutions 0

No solutions have been posted yet.