Reproduce “Asynchronous Collective Tree Exploration: a Distributed Algorithm, and a new Lower Bound” 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
Romain Cosson, Laurent Massoulié
The authors present a distributed algorithm for asynchronous exploration of an unknown rooted tree, where agents coordinate through local whiteboards and follow shared exploration targets. For n nodes, depth D, and k agents, it uses at most 2n+O(k²2ᵏD) moves. A separate lower bound gives Ω(log²k) competitive ratio even with centralized communication, leaving a gap to the upper bounds.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.