Linear-latency contention resolution in the GlobalClock model

Less than 1 year old · traced to

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 n′n' 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(log⁡log⁡n)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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.