{"id":"3fd1096d-5f89-41c0-aad4-386a96d9b964","arxiv_id":"2507.23533","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Combining the RAES threshold link-acceptance rule with streaming node churn produces dynamic expanders with bounded degree, and the paper proves O(log n) push/pull rumor spreading on them.","lead":"This paper analyzes a local protocol that maintains a bounded-degree expander while nodes continuously join and leave. It proves the dynamic snapshots expand well with high probability, and that push and pull rumor spreading finish in O(log n) rounds.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.2's bootstrap is not proven: Lemma 6.3 establishes only a stable connected component, and connectedness does not imply β log n informed nodes in O(log n) rounds.","rationale":"The reader's weakest_assumption focuses on the uniform link-manager assumption, but that is part of the model's definition in Definition 3.3(b), not a hidden correctness assumption; the paper explicitly discusses non-uniform link managers as an open variant in Section 8. I therefore do not treat that as the main load-bearing concern. The more serious issue is the bootstrap in Theorem 6.1 / Lemma 6.3, which the reader also flags as under-formalized. My read strengthens that concern: the proof as written is not merely terse; it draws the wrong consequence from the facts it establishes. A stable connected component of size β log n does not imply that β log n nodes become informed in O(log n) rounds, because randomized rumor spreading on a path of logarithmic length takes Θ(log n log log n) rounds. The expansion guarantees of Section 5 apply to subsets of H_t, not to subsets of the component left after deleting OLD, and for small sets the deleted nodes can absorb the entire boundary. Hence the bootstrap cannot be completed by the sentence currently in the proof. This does not make the expansion theorems wrong: the proofs of Lemma 4.1, Lemmas 5.2--5.4, and the queue bounds are substantial and appear structurally sound. It does mean Theorem 1.2 is not yet established. Since the reader's verdict is already CONDITIONAL and my concern is consistent with that, I do not recommend changing the verdict; I recommend that acceptance require a complete proof of Lemma 6.3 or an alternative bootstrap argument.","tokens_in":30455,"tokens_out":36798,"duration_ms":416000,"concrete_test":"Provide a complete, rigorous proof of Lemma 6.3. It must show that the component of H_{ts} \\ OLD containing the source has vertex expansion Ω(1) for all subsets of size up to β log n, or otherwise give a mechanism producing β log n informed nodes in O(log n) rounds from the stated hypotheses. As a concrete analytical check, attempt to construct a graph satisfying the vertex-expansion guarantee of Lemma 5.4 together with a set OLD of size Θ(log^2 n) whose removal leaves a connected path of length β log n as the source's component. If such a construction exists, then push or pull on that component takes ω(log n) rounds to inform β log n nodes, so the bootstrap argument as written fails. If instead the expansion guarantee for subsets of H_{ts} \\ OLD requires |S| ≥ C log^2 n, then the paper must explain how the informed set reaches that size before the expansion argument can begin.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step for Theorem 1.2 is Lemma 6.3, but its proof does not close the gap it claims. Lemma 6.3 asserts that within O(log n) rounds there are β log n informed nodes, yet the proof only shows that the source w.h.p. connects to a connected component of H_{ts} \\ OLD of size at least β log n that remains connected for Θ(log^2 n) rounds. It then says that 'thanks to Lemma 6.3' the expansion argument can be applied. This is circular: Lemma 6.3 was supposed to produce the β log n informed nodes, but connectivity of a component does not suffice to produce them in O(log n) rounds. On a path of length L, both push and pull require Θ(L log L) rounds; for L = β log n this is Θ(log n log log n), not O(log n). Moreover, the component need not inherit the expansion of H_{ts}: the deleted set OLD has size Θ(log^2 n), so the entire boundary of a subset of size less than Θ(log^2 n) could lie inside OLD. Lemma 5.4 only gives expansion for subsets of H_{ts}, not for subsets of H_{ts} \\ OLD. Thus the transition from 'source is connected to a stable connected component' to 'β log n informed nodes in O(log n) rounds' is unsupported, and the rumor-spreading bound depends on this transition.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript introduces the Threshold-Driven Streaming Graph model TSG(n,d,c), which combines the streaming node-churn process with the threshold-based RAES edge-formation rule from prior work. The main results are: (i) for every round t ≥ 2n, the snapshot G_t is w.h.p. an expander in the sense that every vertex subset of size at least β log n has constant conductance and there is an induced expander subgraph on n − O(log n) vertices; and (ii) push or pull rumor spreading from a source joining at time t_s ≥ 2n informs n − O(log n) vertices within O(log n) rounds. The technical core is a joint-distribution lemma (Lemma 4.1) that controls correlations among accepted link destinations, a queue bound (Lemma 4.2) for the number of pending requests, expansion proofs for small and large subsets (Lemmas 5.2 and 5.3), and a proof sketch for the rumor-spreading bootstrap (Lemma 6.3) and its use of the static conductance-based analysis.","tokens_in":30735,"tokens_out":18850,"duration_ms":231902,"significance":"If both theorems are correct, the expansion half is a substantial contribution: it extends the static RAES analysis to a dynamic node-churn model while keeping bounded degree, and it gives near-optimal communication costs (O(log n) pending requests per round, w.h.p.). Lemma 4.1 appears to be a genuinely new technical tool, and the queue analysis in Section 4.2 is nontrivial. The rumor-spreading claim is a natural and important application, but the current proof of Theorem 1.2 is only a sketch and contains a load-bearing gap: the bootstrap lemma does not prove what it states. The expansion theorem alone may be publishable, but the paper as submitted claims both results and needs a rigorous treatment of the bootstrap before the rumor-spreading theorem can be accepted.","major_comments":[{"comment":"Lemma 6.3 states that within T' = O(log n) rounds there are β log n informed nodes, but its proof only establishes that the source w.h.p. belongs to a connected subgraph of size at least β log n that remains connected for Θ(log^2 n) rounds. Connectivity alone does not imply O(log n) w.h.p. spreading: on a path component of length Θ(log n), push and pull advance the front by one vertex with constant probability per round, so a high-probability bound requires Ω(log^2 n) rounds, not O(log n). The proof also does not show that the component inherits expansion from H_t after deleting OLD; Lemma 5.2 controls expansion in the full snapshot G_t, but all boundary vertices of a subset of that component could lie outside the component or in OLD. The sentence 'Finally, thanks to Lemma 6.3, we can apply the expansion argument' is therefore circular: Lemma 6.3 was supposed to produce the informed set, yet its proof never analyzes the rumor protocol or the informed set. This gap is load-bearing for Theorem 1.2.","section":"Section 6.2, Lemma 6.3 and the paragraph following its proof"},{"comment":"The proof after the bootstrap invokes the proof argument of Theorem 6.2, which is a static-graph statement requiring a fixed connected graph with constant conductance and a bounded degree ratio. The TSG snapshots are not fixed: vertices leave, new vertices join, and the graph changes every round. The text asserts in one sentence that a logarithmic informed set 'dominates' the impact of edge deletions over a logarithmic window, but it does not supply a formal coupling or a round-by-round argument showing that the conductance-based expansion analysis applies to the evolving snapshots and to the evolving set of informed nodes. Assuming the bootstrap were fixed, this dynamic adaptation would still need a detailed proof rather than an appeal to the static theorem.","section":"Section 6.2, 'The analysis on the TSG model'"}],"minor_comments":[{"comment":"The displayed inclusion writes '|Q_t| ≤ 100 log n', dropping the factor (cd)^2 that appears in the lemma statement and in the preceding displayed inequality; it should be 100(cd)^2 log n.","section":"Section 4.2, proof of Lemma 4.2, Eq. (23)"},{"comment":"The statement says 'α = α(d) sufficiently large integers', but conductance is bounded above by 1 and the proofs (Lemmas 5.2–5.4) yield a bound of order 1/((c+1)d); the wording should be corrected to 'α = α(c,d) ∈ (0,1)' or similar.","section":"Theorem 5.1 statement"},{"comment":"References [16] and [17] are the same paper by Chierichetti, Giakkoupis, Lattanzi, and Panconesi; the duplicate should be merged and the citation in Section 6.2 made consistent.","section":"References [16] and [17]"},{"comment":"There is a typo in the theorem statement ('inform at leastn−O(log n)') and 'uniformed' should be 'uninformed' in the description of the pull protocol in Section 6.1.","section":"Theorem 1.2 statement and Section 6.1"},{"comment":"Lemma 6.3 uses β log n as the bootstrap target, while Lemma 5.2 guarantees expansion only for sets of size at least 2β log n; the proof never reconciles this factor-of-two gap, even though the gap is presumably fixable by adjusting constants.","section":"Section 6.2, Lemma 6.3 and Lemma 5.2"}],"recommendation":"major_revision","confidential_remarks":"The expansion part of the paper is technically substantial and likely salvageable, but Theorem 1.2 is not proven as written. I would recommend asking for a complete proof of the bootstrap and of the dynamic adaptation of the static rumor-spreading argument; weakening or removing Theorem 1.2 would also be an option if the bootstrap cannot be closed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Nice read overall. The paper introduces TSG(n,d,c), the streaming node-churn model with RAES's threshold acceptance, and proves that every snapshot is a good expander w.h.p. The expansion part is the real substance. Lemma 4.1, bounding the joint distribution of link destinations by a product form up to constant factor, is a genuine technical step beyond both the static RAES analysis [10] and the unbounded-degree churn model [12]. The queue control (Lemmas 4.2–4.4) is clean and gives optimal message work. Theorems 5.1 (a) and (b) rest on detailed multi-step proofs; I did not find a load-bearing error there, just the usual 'choose c,d large enough' constants.\n\nThe soft spot is Theorem 1.2. The proof sketch in Section 6.2 is exactly that: a sketch. Lemma 6.3 shows that w.h.p. the source lands in a stable connected component of size Ω(log n) inside H_ts minus OLD, but it does not show that Ω(log n) nodes actually get informed in O(log n) rounds. The paper jumps from 'connected component of size β log n' to 'now apply the expansion argument'. I disagree with the stress-test's specific quantitative point: on a bounded-degree path of length L, push and pull take O(L) rounds, not Θ(L log L), because each boundary step succeeds with constant probability. So the component doesn't need to be an expander for the bootstrap. But the paper still owes the reader the easy geometric argument: in a connected graph with maximum degree Δ=O(1), starting from one informed node, the informed set reaches size L in O(Δ L) rounds w.h.p., so L=Θ(log n) gives O(log n). They didn't include it, and as written the transition in Lemma 6.3 to the expansion phase is not demonstrated.\n\nThere are also typos and small garbles in Lemma 4.1's proof (e.g., the comment about 'may not be in V_sj' reads backwards), which reduce confidence even though the high-level structure of that lemma is sound. The citation pattern is fair: [10,12] are prior work, not circular, and Lemma 4.1 is new. No fitted parameters.\n\nWho is this for? Researchers in distributed algorithms and random dynamic graphs. The expansion theorem alone is a solid contribution. With a completed bootstrap proof, the rumor-spreading result would be a strong paper. As it stands, it should go to peer review, with a request for a full proof of Theorem 1.2 and a cleaned-up Lemma 4.1. I would not desk-reject it.","headline":"Strong expansion results for a new threshold/churn model, but Theorem 1.2 needs a real proof of the bootstrap, not just a sketch.","tokens_in":31295,"tokens_out":13465,"would_cite":true,"duration_ms":152354,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","68W20","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"Under streaming node churn, a threshold-based link protocol keeps every snapshot an almost-full expander, and rumor spreading completes in O(log n) rounds.","keywords":["threshold-driven streaming graph","expander","node churn","RAES","rumor spreading","conductance","bounded degree","streaming model"],"falsifier":"Run the TSG(n,d,c) process for many independent rounds and, at each t ≥ 2n, measure the conductance of every subset of size β log n and the size of the largest induced expander subgraph. The theorem predicts constant conductance for all such subsets and an induced expander on n − O(log n) vertices; if a constant fraction of rounds showed a subset of size β log n with conductance below 1/(10(c+1)d), or more than O(log n) vertices outside the expander, the claim would be refuted. A targeted test of the model assumption is to substitute a link manager that returns only vertices from a fixed half of the population: the near-product bound already fails in that variant, and the same empirical measurements should show the expansion property breaking.","tokens_in":30248,"feed_emoji":"📡","tokens_out":7500,"duration_ms":82035,"temperature":0.7,"pith_summary":"The paper tries to establish that a simple threshold-driven link protocol keeps a peer-to-peer-style network well connected even when the vertex population itself streams, with one node joining and one node leaving every round. Specifically, it analyzes TSG(n,d,c), in which each vertex maintains d outgoing connection requests and accepts incoming requests only up to a cd cap, and proves that every snapshot after round 2n is, with high probability, an almost-full expander: an induced subgraph on n − O(log n) vertices is an expander, and every vertex subset of size at least β log n has constant conductance. It then proves that the same expansion makes rumor spreading fast: if a source joins at or after round 2n, both push and pull inform n − O(log n) vertices within O(log n) rounds. A reader should care because bounded-degree, decentralized topologies that survive node churn are exactly what unstructured peer-to-peer networks need, and this paper shows that a local threshold rule alone can supply them with near-optimal message overhead.","feed_headline":"Rumor spreads in O(log n) rounds on churning networks","feed_subtitle":"A threshold-based link protocol keeps every snapshot an almost-full expander, so push and pull broadcast stay fast.","key_machinery":"The load-bearing object is Lemma 4.1, a near-product bound on the joint distribution of link destinations: for any set R of requests and any target set P, the probability that every request in R lands in P is at most (220|P|/(n−1))^{|R|}. This is what controls the correlations created by the threshold acceptance rule, where one rejected request can cascade into future requests. The surrounding machinery is a queue argument: Lemmas 4.2–4.4 show that the number of pending requests stays O(log n) with high probability and that each request is pending only O(1) rounds in expectation, bounding message load at O(log n) per round. Expansion then follows by a union bound over small subsets and an age-order argument for large subsets, and the expander subgraph is built from vertices with no pending requests.","core_discovery":"The central claim is that the original RAES acceptance rule—reject all incoming requests in a round whenever accepting them would exceed a cd in-degree cap—does not break down under streaming node churn. For any round t ≥ 2n, the snapshot G_t generated by TSG(n,d,c) has, with high probability, an induced expander subgraph on all but O(log n) vertices and constant conductance for every subset of size at least β log n; this is Theorem 1.1. As a consequence, Theorem 1.2 states that push or pull rumor spreading from a source that joins at round t_s ≥ 2n reaches n − O(log n) vertices within O(log n) rounds. The O(log n) slack is inherent to the model, because a freshly joined vertex may stay isolated for o(log n) rounds with non-negligible probability, so the broadcast target cannot reasonably be all n vertices.","pith_inferences":["The cycle decomposition used to prove Lemma 4.1, where a request alternates between a stable connected phase and a geometric rejection phase, looks portable to Poisson node churn with random lifetimes, where snapshot size itself fluctuates; the paper explicitly conjectures this extension.","The proof's real requirement is that no target set P receives too much probability mass—bounded by O(|P|/n) per request—so a link manager with mild bias over a large support might preserve the expansion bounds with larger constants, even though the paper only analyzes the uniform case.","Because a logarithmic informed set is shown to stay stable for Θ(log^2 n) rounds, a self-stabilizing variant that resets corrupted links while preserving the queue-halving property could plausibly recover from arbitrary bad states in polylogarithmic time; the paper raises this as an open direction.","A protocol that gives each new vertex one guaranteed initial connection, or lets it pull from an already-informed neighbor on entry, could plausibly reduce the uninformed slack from O(log n) to o(log n), closing the only gap left open by Theorem 1.2."],"forward_implications":["Every snapshot after round 2n is, with high probability, an expander on all but O(log n) vertices, so distributed tasks that need constant conductance can run on a network whose membership changes completely every n rounds.","Push and pull rumor spreading from a late-joining source finish in O(log n) rounds and inform all but O(log n) vertices, giving a logarithmic broadcast bound in a churning bounded-degree model.","The number of link-manager calls per round is O(log n) with high probability and constant in expectation, so maintaining the expander does not congest the network.","Each vertex makes O(log n) total link-manager calls over its lifetime with high probability and O(1) in expectation, so per-node work stays small.","The n − O(log n) broadcast target is tight: fresh vertices can stay isolated for o(log n) rounds, so no protocol of this type can guarantee informing the last few arrivals immediately."],"supporting_citations":[{"why":"Defines the original RAES protocol whose request-acceptance rule is combined with churn here.","marker":"[10]"},{"why":"Supplies the streaming node-churn model and the near-uniform destination lemma that Lemma 4.1 extends to joint distributions.","marker":"[12]"},{"why":"Gives the conductance-based rumor-spreading bound for bounded-degree graphs used after the bootstrap phase.","marker":"[17]"},{"why":"Motivates and analyses the joining protocol in dynamic distributed networks that underlies the link-manager view.","marker":"[24]"},{"why":"Provides the dynamic-network-with-churn framework and flooding baseline that position the model and results.","marker":"[4]"}],"fun_headline_variants":["Churn-proof expander: rumor spreading O(log n)","Threshold rule keeps expander under churn, so gossip is fast","Node churn no hurdle: rumor spreading reaches O(log n) rounds","Streaming churn still yields fast rumor spreading","O(log n) rumor spread despite streaming node churn"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire analysis assumes that every connection request targets a destination chosen independently and uniformly at random among the currently alive vertices; if a link manager returned biased or correlated destinations, the near-product bound and the expansion and rumor-spreading conclusions would no longer be guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["Churn-proof expander: rumor spreading O(log n)","Threshold rule keeps expander under churn, so gossip is fast","Node churn no hurdle: rumor spreading reaches O(log n) rounds","Streaming churn still yields fast rumor spreading","O(log n) rumor spread despite streaming node churn"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000882,"raw_usage":{"total_tokens":3839,"prompt_tokens":1000,"completion_tokens":2839,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":2755}},"tokens_in":616,"tokens_out":2839,"duration_ms":22965,"temperature":1.0,"reasoning_tokens":2755,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T10:39:45.493897+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the TSG(n,d,c) process for many independent rounds and, at each t ≥ 2n, measure the conductance of every subset of size β log n and the size of the largest induced expander subgraph. The theorem predicts constant conductance for all such subsets and an induced expander on n − O(log n) vertices; if a constant fraction of rounds showed a subset of size β log n with conductance below 1/(10(c+1)d), or more than O(log n) vertices outside the expander, the claim would be refuted. A targeted test of the model assumption is to substitute a link manager that returns only vertices from a fixed half of the population: the near-product bound already fails in that variant, and the same empirical measurements should show the expansion property breaking.","supporting_citations":[{"cited_title":"Becchetti, A","cited_arxiv_id":null,"evidence_quote":"Defines the original RAES protocol whose request-acceptance rule is combined with churn here."},{"cited_title":"Becchetti, A","cited_arxiv_id":null,"evidence_quote":"Supplies the streaming node-churn model and the near-uniform destination lemma that Lemma 4.1 extends to joint distributions."},{"cited_title":"Chierichetti, G","cited_arxiv_id":null,"evidence_quote":"Gives the conductance-based rumor-spreading bound for bounded-degree graphs used after the bootstrap phase."},{"cited_title":"Cooper, R","cited_arxiv_id":null,"evidence_quote":"Motivates and analyses the joining protocol in dynamic distributed networks that underlies the link-manager view."},{"cited_title":"Augustine, G","cited_arxiv_id":null,"evidence_quote":"Provides the dynamic-network-with-churn framework and flooding baseline that position the model and results."}],"review_version":1}