{"id":"864dec6c-a2ae-462e-8bf5-bf3fa4498e0a","arxiv_id":"2507.15658","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Distributed asynchronous robot teams can explore any tree in 2n + O(k^2 2^k D) moves, and no asynchronous algorithm can beat competitive ratio Ω(log^2 k).","lead":"An algorithm for distributed, asynchronous teams of robots exploring an unknown tree runs in 2n + O(k^2 2^k D) moves, the first such guarantee with regret linear in tree depth, and a new lower bound shows any asynchronous collective exploration must have competitive ratio at least Ω(log^2 k). The paper connects collective exploration to layered graph traversal, an online-algorithm problem, and transfers recent breakthroughs there into the distributed-exploration setting.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 5.3's WLOG that the adversary never forks or deletes a leaf with z(t)=0 (footnote 6) is unproved and load-bearing; zero-mass forks can affect the potential D and future z-trajectory, so the bound L <= w*Lz may fail.","rationale":"The algorithm side (Theorem 3.1) is detailed and the accounting via Proposition 3.8 and Claim 6 is plausible; the distributed implementation is carefully specified. The lower bound is the fragile part. The assertion that the adversary may assume no zero-mass fork is used exactly once, at L <= w*Lz, and the footnote's justification is a single sentence about designer incentives. Because z is defined through a potential that depends on x and delta, a zero-mass fork is not a no-op: it changes the instance seen by z and can force movement. The later assertion Cost(x) >= 2^{-w}Lz also implicitly relies on the same WLOG. The reader's weakest_assumption identifies precisely this point, and I agree. The proposed exhaustive test would indicate whether the WLOG is actually false in the model, or merely unproved; either way a proof is needed. This is a conditional-accept situation, consistent with the reader's verdict.","tokens_in":23850,"tokens_out":22902,"duration_ms":246046,"concrete_test":"Implement the fractional algorithm z from (7) for width w=2 on layered instances of small depth (say D<=4), fixing x to an explicit (a,b)-overhead algorithm (for instance, the one obtained from Lemma 5.2 for a simple ACTE algorithm) and solving the OT minimization in (7) exactly by linear programming. Enumerate all layered instances; check whether any instance that maximizes Cost(z) forks a leaf with zℓ(t−1)=0. If so, construct the modified instance where that fork is delayed until zℓ>0 (or suppressed) and compare Cost(z). If delaying strictly lowers Cost(z), the WLOG is false and Proposition 5.3's proof fails. If exhaustive search finds no counterexample, the WLOG gains computational support but still requires a proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The lower bound (Theorem 3.2) reduces to Proposition 5.3. Its proof in Section 5.2 needs the inequality L <= w*Lz, where Lz counts nodes carrying nonzero z-mass. This is justified only by footnote 6: 'a leaf ℓ is never extended or forked at time t if zℓ(t)=0', with the reason that the input designer has no incentive to make a move that diminishes future options without incurring cost. That premise is not secure. The algorithm z(t) is defined by the minimization (7) involving the potential D(δ(t),x(t),z); forking a leaf with zℓ(t−1)=0 changes δ(t), the layer X(t), and the objective, and can make the minimizer move mass from elsewhere to the new children, incurring real OT↑ cost. Thus a zero-mass fork can be strictly profitable for the adversary, contradicting the claimed WLOG. If such forks are allowed, new children may inherit no z-mass, so L can exceed w*Lz; then the chain 2^{-w}Lz <= Cost(x) <= 2^{-(w+1)}Lz + bD breaks. Since a=c(k)/k and b=c(k), the Omega(log^2 k) conclusion depends on this gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies asynchronous collective tree exploration (ACTE) and its distributed variant (DACTE). The authors present a distributed algorithm that explores any n-node tree of depth D in at most 2n + O(k^2 2^k D) moves, together with a variant achieving O(k/log k)(n + kD) moves. They also prove a lower bound of Ω(log^2 k) on the competitive ratio of any ACTE algorithm, improving over the previous Ω(log k). The lower bound is obtained via a reduction to fractional layered graph traversal, building on the recent Bubeck–Coester–Rabani lower bound. The paper contains detailed proofs of the algorithm's correctness and of the lower-bound reduction.","tokens_in":24157,"tokens_out":29834,"duration_ms":323279,"significance":"If correct, the algorithmic contribution is a significant advance: it is the first distributed asynchronous exploration algorithm with regret linear in D, and it draws an interesting connection to deterministic layered graph traversal. The lower bound would also be a major improvement, linking ACTE to the randomized k-server lower bound. The paper is generally well written and the algorithm part is supported by thorough claims. However, the lower-bound proof rests on an unproved and questionable ``without loss of generality'' statement (discussed below), so the advertised Ω(log^2 k) bound is not yet established. The algorithmic part alone may still be publishable, but the central lower-bound claim needs repair.","major_comments":[{"comment":"The proof of Proposition 5.3 assumes, without proof, that the adversarial layered instance never forks a leaf ℓ at a time when zℓ(t)=0, and it uses this WLOG to conclude L ≤ wLz. This assumption is load-bearing: it is the only step that bounds the tree size L in terms of the support size Lz, and it feeds directly into the inequalities that yield Cost(x(·), L(·)) ≤ 2bD. The footnote's justification ('the designer ... has no reason to make a move that diminishes its future options') is not a proof: forking a zero-mass leaf can increase future options (the new children become active leaves), it changes the minimization domain X(t) and the potential D(δ(t),x(t),z) in (7), and it can force the minimizer to move mass from other leaves into the new children, incurring real OT↑ cost in (9). Moreover, the claimed inequality L ≤ wLz can fail when zero-mass forks are allowed: for width w=3, the adversary can keep a single positive leaf b and repeatedly fork the currently active zero-mass leaf, e.g., layers {b,c}, then {b,c1,c2}, then {b,c3,c4}, ..., deleting one child at each step. The underlying tree then has L ≈ 2D nodes while Lz = O(1), so L > wLz for large D. On such an instance the chain 2^{-w}Lz ≤ Cost(x) ≤ aL + bD does not imply 2^{-w}Lz ≤ 2^{-(w+1)}Lz + bD, and the conclusion Cost(x(·), L(·)) ≤ 2bD is not obtained. Since Proposition 5.3 is the basis of Theorem 3.2, this gap must be repaired, for instance by proving that zero-mass forks can be eliminated from any instance without increasing the final bound, or by establishing a direct bound on L in terms of Lz and Cost(x).","section":"Section 5.2, footnote 6"}],"minor_comments":[{"comment":"The inequality D(δ(t), x(t), z′) − D(δ(t), x(t−1), z′) ≤ OT(x(t−1), x(t)) appears to be missing a factor of 2: since a_+ − b_+ ≤ |a−b|, each summand is bounded by |(z′_u+δ_u(t)−2x_u(t)) − (z′_u+δ_u(t)−2x_u(t−1))| = 2|x_u(t)−x_u(t−1)|. The same issue occurs in the bound for B in the leaf-deletion case. This only affects the constant in the final bound (18bD would become a different constant), so the asymptotic claim is unaffected, but the proof as written is not fully correct.","section":"Section 5.2, Eq. (13)"},{"comment":"The lemma divides the robots into teams of size k′ or fewer and then applies the guarantee f(k′, n, D) to every team, including teams of size strictly smaller than k′. This implicitly requires that f(k, n, D) is non-decreasing in k, which is plausible for the algorithm presented but should be stated explicitly and justified.","section":"Lemma 3.3"},{"comment":"The assertion that any asynchronous greedy algorithm requires at least kn/2 robot moves on the comb tree is stated without proof; a short argument would improve the clarity of the claim.","section":"Section 3.3"},{"comment":"The entry 'This W ork' should read 'This work'.","section":"Table 1"},{"comment":"The statement 'at all times Σu δu(t) ≤ D' is inaccurate because δ(t) is a probability configuration and its total mass over all nodes is the expected depth plus one, which can reach D+1. The telescoping argument only needs the final-minus-initial difference to be at most D, which holds; the wording should be corrected.","section":"Section 5.2, telescoping argument"},{"comment":"The phrase 'consecutive branches can be forces to be explored' contains a typo: 'forces' should be 'forced'.","section":"Footnote 5"}],"recommendation":"major_revision","confidential_remarks":"The algorithmic part of the paper appears technically sound and interesting, and the exposition is generally careful. My main concern is the lower-bound proof in Section 5.2, specifically the WLOG in footnote 6. If this gap cannot be repaired, the advertised Ω(log^2 k) lower bound would have to be withdrawn or substantially weakened, although the distributed algorithm alone might still merit publication. I would encourage the editor to seek a second opinion on the lower-bound proof, as the issue is subtle and load-bearing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The algorithm half of this paper is a real advance; the lower-bound half is an interesting and plausible construction that is not yet fully rigorous.\n\nThe main positive result, a distributed asynchronous CTE algorithm with 2n + O(k^2 2^k D) moves and a O(k/log k)-competitive variant, is new and appears correct. The reduction to Burley's deterministic layered graph traversal is elegant, and the formal distributed implementation in the appendix is careful—Claims 1-6 check out. The extensions to weighted trees and continuous speeds are useful, and the paper is honest about why randomized LGT can't be plugged in.\n\nThe lower bound (Ω(log^2 k) for ACTE) is the more delicate part. The reduction from ACTE to fractional LGT, and the potential-based construction of z, are genuinely new and worth studying. But the proof of Proposition 5.3 has a load-bearing WLOG: footnote 6 assumes the adversary never forks a leaf with z_l(t)=0, and the justification is a single sentence. This WLOG is needed to get L ≤ wL_z, which drives the bound Cost(x) ≤ 2bD. It's not obviously wrong, and the inequality (9) in the fork case seems to handle zero-mass forks, but the WLOG as stated is not proven. An adversary could in principle exploit zero-mass forks to change δ and alter z's future trajectory. I'd want to see a proper argument that such forks can be eliminated without weakening the instance, or a replacement for the L ≤ wL_z step. There's also a smaller gap in the proof of (4): the existence of the witness leaf ℓ' is asserted without full argument.\n\nThe abstract's 'average-case 1-competitive' phrasing is sloppy, but minor.\n\nBottom line: the algorithmic result deserves publication now; the lower bound is plausible but needs repair. If you work on collective exploration or online algorithms, read this paper. For peer review, I'd send it to a serious referee; the results are important and the core is serious, but I'd ask for a complete proof of the WLOG and the (4) step before accepting.","headline":"The algorithm half is a real advance; the lower-bound half is plausible but not yet rigorous.","tokens_in":24642,"tokens_out":24735,"would_cite":true,"duration_ms":266591,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that robot teams can explore unknown trees asynchronously with regret linear in depth, and that no asynchronous algorithm, even with central communication, beats $\\Omega(\\log^2 k)$ overhead.","keywords":["collective tree exploration","asynchronous algorithms","distributed algorithms","whiteboard communication","layered graph traversal","competitive ratio","lower bound","mobile agents"],"falsifier":"Search, for example by exhaustive enumeration for width $w = 3$ or $4$, for a layered tree instance in which the adversary strictly improves its outcome by forking or deleting a leaf $\\ell$ at a time when $z_\\ell(t) = 0$, compared with any instance that avoids such moves; finding one would invalidate the without-loss-of-generality step and could open the way to a faster ACTE algorithm. Alternatively, any ACTE algorithm with $c(k) = o(\\log^2 k)$ would directly refute Theorem 3.2.","tokens_in":23628,"feed_emoji":"🤖","tokens_out":12305,"duration_ms":121319,"temperature":0.7,"pith_summary":"The paper introduces DACTE, a model where an adversary decides which of $k$ robots moves next and robots learn about the tree only by reading and writing whiteboards at the nodes. It establishes two results. First, a distributed asynchronous algorithm explores any unknown tree with $n$ nodes and depth $D$ in at most $2n + O(k^2 2^k D)$ moves, and a variant achieves $O(k/\\log k)(n + kD)$ moves, so the regret term is linear in $D$ and asymptotically optimal in the average case where random trees satisfy $n = \\Theta(D^2)$. Second, every asynchronous collective tree exploration algorithm, even one with centralized all-to-all communication, that explores in $O(c(k)(n + kD))$ moves must have $c(k) = \\Omega(\\log^2 k)$, improving the earlier $\\Omega(\\log k)$ bound. Together these claims say that asynchrony alone does not preclude efficient distributed exploration, while the competitive overhead of any asynchronous team grows at least polylogarithmically with team size.","feed_headline":"Asynchronous robot teams explore trees with regret linear in depth","feed_subtitle":"Whiteboard-only robots hit 2n + O(k^2 2^k D) moves; no async strategy beats Ω(log^2 k) overhead.","key_machinery":"The algorithm rests on locally-greedy exploration with targets: a moving robot always crosses an unexplored edge if one is present, otherwise it moves toward its current target node. A potential $P(t) = \\sum_i d(\\text{position}_i(t), \\text{target}_i(t))$ converts target movement into an explored-edge count, giving the bound that after $M$ moves at least $(M - \\text{total target movement})/2$ edges are explored. The targets form a single shared sequence produced by a deterministic layered graph traversal algorithm run on the layered instance $L(h)$ whose leaves are the active children of the current target; whiteboards at target nodes propagate the sequence to follower robots. The lower bound rests on fractional tree traversal: a configuration $x(t)$ is the distribution of $k$ robots over the current layer, and the paper converts any ACTE algorithm into a fractional algorithm with $(c(k)/k, c(k))$ overhead, then applies a potential $D(\\delta, x, z) = \\sum_u (z_u + \\delta_u - 2x_u)_+$, where $\\delta(t)$ is the distribution of a uniformly random depth-first search, to define a converted fractional algorithm $z(t)$ that removes the additive size term and is $O(w^2)$-competitive.","core_discovery":"The central claim is that the asynchronous adversary is not a barrier to distributed collective exploration. The paper proves that a locally-greedy exploration rule whose robot targets are generated by a deterministic layered graph traversal on the 'active frontier' of partially explored subtrees explores in $2n + k c_k D$ moves, where $c_k$ is the competitive ratio of the traversal subroutine; with the best known deterministic subroutine this is $2n + O(k^2 2^k D)$, and a team-splitting argument converts it into $O(k/\\log k)(n + kD)$. On the negative side, the paper proves that any asynchronous collective tree exploration algorithm with cost at most $O(c(k)(n + kD))$ must satisfy $c(k) = \\Omega(\\log^2 k)$. The proof reduces ACTE to fractional layered graph traversal: an algorithm with sub-polylog overhead would yield fractional tree traversal with $o(w^2)$ competitive ratio, contradicting the $\\Omega(w^2)$ lower bound.","pith_inferences":["Editorial extension: the paper's conjecture that randomization cannot improve collective exploration against an adaptive adversary, while centralized communication can, frames distributed algorithms as the 'deterministic' counterpart of online algorithms; testing this parallel on other multi-agent problems, such as collective metrical task systems, is a natural next step.","Editorial extension: the potential-based reduction in Proposition 5.3 may transfer the $\\Omega(w^2)$ fractional lower bound to other problems with additive size terms and time-varying metric spaces; the paper hints at this applicability but does not develop it.","Editorial extension: the gap between the $O(k/\\log k)$ upper bound and the $\\Omega(\\log^2 k)$ lower bound leaves room for a distributed algorithm that avoids the $2^k$ factor of deterministic layered graph traversal, which would need a different target-selection mechanism."],"forward_implications":["A distributed, asynchronous robot team can explore with regret linear in tree depth, so the asynchronous adversary is compatible with near-optimal exploration rather than an obstacle.","Because a uniformly random $n$-node tree has depth $\\Theta(\\sqrt{n})$ with high probability, the $2n + O(k^2 2^k D)$ bound is asymptotically optimal, i.e. $1$-competitive, in average-case complexity.","The same linear-regret guarantees extend to weighted trees and continuous robot speeds, since linear guarantees are scale-invariant under the paper's reduction lemmas.","No asynchronous algorithm, centralized or distributed, can have competitive ratio $o(\\log^2 k)$ when measured as $O(c(k)(n + kD))$; this improves the previous $\\Omega(\\log k)$ lower bound.","Splitting the team into $\\lceil \\ln k \\rceil$ robots and applying the generalized pigeonhole principle yields the $O(k/\\log k)$-competitive variant."],"supporting_citations":[{"why":"Defines the distributed whiteboard model of collective tree exploration and gives the synchronous $O(k/\\log k)$ algorithm whose failure under asynchrony motivates the new DACTE algorithm.","marker":"[FGKP06]"},{"why":"Supplies the $O(w 2^w)$-competitive deterministic layered graph traversal used as the target-generating subroutine, yielding the $2n + O(k^2 2^k D)$ guarantee.","marker":"[Bur96]"},{"why":"Proves the $\\Omega(w^2)$ lower bound for fractional layered graph traversal that the new ACTE lower bound contradicts.","marker":"[BCR23]"},{"why":"Provides the centralized asynchronous $O(kD)$-regret algorithm and the conversion (Lemma 5.2) from ACTE guarantees to fractional tree traversal overhead used in the lower-bound proof.","marker":"[CM24b]"},{"why":"Supplies the locally-greedy potential lemma (Proposition 3.8) and the team-splitting argument that the competitive-ratio variant generalizes.","marker":"[Cos24]"}],"fun_headline_variants":["Async tree exploration: linear regret in depth, new Ω(log² k) lower bound","Distributed async exploration: O(k/log k) competitive, Ω(log² k) bound","Asynchronous collective exploration: near-optimal regret with whiteboard sharing","Tree search by async agents: 2n + O(k²2^kD) moves, Ω(log² k) limit"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the footnote-6 assumption in the lower-bound proof: an optimal adversary never forks or deletes a leaf at a moment when the constructed fractional algorithm $z$ gives that leaf zero probability mass; if an adversary could benefit from such moves, the inequality $L \\le w \\cdot L_z$ and the $\\Omega(\\log^2 k)$ bound could fail.","fun_headline_variants_meta":{"raw":{"variants":["Async tree exploration: linear regret in depth, new Ω(log² k) lower bound","Distributed async exploration: O(k/log k) competitive, Ω(log² k) bound","Asynchronous collective exploration: near-optimal regret with whiteboard sharing","Tree search by async agents: 2n + O(k²2^kD) moves, Ω(log² k) limit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001468,"raw_usage":{"total_tokens":5940,"prompt_tokens":1017,"completion_tokens":4923,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":633,"completion_tokens_details":{"reasoning_tokens":4827}},"tokens_in":633,"tokens_out":4923,"duration_ms":41020,"temperature":1.0,"reasoning_tokens":4827,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:28:26.175207+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search, for example by exhaustive enumeration for width $w = 3$ or $4$, for a layered tree instance in which the adversary strictly improves its outcome by forking or deleting a leaf $\\ell$ at a time when $z_\\ell(t) = 0$, compared with any instance that avoids such moves; finding one would invalidate the without-loss-of-generality step and could open the way to a faster ACTE algorithm. Alternatively, any ACTE algorithm with $c(k) = o(\\log^2 k)$ would directly refute Theorem 3.2.","supporting_citations":[],"review_version":1}