Linear-latency contention resolution in the GlobalClock model
Linear-latency contention resolution in the GlobalClock model
Consider randomized acknowledgment-based protocols in the model. In the finite setting, latency concerns completing contention resolution for the participating parties; in the unbounded setting, utilization at rate means that there is a potential function such that waking up parties increases by at most , sufficiently large potential decreases by in expectation per further time step for some , and bounded potential leaves only unsuccessful parties.
GlobalClock contention-resolution conjecture. In the finite setting, there exists a protocol with latency with high probability against an adaptive adversary. In the unbounded setting, there exists a protocol that utilizes the shared resource at some rate , even against an adaptive adversary.
The conjecture proposes that the current 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
Sign in to submit a solution.
No solutions have been posted yet.