Reproduce “Contention Resolution Against an Adversarial Scheduler” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Michael A. Bender, Martín Farach-Colton, Andrew Krapivin, Pritom Kundu, John Kuszmaul, Margaret Kuszmaul, William Kuszmaul, Jingxun Liang
The authors introduce Guess-a-Scale, a protocol for shared-channel access under adaptive scheduling. With a global clock and shared randomness, players use a fresh shared random guess of the active population to choose their broadcast probability, without channel feedback. Its expected live-step cost is at most 32(⌊log₂ n⌋+1)n; an oblivious-scheduler lower bound establishes Θ(1/log n) efficiency asymptotically, even with generous feedback.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.