{"id":"295be87b-de47-46e4-8190-5d93aecfc8e2","arxiv_id":"2506.04368","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"A fully-distributed randomized protocol that maintains a constant-degree expander among honest nodes under stochastic churn and up to o(n/log n) Byzantine nodes, with polylogarithmic per-node overhead.","lead":"This paper gives a distributed protocol that keeps a peer-to-peer network well connected while nodes constantly join, leave, and some misbehave. It matters because it could let blockchains and other dynamic networks run agreement and routing algorithms without assuming the network is already well connected.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 9 does not establish the base case of the induction: it asserts expansion at t1=Θ(√n) with 'it is easy to show' and 'by symmetry', while ignoring that earlier random-walk rewirings already presuppose the expander property the lemma must prove.","rationale":"The reader's weakest-assumption analysis identifies Lemma 9 as the load-bearing gap, and my reading agrees: Theorem 2's induction in Lemma 8 is sound only if a base-case expander exists at t1=Θ(√n), and Lemma 9 is the sole place where this is claimed. I found no more fundamental problem: the protocol idea is coherent, the adaptation of the Byzantine Random Walk theorem is plausible, the polylogarithmic message and computation claims follow from the algorithm's design, and the conductance argument in Lemma 8, while compressed and containing some typographical errors, is a recognizable union-bound argument conditional on a good expander core. The base case, however, is not derivable from Lemma 6 alone, because Lemma 6 addresses a single new node's initial connections and does not account for the accumulated effect of protocol-driven rewirings before t1; those rewirings are justified only by Theorem 1, whose hypothesis is the expander property Lemma 9 must establish. This is a proof gap rather than a demonstrated falsehood: the graph at t1 may well be an expander, and a standard random-graph analysis may repair the lemma. Therefore the appropriate disposition remains CONDITIONAL: the central claim is credible and potentially fixable, but the current manuscript does not rigorously establish it. I would not escalate to REJECT because there is no identifiable internal inconsistency that makes the theorem false, and I would not lower to ACCEPT because the base case is genuinely unproved. The verdict should stay as the reader set it: CONDITIONAL, with the base-case proof as the required revision.","tokens_in":26833,"tokens_out":14336,"duration_ms":149303,"concrete_test":"Independently derive Lemma 9 without invoking the expander assumption. Concretely: (a) analyze the distribution of G_{t1} under Algorithm 1 for t1=Θ(√n) and prove that the graph formed by the initial Entry Manager connections—each node choosing d out-neighbors almost uniformly, subject to the 6d incoming-degree cap—is, whp, a constant-degree expander for the d used in Lemma 8; then prove that the first Θ(√n/log n) phases of rewirings either preserve expansion or can be coupled to independent resampling. (b) As a check, simulate the idealized d-out process with N=10^5–10^6 nodes, no Byzantine nodes, and no rewirings, and measure the spectral gap or conductance of the subgraph at t=√N over many runs. If the idealized d-out graph fails to be a constant-degree expander for the advertised d, Lemma 9 is false as stated; if it passes, the gap is in the proof rather than the claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main theorem (Theorem 2) is proved by induction in Lemma 8, and the induction rests entirely on the base case at t1=Θ(√n) claimed in Lemma 9. Lemma 9 is not actually proved. It partitions the nodes at time t1 into S1 (nodes alive at √n) and S2 (nodes joining in [√n, 2√n]). For S2, it says that because new nodes connect to S1 nearly uniformly, \"it is easy to show\" that all subsets of S2 have conductance at least ϕ′. For S1, it says \"By symmetry\" all subsets of S1 have conductance at least ϕ′. No derivation is given for either statement. In particular, the graph induced by S1 at time t1 is not the graph formed when those nodes first joined: before t1, the protocol has already run Θ(√n/log n) phases in which nodes dropped and reconnected edges using verified tokens from Byzantine random walks. The Byzantine Random Walk Theorem (Theorem 1) and its use in Lemma 8 assume that a constant-degree expander subgraph exists at the start of each phase; Lemma 9 is the only place where that initial expander is supposed to be established. Thus the proof either ignores the effect of those earlier rewirings or implicitly assumes the very property it must prove. There is also a secondary gap in the S2 claim: Lemma 6 analyzes a single new node connecting to d honest nodes, but Lemma 9 needs conductance for the whole set of Θ(√n) newly arriving nodes simultaneously, accounting for incoming-degree caps and rejections. The claim may be true and repairable, but as written the induction has no secure base.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a randomized, fully-distributed protocol (Algorithm 1) that aims to construct and maintain a bounded-degree expander graph among honest nodes in a dynamic peer-to-peer network subject to stochastic churn and a full-information Byzantine adversary. The protocol uses an entry manager, phase-based edge rewirings, and a Byzantine random-walk sampling mechanism adapted from the authors' earlier work. The main result (Theorem 2) claims that for every t >= Θ(√n), with probability 1 - 1/n^Ω(1), the maintained graph contains a constant-degree expander subgraph of size (1 - o(1))|V_t| while tolerating o(|V_t|/log |V_t|) Byzantine nodes. The proof proceeds by induction over phases: Lemma 8 assumes an expander core at the start of a phase and shows the invariant is preserved; Lemma 9 is supposed to establish the base case at t = Θ(√n).","tokens_in":27210,"tokens_out":4076,"duration_ms":46148,"significance":"If the main theorem were proved, the result would be significant: it would provide the first protocol that actually constructs and maintains an expander under both continuous churn and a large Byzantine population, thereby removing the ever-present-expander assumption used in several prior distributed algorithms. The protocol is lightweight and plausible, and the paper explicitly connects the construction to existing Byzantine agreement and leader-election algorithms. The authors also correctly identify the key difficulty of controlling Byzantine influence on random-walk sampling and use a phase-based reconnection mechanism to fight expansion decay. However, the proof as written contains a serious gap in the base case of the induction and an unsupported treatment of edges that survive from previous phases; these issues are load-bearing for the claimed theorem. The paper ships no machine-checked proofs or reproducible code; its main assets are the algorithmic idea and the high-level structure of the proof.","major_comments":[{"comment":"Lemma 9, which is the base case for the entire induction, is asserted rather than proved. The proof says 'it is easy to show (similar to the argument in Lemma 8) that all subsets of S2 have conductance at least phi'' and 'By symmetry, for d sufficiently large, we can show that all subsets in S1 have conductance at least phi''. No derivation is given for either statement. This is not a minor omission: the induction in Lemma 8 and the Byzantine Random Walk Theorem (Theorem 1) both require that the honest subgraph at the start of each phase is an expander, and Lemma 9 is the only place where the initial expander at t1 = Θ(√n) is supposed to be established. Moreover, the S1 case is not symmetric to the initial-joining analysis: by time t1 the nodes in S1 have already been through Θ(√n/log n) phases in which they dropped and reconnected edges, so the graph induced by S1 is not the simple random graph created when those nodes first joined. The proof therefore either ignores the effect of earlier rewirings or implicitly assumes the very property it must prove.","section":"Section 3.3, Lemma 9"},{"comment":"The induction step treats all outgoing edges in ES as independent, freshly random edges with Pr(X_i = 1) ≤ aq/n. This is not justified by Algorithm 1: in each phase a node drops only d of its connections when its outgoing degree is at least 2d, and otherwise establishes up to 3d - d_out connections; a large fraction of the edges present at time t+η log n are edges that survived from earlier phases. Those surviving edges are correlated with the history of rewirings and are not independent random samples from the current node set. The conductance bound `|ES| - |E(S,S)| >= phi'|ES|` is proved by treating all edges as if they were freshly sampled at the end of the phase. As written, the argument does not apply to the actual graph maintained by the protocol, so the induction step does not establish the invariant.","section":"Section 3.3, Lemma 8"},{"comment":"The displayed equation `|ES| = |E(S, S)| + |E(S, S)|` is internally inconsistent: both terms on the right are identical, so it would imply |E(S,S)| = 0. The intended second term is presumably |E(S, V \\ S)| (or E(S, \\bar S)), but as written the equation is meaningless. Since this equation is the starting point for the conductance calculation, it must be corrected and the subsequent bound re-derived before the proof can be evaluated.","section":"Section 3.3, Lemma 8 (equation with |ES|)"},{"comment":"The last paragraph of the lemma asserts that new nodes joining during a phase connect to at least d nodes supplied by the Entry Manager, that each such connection has constant probability of connecting to the core, and that 'it is easy to show that any subset of the new nodes has conductance at least phi''. Lemma 6 only analyzes a single new node's success probability in one connection attempt; it does not jointly analyze the set of Θ(log n) new nodes in a phase, accounting for incoming-degree caps, token verification, and the fact that a new node's candidate list is drawn from the entry manager's nodesList rather than from the core. A joint conductance argument for the newly added nodes is needed for the induction step to go through, but none is provided.","section":"Section 3.3, Lemma 8, treatment of new nodes"}],"minor_comments":[{"comment":"The notation E(U, V) is used before it is defined, and the definition in the proof ('the set of edges with a node in set U connected by an outgoing edge to a node in set V') is informal and does not resolve the S/S duplication. Please define the cut notation and fix all occurrences consistently.","section":"Section 3.3, notation in Lemma 8"},{"comment":"The prose around the new-node connection rule says a node accepts a connection 'if the connection is a verified one and if the incoming degree is 6d; otherwise it will reject'. This appears to be the opposite of the intended rule, which should accept when the incoming degree is less than 6d. The pseudocode in Algorithm 1 (lines 9-12) is clearer, but the prose should be corrected to match it.","section":"Section 2, Algorithm 1 description"},{"comment":"The proof refers to 'the same theorem for time steps between this phase' and says the core 'proves the theorem for time steps between this phase', but the invariant is only stated for phase boundaries. The intermediate-time argument is sketched in one sentence and should be expanded or made precise.","section":"Section 3.3, Lemma 8 proof"},{"comment":"Theorem 1 is imported as an adaptation of the Byzantine Random Walk Theorem from [5], but the manuscript should state explicitly which parts of the proof are new for the dynamic setting and which are verbatim from [5]. Moreover, Lemma 12 has a sentence beginning 'As lemma the states' and a comparison that is difficult to parse; please rewrite it.","section":"Section 3.1, Theorem 1 and Definition 3.2"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an important open problem and the protocol design is plausible, but the proof is not yet in a publishable form. The base case Lemma 9 is the most serious issue: the entire induction and the applicability of the Byzantine Random Walk Theorem rest on it, and the current text does not establish it. The Lemma 8 induction also needs a substantially more careful treatment of surviving edges, and the conductance equation has an obvious typo that affects the formal argument. I would send this back for major revision rather than reject, because the gaps appear repairable in principle, but the authors need to provide a genuine proof of the base case and a correct induction over phases."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper attacks a real gap in the dynamic P2P literature: maintaining a bounded-degree expander under simultaneous continuous churn and a super-polylogarithmic number of Byzantine nodes. The high-level approach is genuinely new and sensible, combining the verified-token random walks from Augustine, Dufoulon, and Pandurangan with the periodic-reconnection idea from the churn-only line of work. If the theorem is true, it removes a major expander assumption from several Byzantine agreement and leader-election results. The protocol itself is lightweight and the Byzantine Random Walk Theorem is adapted with a complete proof in the appendix, which is more than many papers in this area do.\n\nThe soft spots are concentrated exactly where the reader says. Lemma 9, the base case at t1 = Θ(√n), is asserted rather than proved: \"it is easy to show\" for S2 and \"by symmetry\" for S1. That is load-bearing because Lemma 8's induction and the imported Byzantine Random Walk Theorem both presuppose an honest expander at the start of each phase. Without a real base-case argument, the bootstrap has no foundation. Lemma 8 also treats all outgoing edges at the end of a phase as freshly sampled, ignoring that some edges from the previous phase survive and are not re-randomized; that is a genuine gap in the conditional-independence argument. There is also a symbolic slip in the conductance proof where |ES| = |E(S,S)| + |E(S,S)| is written; it is probably a typo, but it obscures the argument.\n\nTwo smaller concerns align with the reader but should not be overstated. The entry manager is trusted to hand out near-uniform random samples, and while the paper says the role is minimal, it is still a trust assumption that deserves flagging. And the churn rate in the model is constant (λ = 1 per round by scaling), so describing the setting as \"high churn\" is an overstatement relative to prior work that handles √n or linear churn per round.\n\nNone of this makes the work unserious. The authors know they are relying on a base case, they state the model and the adversary clearly, and the gaps are specific and plausibly repairable. This is the kind of paper that deserves a serious referee: not desk reject, but with firm requests to actually prove Lemma 9, to rework the induction with explicit accounting of surviving edges, and to clean up the conductance proof. I would not cite the main theorem as established until the proof is fixed, but I would certainly read a revised version.","headline":"First credible attempt at maintaining a bounded-degree expander under both stochastic churn and many Byzantine nodes, but the proof of the core theorem is not yet rigorous: the base case is hand-waved and the induction oversimplifies edge persistence.","tokens_in":27723,"tokens_out":1808,"would_cite":false,"duration_ms":21102,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68W15","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"A fully distributed protocol maintains a constant-degree expander overlay while Byzantine nodes and continuous churn are present.","keywords":["peer-to-peer networks","Byzantine fault tolerance","expander graphs","distributed algorithms","dynamic networks","random walks","churn","overlay networks"],"falsifier":"Run the protocol under the paper's stochastic churn model and, at every phase boundary, compute the conductance of the largest honest subgraph after deleting Byzantine nodes; the theorem predicts a fixed constant lower bound for all t ≥ Θ(√n), so a phase where the honest core's conductance drops below any fixed constant with non-negligible probability would refute it. On the proof side, the base case is the weakest spot: writing out Lemma 9's easy-to-show step would either establish or refute that the honest subgraph at t1 = Θ(√n) is an expander, and a legal churn trajectory where it is not would break the induction regardless of later phases.","tokens_in":26597,"feed_emoji":"🕸️","tokens_out":5404,"duration_ms":49442,"temperature":0.7,"pith_summary":"The paper claims that a randomized, fully distributed protocol can build and maintain a sparse overlay network with high expansion even while nodes continuously join and leave and a large number of them are Byzantine, i.e., adversarially malicious. Previous algorithms for agreement, leader election, and storage in dynamic P2P networks assumed such an expander was already supplied each round; this protocol is meant to be the component that actually supplies it. If the claim holds, it closes the gap between algorithms that need an expander and realistic networks that must construct one under churn and attack, and it does so with only polylogarithmic communication and computation per node per round.","feed_headline":"Protocol keeps P2P overlay an expander under Byzantine churn","feed_subtitle":"Only polylog bits per node per round keep a large honest expander core alive.","key_machinery":"The carrying mechanism is the Byzantine Random Walk Protocol (Algorithm 3), adapted from the static setting. Each honest node launches O($log^{3}$ n) tokens per phase; each token walks c log n steps, and a token that survives is verified and returned, via the reverse path, to its source, which then uses verified tokens to form new connections. Neighbors that send more than cap tokens per round are blacklisted, which bounds the influence of Byzantine flooding. The protocol refreshes connections every η log n rounds, a phase, so deletions do not permanently degrade expansion. The Byzantine Random Walk Theorem (Theorem 1), assuming a static core of honest nodes within a phase, guarantees that most tokens from most core nodes mix almost uniformly inside the core, giving the near-random samples that drive new edges.","core_discovery":"The central claim is Theorem 2: for any time t ≥ Θ(√n), with probability at least 1 − 1/n^Ω(1), the P2P Construction Protocol maintains a bounded-degree graph G_t containing a subgraph of at least (1−o(1))|V_t| honest nodes that is a constant-degree expander, while tolerating up to o(|V_t|/log(|V_t|)) Byzantine nodes. Once the network stabilizes at t ≥ 3n, the guaranteed subgraph has size (1−o(1))n and the protocol tolerates o(n/log n) Byzantine nodes. The protocol is fully distributed in the sense that each node knows only its neighbors and a rough estimate of n, and each honest node processes and sends only O(polylog n) bits per round.","pith_inferences":["The base case at t1 = Θ(√n) is asserted rather than derived: Lemma 9 says the honest subgraph is an expander there by it is easy to show and by symmetry arguments. If that base case is false, the induction in Lemma 8 has no starting point; this is the place to attack the theorem.","The protocol tolerates only stochastic churn; extending the same construction to adversarial churn would require a different argument, since the entry manager and phase-based refresh both rely on Poisson arrival and memoryless departure statistics.","A natural testable extension is to instantiate the protocol at moderate n and measure whether the honest subgraph's conductance stays above a fixed constant across phases; the theorem predicts this for all sufficiently large n, and simulation could expose an early-n breakdown or an unexpectedly large constant.","The verified-token mechanism suggests a general template: any task that needs uniform sampling in a Byzantine network can be layered on these random walks as long as a core expander exists."],"forward_implications":["If the construction holds, algorithms for Byzantine agreement, Byzantine leader election, and storage and search in dynamic P2P networks can run on top of the maintained expander rather than assuming one is given.","The guarantee is maintained continuously at every phase boundary, not only after stabilization: from t = Θ(√n) onward the honest expander subgraph has size (1−o(1)) of the network.","Because each honest node only sends and processes polylogarithmic bits per round, the protocol is scalable enough to be used as a building block in large decentralized systems.","The Byzantine tolerance of o(n/log n) is within a logarithmic factor of the paper's conjectured barrier for any fully distributed protocol in sparse networks."],"supporting_citations":[{"why":"supplies the Byzantine Random Walk Theorem and verified-token technique that the protocol adapts to dynamic graphs.","marker":"[5]"},{"why":"introduces the stochastic churn (M/M/∞) model and the stable network size lemmas the analysis relies on.","marker":"[38]"},{"why":"provides the lemma that a constant-degree expander minus o(n) Byzantine nodes still contains a large constant-conductance honest core.","marker":"[9]"},{"why":"supplies the combinatorial inequality used as Lemma 7 in the conductance union bound.","marker":"[17]"}],"fun_headline_variants":["Constant-degree expander kept under Byzantine churn with polylog overhead","Fully distributed protocol maintains expander despite Byzantine nodes","Polylog bits per round per node yield robust expander under Byzantine attack","Protocol tolerates o(n/log n) Byzantine nodes while preserving expansion","Randomized fully distributed construction of Byzantine-resilient expander"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that early on, when the network first reaches size on the order of the square root of its stable size, the honest nodes already form a sparse, well-connected graph with high expansion; the paper asserts this in Lemma 9 with an it is easy to show argument, and if this base case is not true the later induction cannot start.","fun_headline_variants_meta":{"raw":{"variants":["Constant-degree expander kept under Byzantine churn with polylog overhead","Fully distributed protocol maintains expander despite Byzantine nodes","Polylog bits per round per node yield robust expander under Byzantine attack","Protocol tolerates o(n/log n) Byzantine nodes while preserving expansion","Randomized fully distributed construction of Byzantine-resilient expander"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000447,"raw_usage":{"total_tokens":2302,"prompt_tokens":1032,"completion_tokens":1270,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":648,"completion_tokens_details":{"reasoning_tokens":1180}},"tokens_in":648,"tokens_out":1270,"duration_ms":11340,"temperature":1.0,"reasoning_tokens":1180,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:45:40.798666+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the protocol under the paper's stochastic churn model and, at every phase boundary, compute the conductance of the largest honest subgraph after deleting Byzantine nodes; the theorem predicts a fixed constant lower bound for all t ≥ Θ(√n), so a phase where the honest core's conductance drops below any fixed constant with non-negligible probability would refute it. On the proof side, the base case is the weakest spot: writing out Lemma 9's easy-to-show step would either establish or refute that the honest subgraph at t1 = Θ(√n) is an expander, and a legal churn trajectory where it is not would break the induction regardless of later phases.","supporting_citations":[{"cited_title":"Fully- distributed byzantine agreement in sparse networks","cited_arxiv_id":null,"evidence_quote":"supplies the Byzantine Random Walk Theorem and verified-token technique that the protocol adapts to dynamic graphs."},{"cited_title":"Building low-diameter p2p networks","cited_arxiv_id":null,"evidence_quote":"introduces the stochastic churn (M/M/∞) model and the stable network size lemmas the analysis relies on."},{"cited_title":"Enabling robust and efficient distributed computation in dynamic peer-to-peer networks","cited_arxiv_id":null,"evidence_quote":"provides the lemma that a constant-degree expander minus o(n) Byzantine nodes still contains a large constant-conductance honest core."},{"cited_title":"Moses Jr., and Gopal Pandurangan","cited_arxiv_id":null,"evidence_quote":"supplies the combinatorial inequality used as Lemma 7 in the conductance union bound."}],"review_version":1}