{"id":"09c73b67-3b15-42b0-b42c-d0aaaa6de47e","arxiv_id":"1908.00914","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"CIRCLE-TAG, an online multi-robot information-dissemination algorithm, has competitive ratio O(H max{M, sqrt(MH)}) for arbitrary deployments and O(M) for uniform random deployments in unbounded environments.","lead":"This paper studies how a team of robots with limited communication range can spread a message to all other robots in an open, unbounded area when nobody knows where anyone is. The authors propose an algorithm, CIRCLE-TAG, and prove bounds on how much slower it is than a perfect planner that knew all starting positions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Round-time bound Proposition 1 is unreviewed and the random-deployment M lower bound misuses an RGG connectivity condition, so the O(M) ratio is not established.","rationale":"The reader identified Proposition 1 and the placeholder technical report as the weakest assumption, and I agree that the deferred proof is the structural keystone: every lemma sum uses the round-time bound, so without it the entire competitive analysis collapses. That alone justifies CONDITIONAL/UNVERDICTED rather than ACCEPT. But I also found a second, independent and in-paper checkable issue in Theorem 2: Lemma 4 says G(n,r) is connected with high probability when r >= sqrt(2 log n / n) (unit disk). The paper then asserts that this gives M = O(L sqrt(log n / n)) for points in a disk of radius L. That is not what Lemma 4 states: connectivity of the random geometric graph gives a sufficient radius for connectivity, and although the MST longest edge is the critical radius for connectivity, the asymptotic order is L/sqrt(n) with a logarithmic factor appearing only near the threshold and for worst-case points; for uniform points the longest MST edge is L*sqrt(log n / n) only if points are Poisson on the whole plane with a fixed expected degree, whereas on a disk the relevant nearest-neighbor scale is L/sqrt(n). In fact for uniform points in a disk the maximum nearest-neighbor distance is Theta(L sqrt(log n / n)) while the MST max edge is Theta(L / sqrt(n)), so the two differ by sqrt(log n). Using the larger substituted value makes the claimed competitive ratio O(M) with M taken as the larger quantity, so the theorem's asymptotic constant is off by sqrt(log n). This is a correctness-risk issue internal to the paper, not merely a disagreement with consensus. The simulations and field experiment demonstrate feasibility but do not validate the asymptotic competitive ratios, so they do not repair the proof gap.","tokens_in":9289,"tokens_out":1724,"duration_ms":16046,"concrete_test":"Set L = 1, n = 10^4, sample 10^3 uniform deployments over the unit disk, compute the exact MST longest edge M_emp, and compare it with sqrt(log n / n) and with 1/sqrt(n). If M_emp scales as roughly 1/sqrt(n), the substitution M = O(L sqrt(log n / n)) in Theorem 2 is invalid, and the O(M) competitive ratio is unsupported. Separately, ask the authors to supply the proof of Proposition 1 from technical report [5]; if no proof is available, the round-time bound and the entire competitive analysis remain unverified.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"The central claim for arbitrary deployments rests on Proposition 1, that each round completes within twice one block's coverage time, with the proof deferred to technical report [5] whose URL is a placeholder. That deferred proof is load-bearing because Eq. (1), Lemmas 1–3, and hence both theorems all sum round times under exactly this factor-2 premise. However, an independent concern is sharper for Theorem 2. The proof lower-bounds the optimal offline makespan OPT by M and then substitutes M = O(L*sqrt(log n/n)), citing Lemma 4, which applies to a random geometric graph G(n,r) with radius r, not to the MST's longest edge M. For points in a disk of radius L, the MST longest edge is on the order of L/sqrt(n), not L*sqrt(log n/n); the ratio of those bounds is sqrt(log n). Using the larger value would shrink the claimed competitive ratio by sqrt(log n), so the O(M) statement is not supported by the cited lemma. Together with the unverified Proposition 1, the strongest claim as stated is unproven. Additionally, the 'worst case' sparse-configuration argument is asserted without proof, and Lemma 2's proof is only a sketch with the full argument in [5].","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers the Online Network Formation Problem (ONFP): a single active robot must propagate information to all other robots in an unbounded environment, with no prior knowledge of robot locations and a bounded communication range. The authors propose CIRCLE-TAG, a round-based algorithm in which the leader performs concentric-circle searches and active robots cover assigned circular-sector blocks. For arbitrary deployments they claim an O(H·max{M,√(MH)})-competitive ratio, where M is the longest edge of the Euclidean MST on the initial configuration and H is its height. For uniform random deployments over a disk of unknown radius L, they claim an improved O(M)-competitive ratio. The paper also reports MATLAB simulations and a three-UAV field experiment.","tokens_in":9492,"tokens_out":9682,"duration_ms":106140,"significance":"If the claimed bounds are correct, the paper makes a useful contribution: it gives the first online algorithm for network formation in unbounded environments with a competitive-ratio guarantee, and it includes both simulation and field validation. The algorithm is natural and the analysis is not curve-fitted; there are no free parameters. The arbitrary-deployment bound is structurally plausible, and the random-deployment result, if properly established, would be a meaningful improvement. However, the manuscript's central proofs are deferred to a self-authored technical report, and the proof of Theorem 2 as written appears to use the wrong direction of an inequality. These issues prevent the claims from being independently verified from the submitted text, despite the otherwise sensible high-level strategy.","major_comments":[{"comment":"The proof of Proposition 1, the proof of Lemma 2, and the proofs of Propositions 2–4 are all deferred to the self-authored technical report [5], whose URL contains the placeholder '18-00XX'. Proposition 1 is load-bearing: Equation (1) in Section IV-B.1 and Equation (2) in Lemma 3 both sum round times under the premise that each round completes in at most twice the block-coverage time. Without an accessible proof, the sums in Equations (1) and (2) cannot be verified, and the asymptotic bounds in Theorems 1 and 2 are not independently checkable. Please include the proofs in the manuscript or make the technical report publicly available and ensure it is cited with a working URL.","section":"Section IV-A, Proposition 1 and Section IV-B.2, Lemma 2"},{"comment":"The proof of Theorem 2 is not valid as written. Lemma 4 states that a random geometric graph is connected with high probability when r ≥ √(2 log n / n), which gives an upper bound on the critical connectivity radius and hence an upper bound on M, namely M = O(L√(log n/n)). But to lower-bound OPT in order to upper-bound SOL/OPT, one needs a lower bound on M, i.e., M = Ω(L√(log n/n)) with high probability. An upper bound on M cannot lower-bound OPT. The proof should either establish the matching lower bound (for example, from the existence of isolated vertices when r is below the threshold) or state and prove a different, formally correct argument for the O(M) competitive ratio. The paper should also clarify whether the competitive ratio is meant in expectation, with high probability, or for every instance, since the input is random in this section.","section":"Section IV-C, Theorem 2 proof"},{"comment":"The assertion that the worst-case configuration is a path with equal spacing M and the leader at an endpoint, justified by 'the maximum furthest pairwise distance,' is not proved. Maximum pairwise distance does not by itself determine CIRCLE-TAG's makespan, since the algorithm's rounds depend on the leader's own distances and on the number of active robots at each phase. This unproved extremal claim is used to bound the number of phases by D ≤ 2H and to derive Equation (1). Please provide a rigorous argument that this configuration maximizes the algorithm's completion time among sparse configurations, or replace the step with a direct bound on the radii R_t in terms of M and H that does not rely on the asserted extremal configuration.","section":"Section IV-B.1, Sparse configurations"}],"minor_comments":[{"comment":"Reference [5] has a placeholder URL ('18-00XX'); this should be updated to the actual technical report number.","section":"References"},{"comment":"The phrase 'Mn ≥ 2L' would be clearer as 'nM ≥ 2L', since the product of the number of robots and the longest MST edge is meant.","section":"Section IV-C, after Equation (2)"},{"comment":"The caption states that the arbitrary-deployments bound 'fits nicely' on random deployments, but the plotted quantity and the error bars or confidence intervals are not described; adding this information would make the comparison easier to assess.","section":"Section V, Figure 6"},{"comment":"The typesetting of 'CIRCLE -TAG' with a stray space appears repeatedly; this should be corrected to 'CIRCLE-TAG'.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main issue is that the paper's central claims are not independently verifiable from the submitted manuscript because the proofs are deferred to an inaccessible self-authored technical report. The Theorem 2 proof gap is a concrete error in the argument as written, though likely fixable with a standard connectivity lower bound. I recommend requesting the full proofs and a corrected Theorem 2 proof before considering acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read of the Engin/Isler preprint. The headline is: this is a genuine extension of online freeze-tag / network formation from bounded rectangular environments to unbounded ones, with a clean algorithm and plausible ratio bounds. The catch is that a lot of the load-bearing analysis is deferred to a self-authored technical report [5] whose URL is a placeholder, so I cannot verify the central claims from the manuscript alone.\n\nWhat's new: the CIRCLE-TAG algorithm (leader does concentric-circle search, active robots sweep wedge-shaped blocks) and the competitive ratio O(H * max{M, sqrt(MH)}) for arbitrary deployments, with O(M) for uniform random deployments. That last bound is the kind of clean asymptotic result that makes sense for the random case. The simulation study is reasonable, and the three-UAV field experiment is a nice proof of concept even if it doesn't validate the asymptotics.\n\nThe main soft spot is Proposition 1: it says a round finishes within 2C(b_i,k) of one block's coverage time, and Equ. (1), Lemmas 1–3, and both theorems all sum round times under that factor-2 premise. The proof is not in the manuscript; it's in [5]. Same for Propositions 2–4 and the full proof of Lemma 2. That's a wall between the reader and the result. The worst-case 'path configuration' assertion in Section IV.B is also stated without proof; it's plausible but not self-evident. These are addressable gaps, not demonstrated errors.\n\nOne point where I think the stress-test note is off: the concern that Theorem 2 misuses the RGG connectivity bound. The MST longest edge M is exactly the critical radius at which G(n,M) becomes connected, because the MST minimizes the maximum edge over all spanning trees. So Lemma 4 does apply to M, and the substitution M = O(L sqrt(log n/n)) is legitimate with high probability. That part seems fine to me.\n\nMy verdict: the contribution is likely correct but not fully verifiable in this form. I'd send it to peer review—the problem is interesting enough and the authors' prior work is solid—but I'd insist the technical report be made available, or the key proofs included in an appendix. If the deferred proofs check out, this is a good paper for the multi-robot systems crowd. For my own work, I'd cite it cautiously, once I can see the full proof.","headline":"Genuine extension of online network formation to unbounded environments, but the main proofs sit in an inaccessible tech report, so the ratios are plausible rather than verifiable.","tokens_in":10011,"tokens_out":4316,"would_cite":true,"duration_ms":42443,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A leader-driven search, CIRCLE-TAG, propagates a message to all robots in unbounded unknown terrain with competitive ratio $O(H \\cdot \\max\\{M, \\sqrt{MH}\\})$ for arbitrary deployments and $O(M)$ for uniform random ones, where $M$ and $H$…","keywords":["online network formation","multi-robot systems","competitive analysis","freeze-tag problem","Euclidean minimum spanning tree","coverage search","unbounded environments","random geometric graphs"],"falsifier":"Run CIRCLE-TAG on a line configuration with robots spaced $M$ apart and measure, in each round, the true round duration against $2C(b_{i,k})$, the doubled Block-Cover time of a single assigned block. If any round exceeds that doubled coverage time, Proposition 1 is false and the sums in the proof do not bound the solution; looking for such an instance in simulation would settle the load-bearing premise directly.","tokens_in":9047,"feed_emoji":"🤖","tokens_out":9414,"duration_ms":88835,"temperature":0.7,"pith_summary":"The paper studies a team of robots that can talk only within a short range, scattered over an open area with no boundary and no shared knowledge of each other's positions. One robot holds a message; the goal is to propagate it to all robots as fast as possible in an online, asynchronous fashion. The paper proposes CIRCLE-TAG, in which a leader searches in expanding concentric circles and, once two robots are found, assigns each active robot a sector block to sweep. Its central claim is that for arbitrary deployments the makespan is at most $O(H \\cdot \\max\\{M, \\sqrt{MH}\\})$ times the optimal offline makespan, where $M$ is the longest edge of the Euclidean minimum spanning tree on the starting positions and $H$ is the tree's height; for uniformly random deployments the expected competitive ratio drops to $O(M)$. A sympathetic reader would care because this is a worst-case guarantee that does not depend on the size or boundary of the environment, only on two structural numbers of the initial configuration.","feed_headline":"Robot networks can form in unbounded terrain at a provable speed","feed_subtitle":"The guarantee depends only on the widest gap and height of the robots' minimum spanning tree, not on the area or boundary.","key_machinery":"The load-bearing object is the pair $(M,H)$ of the Euclidean MST on the initial robot positions, combined with CIRCLE-TAG's two-motion schedule: the leader's Concentric-Circles-Search (CCS), whose radius in round $i$ increases by the number of active robots, and the Block-Cover sweeps, in which each active robot covers a cut-circle-sector block with $k_i$ concentric arcs. Proposition 1, that a round completes in at most twice the Block-Cover time of a single block, $2C(b_{i,k})$, is what converts geometry into the phase sums that bound the solution. The MST supplies the lower bound $M$ on the optimal offline time, bounds the phase radius differences ($\\Delta^-<2M$), and bounds the number of phases by $2H$; in the random case, the same machinery is fed by ring counts and the random-geometric-graph connectivity threshold.","core_discovery":"The central discovery is that the online network formation problem in unbounded environments is governed by two structural parameters of the initial configuration: the largest edge length $M$ of the Euclidean MST built on the robot positions, and the MST's height $H$. CIRCLE-TAG's search has completion time $O(M^2 H)$ in sparse configurations and $O(\\max\\{M^2H, (MH)^{3/2}\\})$ in dense ones; since the optimal offline strategy needs at least $M$ time units, this yields the $O(H \\cdot \\max\\{M, \\sqrt{MH}\\})$ competitive ratio of Theorem 1. For random deployments over an unknown disk of radius $L$, analysis by concentric rings and the connectivity threshold of random geometric graphs ($M=O(L\\sqrt{\\log n/n})$) gives an expected solution time $O(L^2\\log n/n)$, which is $O(M)$-competitive by Theorem 2. The same algorithm and bounds cover the asynchronous setting, where robots need not start together.","pith_inferences":["An implication left implicit is a natural policy threshold at $n \\approx M$: sparse configurations are dominated by the leader's search time, dense ones by block coverage. A hybrid that switches the radius-increment rule at this threshold could plausibly remove the $\\sqrt{MH}$ term, but the paper does not propose or test it.","Because distances are normalized by the communication range, the same ratios apply across physical scales; the field experiment using UAVs at $h=40$ m, step $60$ m, and range $50$ m is one concrete instantiation of that scale invariance.","The expanding-circles leader motion is the classic symmetric rendezvous strategy, so the block-cover machinery may transfer to multi-robot rendezvous with unknown initial distances, a problem outside this paper's scope."],"forward_implications":["For arbitrary deployments, the message reaches all robots in time within $O(H \\cdot \\max\\{M, \\sqrt{MH}\\})$ of the optimal offline strategy, so the guarantee worsens only with the widest initial gap and the MST's height, not with the area or boundary of the environment.","For uniformly random deployments, the expected competitive ratio is $O(M)$, a clear improvement over the arbitrary-deployment bound as the number of robots grows.","The algorithm is asynchronous and uses no global position knowledge, so robots can start at different times and still execute the same strategy successfully.","The only gap left in the arbitrary-deployment analysis is the $\\sqrt{MH}$ factor; removing it is explicitly identified as future work."],"supporting_citations":[{"why":"Defines the Freeze-Tag Problem, the offline model of waking up frozen robots that this paper turns into an online, unbounded-environment version.","marker":"[2]"},{"why":"Gives the prior Euclidean-domain online freeze-tag analysis on a bounded rectangle, the bounded-environment assumption that this paper removes.","marker":"[11]"},{"why":"Establishes the competitive-ratio framework and lower bound for the online freeze-tag problem in graph settings, which motivates the online analysis here.","marker":"[8]"},{"why":"Supplies the random-geometric-graph connectivity threshold used in Lemma 4 to relate the MST maximum edge $M$ to the deployment radius $L$ and robot count $n$.","marker":"[7]"},{"why":"Contains the deferred proof of Proposition 1 and the full proofs of the lemmas and propositions on which the competitive-ratio bounds stand.","marker":"[5]"}],"fun_headline_variants":["Robot networks form at provable speed in unbounded terrains","Asynchronous robot networking: speed guarantee from MST shape","Unbounded unknown environments: robot network speed bounded","Online robot network formation: competitive ratios from M and H","Random deployment robot networks: O(M)-competitive speed"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire runtime analysis rests on Proposition 1, which claims that each round of CIRCLE-TAG finishes in no more than twice the time one active robot needs to sweep its assigned block; the proof is deferred to a self-authored technical report whose URL is a placeholder, and if this bound fails, the phase sums and both competitive ratios no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Robot networks form at provable speed in unbounded terrains","Asynchronous robot networking: speed guarantee from MST shape","Unbounded unknown environments: robot network speed bounded","Online robot network formation: competitive ratios from M and H","Random deployment robot networks: O(M)-competitive speed"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000763,"raw_usage":{"total_tokens":3383,"prompt_tokens":941,"completion_tokens":2442,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":557,"completion_tokens_details":{"reasoning_tokens":2363}},"tokens_in":557,"tokens_out":2442,"duration_ms":18639,"temperature":1.0,"reasoning_tokens":2363,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:28:33.504508+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run CIRCLE-TAG on a line configuration with robots spaced $M$ apart and measure, in each round, the true round duration against $2C(b_{i,k})$, the doubled Block-Cover time of a single assigned block. If any round exceeds that doubled coverage time, Proposition 1 is false and the sums in the proof do not bound the solution; looking for such an instance in simulation would settle the load-bearing premise directly.","supporting_citations":[{"cited_title":"The freeze-tag problem: how to wake up a swarm of robots","cited_arxiv_id":null,"evidence_quote":"Defines the Freeze-Tag Problem, the offline model of waking up frozen robots that this paper turns into an online, unbounded-environment version."},{"cited_title":"Probabilistic network for- mation through coverage and freeze-tag","cited_arxiv_id":null,"evidence_quote":"Gives the prior Euclidean-domain online freeze-tag analysis on a bounded rectangle, the bounded-environment assumption that this paper removes."},{"cited_title":"The online freeze-tag problem","cited_arxiv_id":null,"evidence_quote":"Establishes the competitive-ratio framework and lower bound for the online freeze-tag problem in graph settings, which motivates the online analysis here."},{"cited_title":"Critical power for asymp- totic connectivity in wireless networks","cited_arxiv_id":null,"evidence_quote":"Supplies the random-geometric-graph connectivity threshold used in Lemma 4 to relate the MST maximum edge $M$ to the deployment radius $L$ and robot count $n$."},{"cited_title":"Asynchronous network formation in unknown unbounded environments","cited_arxiv_id":null,"evidence_quote":"Contains the deferred proof of Proposition 1 and the full proofs of the lemmas and propositions on which the competitive-ratio bounds stand."}],"review_version":1}