{"id":"0c0f983c-f86d-44d3-87d2-3c2a788fa4e1","arxiv_id":"2607.29474","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A gossip-based global termination detector lets nodes in a distributed betweenness centrality computation stop only after all nodes have converged, avoiding premature-stop errors.","lead":"This paper adds a distributed termination layer that tells each node in a network when all nodes have finished computing betweenness centrality, so they stop together instead of stopping early. A reader might care because stopping too early in distributed graph algorithms silently corrupts results, and this is a lightweight, message-efficient fix.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Safety of the global termination rule is unproven: local stability for MIN phases does not imply finality, and the ε=0.05 trigger can fire before all vertices are even locally converged; the zero-error result is empirical, not guaranteed.","rationale":"The reader's weakest assumption — that local stability for MIN phases does not imply finality, and that the gossip ratio can reach the global condition while some vertices are only temporarily stable — is precisely the load-bearing gap in the paper's central claim. The paper positions its contribution as 'letting vertices stop safely after detecting global convergence,' but Algorithm 1 has no invariant or proof connecting its trigger to the actual finality of the distributed BC estimates. In a Bellman-Ford-style dependency-accumulation algorithm, the BC estimate is a sum of contributions that arrive in waves; a vertex can appear stable for several phases and then change when a distant dependency contribution arrives. Section IV-B acknowledges limitations such as churn and message loss, but it does not address this fundamental finality gap; the statement that delays only postpone convergence is too strong because a delayed dependency message can cross the detection threshold. The empirical zero-error results on four graphs, with hand-picked ε and MIN values and no repeated runs, are not sufficient to establish the claim. This does not mean the paper is dishonest or worthless: the simulator and code are linked, the comparison with local stopping is instructive, and a shadow-mode experiment could validate the safety condition empirically. The reader's CONDITIONAL verdict is appropriate; no verdict change is needed, but the condition should include the concrete safety check proposed above. If that check reveals nonzero error, the verdict should move to REJECT, since the central claim would then be falsified even on the paper's own evaluation setup.","tokens_in":8719,"tokens_out":7512,"duration_ms":91183,"concrete_test":"Run the existing simulator in a shadow mode: do not actually stop vertices when GLOBAL CONVERGENCE is first detected; instead, snapshot all BC estimates and let the baseline algorithm continue processing messages until quiescence (or for 2×diameter additional phases). Compare the snapshot with the final estimates using the paper's relative ℓ2 error (Eq. 4). Run this on all four evaluated graphs and on an added long-path or barbell graph with the paper's per-message delay and phase settings (ε=0.05, MIN=5). If the snapshot error is nonzero on any graph, or if the trigger fires when v/w < N (so some vertices have not reported local convergence), the detector's safety condition is empirically insufficient. If the snapshot error is zero on all of these, the concern is substantially weakened, though still without a formal proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1's only safety condition is the conjunction of (i) a vertex's own BC estimate having changed by less than ε for MIN consecutive phases (line 17-19) and (ii) the gossip aggregate satisfying |N - v/w|/N ≤ ε for MIN consecutive phases (line 23). The paper never proves — and the Section IV-B correctness discussion only asserts — that a plateau of length MIN implies the estimate cannot change later. In a distance-vector BC computation, dependency contributions from distant targets propagate in a second wave from the leaves of the shortest-path DAG upward; a vertex can sit on a plateau for several phases while that wave is still in transit, then receive a delayed dependency update that moves its estimate. Thus local stability is at best a heuristic, not a finality certificate. Moreover, because the experiments set ε = 0.05, the trigger can fire when v/w is only ≈0.95N — i.e., up to roughly 5% of vertices have not even reported local convergence. The claim in Section IV-B that transient delays 'only postpone the dissemination of convergence information' is therefore not generally true: a delayed dependency message can pass the detection point, reproducing the premature-termination error the paper is meant to prevent. The zero final error is an empirical observation on four small graphs with hand-picked thresholds, not a consequence of the proposed condition. Since the entire contribution is the safety of this stopping rule, this gap is load-bearing.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a lightweight, fully distributed global termination detection layer for distance-vector-based distributed betweenness centrality computation. Each vertex monitors whether its own betweenness estimate has been stable for MIN consecutive phases, and a peer-sampling aggregation (v/w) is used to estimate the number of locally converged vertices. When this aggregate is within epsilon of the known network size N for MIN consecutive phases, vertices declare global convergence and stop. The authors evaluate this global stopping rule against a local stopping rule using a custom Python simulator on four graphs (ER, Geometric, Email, Road), reporting zero final relative L2 error under global termination and nonzero error under local termination. The paper argues that local convergence is unsafe and that the proposed global condition provides an explicit, safe system-wide stopping point.","tokens_in":9073,"tokens_out":2713,"duration_ms":34568,"significance":"If the safety claim were established, the contribution would be practically useful: it adds a constant-size-message termination layer on top of an existing distributed betweenness algorithm, without modifying the core computation, and it gives vertices an explicit stopping signal rather than relying on fixed round bounds or local inactivity. The paper also provides a reproducible simulator and uses an external ground-truth source (NetworkX), which is a strength. However, the central claim that the detected condition guarantees exact betweenness is not proven; it is supported only by a correctness intuition and an empirical evaluation on four small graphs with hand-picked thresholds. The gap between what is asserted ('explicit globally safe stopping condition') and what is demonstrated (zero error in the evaluated simulations) is load-bearing, because the safety of the stopping rule is the entire contribution.","major_comments":[{"comment":"The safety of the global termination rule is not proven. The algorithm declares local convergence when a vertex's betweenness estimate has changed by less than epsilon for MIN phases, and global convergence when |N - v/w|/N <= epsilon for MIN phases. The paper states in Section IV-B that transient delays 'only postpone the dissemination of convergence information,' but this is not generally true: in a distance-vector betweenness computation, dependency contributions from distant targets propagate in a second wave from the leaves of the shortest-path DAG. A vertex can sit on a plateau for several phases while that wave is still in transit and then receive a delayed dependency update that changes its estimate. A local-stability plateau is therefore at best a heuristic, not a finality certificate. Since the paper's central claim is that the detector lets vertices 'stop safely,' the missing","section":"Section IV-B and Algorithm 1 (lines 17-19, 23)"},{"comment":"The empirical support for safety is limited. The experiments use a single hand-picked epsilon=0.05 and MIN=5, with no repeated runs, no confidence intervals, and only four graphs. Because the termination condition is |N-v/w|/N <= 0.05, the detector can fire when up to roughly 5% of vertices have not even reported local convergence, and delayed dependency messages can pass the detection point in exactly the scenario the paper aims to prevent. The zero final errors in Table I are observations on these four instances, not consequences of a proved invariant. To support the safety claim, the authors should either prove an invariant relating the termination condition to actual convergence of the betweenness estimates, or provide a systematic sensitivity analysis and repeated trials showing the zero-error behavior is robust across threshold choices and graph families.","section":"Section V, Table I and Eq. (4)"},{"comment":"The termination layer's aggregation behaviour is taken on faith from prior self-cited works [11]-[13] without stating the conditions under which v/w converges to the number of locally converged vertices. The algorithm halves and adds (v,w) on random peer interactions under asynchronous message delays; no correctness proof is given for this gossip process in the present setting, and no formal relationship is established between the aggregate ratio v/w and the true count of converged vertices. If the aggregation can underestimate or overestimate the converged count at the moment of detection, the global condition in Algorithm 1 is not reliable. This is closely related to the safety gap above and should be addressed as part of the formal analysis.","section":"Section IV-A and references [11]-[13]"}],"minor_comments":[{"comment":"The name 'Erd ˝os–R´enyi' contains a corrupted character ('˝o' instead of 'ő').","section":"Abstract"},{"comment":"The Require line mentions STABLE_i but the procedure does not define how STABLE_i is computed; the experimental section states that stability means a change of less than epsilon for MIN consecutive phases, but this definition should appear in the algorithm or in Section IV-A, not only in Section V.","section":"Algorithm 1"},{"comment":"The text says that when v/w matches N, global convergence is declared, but Algorithm 1 and the experiments use the tolerance |N-v/w|/N <= epsilon. This discrepancy should be stated explicitly in the prose.","section":"Section IV-B"},{"comment":"Figures 1-4 are referenced but not shown in the text provided; the authors should ensure the figure captions and axes clearly distinguish local and global scenarios, and report the evolution of v/w as well as the error.","section":"Section V"},{"comment":"The statement 'In the proposed approach, whenever a vertex reaches a local convergence, it increments v by 1 in Algorithm 1' conflicts with Algorithm 1, where v is incremented by 1 only in the 'LOCAL CONVERGENCE' branch after the state transition; clarify the exact update rule.","section":"Section IV-A"}],"recommendation":"major_revision","confidential_remarks":"The core contribution is a stopping rule whose safety is asserted but not proven. The paper's own limitation discussion acknowledges that the mechanism targets stable networks, but it does not acknowledge that the local-stability criterion is insufficient even under reliable delivery. The evaluation is too thin to substitute for a proof: four graphs, no repeats, hand-picked epsilon and MIN, and no analysis of how often the detector fires with fewer than N locally converged vertices. This is fixable within the manuscript's scope by adding a formal correctness analysis under explicit assumptions or by substantially reframing the contribution as a heuristic with a much more thorough sensitivity study, but as it stands the central claim is not supported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper adds a gossip-based global termination detector to Crescenzi et al.'s distance-vector betweenness centrality algorithm. That is actually new relative to the cited literature, and the empirical comparison against local stopping is a useful, honest contribution: it shows that local convergence on heterogeneous graphs leaves real residual error, while the global rule keeps zero error on the four tested networks. The problem is well motivated, the overhead analysis is straightforward, and the code is public. Credit where it's due: this is a modest but sensible piece of engineering.\n\nThe soft spot is load-bearing. The safety of the stopping rule rests on two assertions that the paper does not prove. First, that a vertex whose BC estimate stays within epsilon for MIN phases will not change later. In a distance-vector computation, dependency updates propagate in a second wave from leaves upward, and a plateau of five phases can easily be transient. Second, the global trigger only requires v/w to be within epsilon of N, so with epsilon=0.05 it can fire while up to 5% of vertices have not even reported local convergence. If those vertices still need messages from vertices that have already stopped, the premature-termination error the paper claims to prevent can reappear. Section IV-B's statement that transient delays only postpone termination is not generally true for that reason. The zero-error result is an observation on four small graphs with hand-picked thresholds, not a consequence of the proposed condition.\n\nThat said, this is not a fatal flaw in the sense of the paper being incoherent. It is an unproven central claim, and the evaluation lacks repeated runs, confidence intervals, or sensitivity analysis. A referee should ask for either a formal correctness argument for the stopping condition under the stated model, or a much more thorough empirical study (multiple seeds, varying epsilon and MIN, larger and more varied graphs, message delays) with error statistics. The paper is preliminary but points at a real failure mode, and the approach is plausible. I would send it to peer review, but I would not accept it as is.\n\nThis is a paper for people working on distributed graph algorithms and termination detection. It won't reshape the field, but it is a legitimate contribution if the authors can back up the safety claim. I would bring it to a reading group only for the discussion of what counts as a proof of convergence in this setting. I would not cite it in my own work yet. The code availability and the clear problem statement make it worth engaging with, and the serious thinker flag is deserved: the authors are honestly identifying a gap, even if their solution is not yet fully justified.\n\nRecommendation: engage with it, but demand rigor on the termination condition before believing the headline.","headline":"Plausible global termination layer for distributed BC, but safety is empirically demonstrated, not proven; deserves a serious referee if the team is willing to tighten the central claim.","tokens_in":9516,"tokens_out":3014,"would_cite":false,"duration_ms":35277,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A lightweight global termination detector lets distributed betweenness computation stop at true system-wide convergence, not at each vertex's own apparent stability.","keywords":["betweenness centrality","global termination detection","distributed graph algorithms","gossip aggregation","local convergence","distance-vector algorithms","overlay network","premature termination"],"falsifier":"On a long chain graph, run the distance-vector betweenness computation with the termination layer and freeze a vertex's estimate after its first MIN stable phases while a dependency wave is still propagating toward it from the far end; if the global condition triggers before that wave arrives and the final relative L2 error is non-zero, the detector's convergence criterion is unsound. The paper's own geometric-graph case, where the termination layer did not converge under physical-neighbour communication within the simulation budget, marks the edge of the claimed regime.","tokens_in":1290,"feed_emoji":"🛑","tokens_out":2796,"duration_ms":78986,"temperature":0.7,"pith_summary":"The paper tackles a blind spot in distributed betweenness centrality: vertices often halt as soon as their own estimate stops changing, but shortest-path dependency information may still be propagating elsewhere in the network. The authors add a parallel, lightweight termination layer in which vertices gossip a pair of counters whose ratio estimates the number of locally converged vertices, and stop only when that ratio is within a tolerance of the known network size for several consecutive phases. A custom event-driven simulator on synthetic and real graphs shows that local stopping yields non-zero final error, while the global condition stops later and keeps the final betweenness error at zero. The paper argues this gives distributed betweenness algorithms an explicit, coordinated halting condition without modifying the underlying computation.","feed_headline":"Global stop signal cuts distributed betweenness error to zero","feed_subtitle":"Vertices keep running until a system-wide tally proves the whole network converged, not just their own estimate.","key_machinery":"The detector is built on a (v, w) pair maintained by every vertex: the seed starts with w=1, and in each phase a vertex halves its pair, pushes it to a random peer, pulls the peer's pair, and adds the received values. The ratio v/w aggregates toward the number of vertices that have entered LOCAL CONVERGENCE, and GLOBAL CONVERGENCE is declared when |N - v/w| / N is within epsilon for MIN consecutive phases. This machinery converts a purely local stability signal into a system-wide stopping decision using only constant-size messages and O(1) state per vertex, and it runs in parallel with the baseline distance-vector betweenness algorithm.","core_discovery":"The paper's central claim is that safe termination of distributed betweenness centrality cannot be decided from a single vertex's local stability: a vertex whose estimate is stable may still be needed by others, or may later receive new dependency information. The proposed termination layer lets every vertex decide when the whole system has converged by running a push-pull gossip aggregation of the number of vertices that have reported local stabilisation, and only then halting. In the evaluated networks, following this global condition instead of stopping at local stability gives zero final relative L2 error, whereas local stopping gives non-zero errors on every tested graph, including a re","pith_inferences":["The same (v, w) gossip termination layer could be grafted onto other iterative distributed algorithms that expose a local-stability predicate, such as distributed PageRank or label propagation, since the mechanism is not tied to betweenness math.","The paper evaluates a single epsilon-MIN setting; sweeping these parameters would reveal a tradeoff between premature-declaration risk and stopping latency, and would test how robust the zero-error result is.","Under the overlay model, termination detection can outpace physical-neighbour propagation of betweenness messages, so a deployment using overlay gossip should model hop-level transmission cost, which the paper explicitly leaves as deployment-dependent.","The authors themselves limit the claim to stable networks with reliable delivery and fixed N; extending the detector to churn, message loss, or a changing N would require retransmission, membership updates, and dynamic adjustment of N."],"forward_implications":["Distributed betweenness implementations that currently stop at fixed rounds or local inactivity can be retrofitted with this termination layer, removing premature-termination error without changing the core algorithm.","The layer adds at most 2N constant-size logical messages per phase across N active vertices, a small and bounded overhead compared with running extra phases after convergence.","Under overlay communication, the detector reaches global convergence in fewer phases than under physical-neighbour diffusion on every tested graph, so overlay routing can cut stopping latency on slowly mixing or high-diameter networks.","Local stopping is unsafe across all four evaluated graph families, producing non-zero final error in every case, while global stopping yields zero final error.","A correctly detected global stop lets all vertices halt together, eliminating post-convergence message exchanges in bandwidth-limited settings."],"fun_headline_variants":["Global stop signal cuts betweenness error to zero","System-wide convergence check ends centrality errors","Wait for global proof, not local stability","Distributed centrality: halt only after global convergence","Local stopping fails; global termination wins"],"cache_read_input_tokens":10880,"weakest_assumption_plain":"The load-bearing premise is that a vertex whose betweenness estimate has changed by less than epsilon for MIN consecutive phases can be counted as converged; the paper does not prove that such a temporarily stable vertex cannot later receive new dependency information through other parts of the network.","fun_headline_variants_meta":{"raw":{"variants":["Global stop signal cuts betweenness error to zero","System-wide convergence check ends centrality errors","Wait for global proof, not local stability","Distributed centrality: halt only after global convergence","Local stopping fails; global termination wins"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000227,"raw_usage":{"total_tokens":1322,"prompt_tokens":773,"completion_tokens":549,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":517,"completion_tokens_details":{"reasoning_tokens":497}},"tokens_in":517,"tokens_out":549,"duration_ms":6509,"temperature":1.0,"reasoning_tokens":497,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T06:23:16.582447+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a long chain graph, run the distance-vector betweenness computation with the termination layer and freeze a vertex's estimate after its first MIN stable phases while a dependency wave is still propagating toward it from the far end; if the global condition triggers before that wave arrives and the final relative L2 error is non-zero, the detector's convergence criterion is unsound. The paper's own geometric-graph case, where the termination layer did not converge under physical-neighbour communication within the simulation budget, marks the edge of the claimed regime.","supporting_citations":[],"review_version":1}