{"id":"fae1ba4e-5ef0-4e4a-a0a8-aa93bde8d74b","arxiv_id":"2505.05735","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Error correcting codes, locally decodable codes, and a new resilient routing primitive allow O(1)-round simulation of Congested Clique rounds under per-node bounded-degree edge corruption.","lead":"This paper shows that any protocol for the fully connected Congested Clique can be simulated with only a constant factor slowdown even when a mobile Byzantine adversary corrupts a constant fraction of each node's incident edges in every round. It also gives an adaptive-adversary simulation with n^{2-o(1)} total corrupted edges, up from the previous linear bound.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of the cover-free lemma (Lemma 4.3) contains a numerically incorrect Chernoff bound, so the stated parameter range is unsupported; the flaw is repairable and does not affect the used regimes.","rationale":"The reader flagged Lemma 4.3 as the weakest assumption; I agree it is the key dependency, but the specific load-bearing issue is not merely that the construction is unverified—it is that the proof's Chernoff bound is quantitatively wrong, so the LLL condition does not follow for the stated k range. However, since all concrete compilers operate in regimes where the correct bound is overwhelmingly small (k = n^{o(1)} or smaller), the main results are very likely correct. I recommend conditional acceptance: the paper should correct the Chernoff calculation and the variable indexing in Appendix A, and should state the effective constant in k = O(n/log n) that makes Lemma 4.3 valid. No other issue of comparable weight emerged: the routing analysis, the non-adaptive and adaptive compilers, and the deterministic constructions all appear internally consistent.","tokens_in":69,"tokens_out":45290,"duration_ms":1105524,"concrete_test":"Re-derive the bad-event probability using the multiplicative Chernoff bound Pr(X ≥ (1+ε)μ) ≤ exp(-ε μ/3) for ε ≥ 1 with μ = E[X] ≤ δL/2, compute the maximum degree d of the LLL dependency graph (d ≤ (r+1)|H|), and verify whether epmax d^{1.5} < 1 holds for k = ĉ n/log n with the ĉ used in Lemma 4.2. Additionally, run a small computational instantiation of the randomized construction (e.g., N=2^20, k=2^10, δ=1/50, |H|=2N) and empirically estimate Pr(bad) over random H; if the observed fraction of violating tuples is far above 1/N^4, the Chernoff estimate in the proof is confirmed wrong.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central routing theorem (Theorem 4.1) rests on Lemma 4.3. In the randomized proof (Section 4.1 and Appendix A), X is a sum of L independent Bernoulli variables with mean μ ≤ δL/2; the paper claims Pr(X > δL) ≤ e^{-c' log N /12} whenever L ≥ c' log N. The standard Chernoff bound gives Pr(X ≥ 2μ) ≤ exp(-μ/3) ≤ exp(-δL/6), which for δ = 1/50 is exp(-L/300), not exp(-L/12). Consequently pmax is roughly exp(-L/300), and to obtain pmax ≤ 1/(e N^2 |H|^2) one needs L ≥ (600+300c2) log N, not L ≥ (24+12c2) log N. Since L = floor(δN/(4(r+1))) ≈ N/(200k), this requires k ≤ N/(C log N) with C ~ 120000, much smaller than the O(N/log N) stated in Theorem 4.1. For k = Θ(N/log N) the LLL criterion epmax d^{1.5} < 1 fails. In addition, Appendix A defines the LLL random variables only for 0 ≤ i ≤ r, while the cover-free family has m sets; this must be i ∈ [m]. Both issues are technical: the compilers in the paper use k = n^{o(1)} (adaptive, Theorem 5.5), k = O(1) (non-adaptive and deterministic Θ(1)), or k = O(√n) (deterministic 1/√n), for which L = n^{1-o(1)} or n^{1/2} and even the correct Chernoff bound makes pmax super-polynomially small. The main theorems are therefore expected to survive a corrected proof, but Lemma 4.3 as written is not proved for its claimed range.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the AllToAllComm problem in the Congested Clique under a mobile Byzantine edge adversary with bounded faulty degree, deg(F_i) <= alpha n. For the non-adaptive adversary it presents a randomized O(1)-round compiler with alpha = Theta(1) and bandwidth B = Theta(log n); for the adaptive adversary it presents a randomized O(1)-round compiler with alpha = exp(-sqrt(log n log log n)) and B = 1; and it presents deterministic compilers with O(log n) rounds for constant alpha and O(1) rounds for alpha = Theta(1/sqrt(n)). The key technical ingredient is a deterministic resilient super-message routing scheme (Theorem 4.1), built from Justesen codes, a new cover-free family construction, and, in the adaptive case, locally decodable codes and sparse recovery sketches.","tokens_in":38510,"tokens_out":14145,"duration_ms":134929,"significance":"Assuming correctness, the results are a clear advance over the previous mobile-edge-adversary compiler of Fischer and Parter [32], improving the per-round corruption budget from Theta~(n) to n^{2-o(1)} corrupted edges while reducing round overhead to O(1). The routing formulation is a natural adversarial analogue of Lenzen routing and is likely to be reused. The proof structure is modular, and the analysis of the two-round routing (Lemmas 4.5-4.7) is careful; the adaptive simulation bounds are coherent with the external LDC parameters. The paper does not assume its own conclusions: the fault thresholds come from Justesen codes and the KMRS LDC, and the protocols reduce to routing and coding primitives. The main reservation is a numerically incorrect Chernoff bound in the proof of the cover-free family lemma; it is repairable and does not affect the concrete parameter regimes used by the main theorems, but it must be fixed.","major_comments":[{"comment":"The Chernoff bound used to bound Pr(X > delta L) is not correct. Since X is a sum of L independent Bernoulli variables with mean mu <= delta L/2, the multiplicative Chernoff bound gives Pr(X > delta L) <= exp(-delta L/6), i.e., exp(-L/300) for delta = 1/50, not exp(-L/12). Consequently the requirements L >= (24+12c2) log N in Section 4.1 and L >= (36+24c2) log N in Appendix A are too small by a factor of about 25; to obtain pmax <= 1/(e N^2 |H|^2) one needs L = Omega((1+c2) log N / delta). Because L = floor(delta N/(4(r+1))), the proof as written does not establish Lemma 4.3 for the full stated range r+1 <= c1 delta N / log N, and hence does not establish Lemma 4.4 and Theorem 4.1 for k = Theta(N/log N) with the stated constants. The issue is repairable by choosing c1 small enough so that L >= C log N for the correct constant C, and the main applications use k = n^{o(1)}, k = O(1), or k = O(sqrt(n)), where L is much larger than any constant multiple of log n; but the proof must be corrected.","section":"Section 4.1 and Appendix A, Lemma 4.3"}],"minor_comments":[{"comment":"The random variable set is declared as Y = {Y_{i,j} | 0 <= i <= r, j in [L]}, but the cover-free family consists of m sets indexed by i in [m]. The bad events are defined for arbitrary i0 in [m], so the variables must be Y_{i,j} for all i in [m]; otherwise the LLL instance does not cover all sets in the family.","section":"Appendix A, LLL construction"},{"comment":"The Chernoff bound is applied to a single pair (u,v), but the correctness statement is for all pairs simultaneously. Add the standard union bound over n^2 pairs and state the required constant in the exponent.","section":"Section 5.1, Lemma 5.4"},{"comment":"The line 'b = O(nt/n) = O(t)' is confusing; since x = Theta(n), it should simply read b = O(t).","section":"Section 5.2, Lemma 5.9"},{"comment":"The phrase 'alpha = Omega(1)' conflicts with 'sufficiently small constant'; this should be alpha = Theta(1) with alpha smaller than the constant required by Theorem 4.1.","section":"Section 1, Theorem 1.4"},{"comment":"The bandwidth entry for the deterministic Theta(1) row lists B in {1,...,polyn}; this is fine, but consider clarifying that the O(log n) round bound already holds for B = 1.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a strong and timely contribution. My recommendation of major revision is driven by the incorrect Chernoff bound in the proof of Lemma 4.3, which is a load-bearing lemma. I expect the authors can repair it with a constant adjustment; after that, the paper should be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The bottom line: this is a substantial paper with a genuine new result, but the proof of Lemma 4.3, which the entire routing scheme rests on, is not correct as written. I would still send it to peer review, but with the expectation that the authors fix the lemma's proof.\n\nWhat's actually new: the bounded-degree mobile Byzantine edge adversary is new to communication settings, and the paper shows how to simulate Congested Clique rounds against it with O(1) rounds of overhead, tolerating up to n^{2-o(1)} edge corruptions adaptively and Theta(n^2) non-adaptively or deterministically. That's a real jump from the Theta(n) faults in Fischer-Parter PODC 2023. The resilient super-message routing scheme (Theorem 4.1) is a nice analogue of Lenzen routing, and the combination of LDCs with sparse recovery sketches in the adaptive construction is coherent.\n\nThe main routing analysis (Lemmas 4.5-4.7) is careful and correct: it tracks corruptions round by round and uses deg(F) <= alpha n plus the cover-free overlap bounds to keep the error below half the ECC distance. The paper is honest about what depends on external constructions, and I see no circularity or fitting.\n\nThe soft spot is Lemma 4.3. The randomized proof claims Pr(X > delta L) <= e^{-c' log N / 12} when L >= c' log N. But X has mean at most delta L / 2, so the standard Chernoff bound gives exp(-delta L / 6), not exp(-c' log N / 12). With delta = 1/50, the constant is off by roughly a factor of 25. The LLL derandomization in Appendix A also defines random variables only for indices 0..r when it should define them for all m sets in the family. Both issues are repairable, and the paper's main theorems survive: the compilers use k = n^{o(1)}, k = O(1), or k = O(sqrt n), which make L = n^{1-o(1)} or n^{1/2}, so even the corrected Chernoff bound gives super-polynomially small failure probability. But Lemma 4.3 as stated claims support for k = O(n / log n), and that range is not proved with the current argument. A corrected proof would need a smaller constant in the k bound or a different construction.\n\nThis paper is for distributed computing researchers working on Byzantine fault tolerance and Congested Clique algorithms. It deserves a serious referee, and I expect it will be accepted after a moderate revision that fixes the cover-free lemma. I would cite it in my own work.\n\nRecommendation: send to peer review.","headline":"Strong contribution with a real result, but the cover-free lemma at the heart of the routing theorem has a fixable proof bug that needs correction before publication.","tokens_in":39134,"tokens_out":3253,"would_cite":true,"duration_ms":33582,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","68P30","94B60"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that any Congested Clique round can be simulated in O(1) rounds when faults are capped by per-node degree, tolerating n^{2-o(1)} corruptions against an adaptive adversary.","keywords":["Congested Clique","Byzantine mobile adversary","bounded-degree edge faults","all-to-all communication","locally decodable codes","cover-free families","sparse recovery sketches","distributed compilers"],"falsifier":"Take $n$ large enough for Lemma 4.3's hypotheses, say $k=\\lfloor n/\\log n\\rfloor$, $\\delta=1/50$, and $H$ the $2kn$ input and output index sets, run the deterministic local-lemma construction, and check every tuple in $H$: if any set $A_{i_0}$ has fewer than $(1-\\delta)|A_{i_0}|$ elements outside the union of any $k-1$ other sets from $H$, the routing lemma fails. A direct simulation alternative: run SMRoutingProtocol with an adaptive adversary that corrupts any chosen $\\alpha n$ edges per node per round; a single target node that fails to decode its super-message, meaning the received error fraction reaches $\\delta_C/2$, would refute the routing theorem's guarantees.","tokens_in":37915,"feed_emoji":"📡","tokens_out":9770,"duration_ms":95509,"temperature":0.7,"pith_summary":"This paper asks whether the classical total-fault bound in the Congested Clique can be replaced by a per-node degree bound without slowing down computation. It answers yes: for a sufficiently small constant $\\alpha$, a randomized compiler simulates any fault-free Congested Clique round in $O(1)$ rounds while a non-adaptive adversary corrupts up to $\\alpha n$ edges at each node, and a second compiler does the same against an adaptive adversary with $\\alpha=\\exp(-\\sqrt{\\log n \\log\\log n})$ using only one bit of bandwidth. Because each round is simulated with constant overhead, any $r$-round algorithm becomes $O(r)$ rounds in the resilient model. The significance is that the model can now tolerate almost quadratically many edge failures per round, a regime impossible under total-count bounds.","feed_headline":"Constant-round simulation survives n^{2-o(1)} edge faults","feed_subtitle":"Any Congested Clique round stays O(1)-round safe with an α-fraction of faulty edges per node.","key_machinery":"The load-bearing object is a deterministic resilient super-message routing scheme, the adversarial analogue of Lenzen routing. An instance has $k=O(1/\\alpha)$: each node is the source and target of at most $k$ super-messages of $O(\\alpha n)$ bits with known target sets, and the scheme delivers them in $O(1)$ rounds under an adaptive bounded-degree adversary. The scheme encodes each super-message with a constant-rate, constant-distance error-correcting code and assigns each codeword bit to a helper node set $A(u,j)$ drawn from a $(k-1,\\delta)$-cover-free family, constructed deterministically via a local-lemma algorithm. The cover-free property guarantees that, for any target, only a small $\\delta$-fraction of helper nodes are contested by other messages, while the degree bound guarantees at most $O(\\alpha k)$ corrupted bits per codeword, keeping the received word within half the code distance. The adaptive compiler layers a locally decodable code and sparse-recovery sketches on top: the code's non-adaptive query pattern lets each node fetch the same $q$ positions for all of its sketches at once, and the sketches keep the data to recover at $O(\\alpha n \\log^2 n)$ bits, which is why the adaptive threshold is $1/(q \\log^6 n)$.","core_discovery":"The central claim is that AllToAllComm, the task of delivering for every ordered pair $(u,v)$ the message $m_{u,v}$, admits $O(1)$-round solutions under the $\\alpha$-Byzantine-degree mobile adversary. The non-adaptive solution uses random permutations and error-correcting codes: each codeword bit travels over a secretly random edge, so although an $\\alpha$-fraction of bits may be corrupted, the code distance leaves decoding correct with high probability. The adaptive solution is different, because the adversary sees the randomness: the nodes first exchange raw messages, use sparse-recovery sketches to compress the corrupted messages at each node, encode the sketches with a non-adaptive locally decodable code of sub-polynomial query complexity, and route the queried positions through the super-message routing scheme; each node decodes only its own sketch and recovers all corrections. The result is that simulation overhead stays $O(1)$ while the per-round fault budget rises from $\\Theta(n)$ total edges to $n^{2-o(1)}$ total edges.","pith_inferences":["The authors state Theorem 5.5 for any locally decodable code with query complexity $q$, so an improved LDC with $q=\\mathrm{polylog}\\, n$ would immediately raise the adaptive threshold to $1/\\mathrm{polylog}\\, n$; they do not speculate on such an improvement.","The cover-free helper-set construction is a routing-independent combinatorial gadget that could plausibly serve other tasks needing many witness sets protected from bounded-degree failures, such as fault-tolerant aggregation or verification.","The deterministic $\\Theta(1)$-fault algorithm's hypercube bit-exchange pattern suggests a deterministic route to fault-tolerant sorting or permutation routing in the same model, though the paper does not develop that direction."],"forward_implications":["Any $r$-round Congested Clique algorithm can be simulated in $O(r)$ rounds against a non-adaptive adversary with constant $\\alpha$ and bandwidth $B=\\Theta(\\log n)$, tolerating $\\Theta(n^2)$ edge corruptions per round.","Against an adaptive adversary, $O(1)$-round simulation per round holds with $B=1$ and $\\alpha=\\exp(-\\sqrt{\\log n \\log\\log n})$, so the adversary may corrupt $n^{2-o(1)}$ edges per round.","A deterministic compiler simulates every round in $O(\\log n)$ rounds with $B=1$ against a constant-fraction adaptive adversary, again tolerating $\\Theta(n^2)$ corrupted edges per round.","A deterministic $O(1)$-round compiler works for $\\alpha=\\Theta(1/\\sqrt{n})$, supporting $\\Theta(n^{3/2})$ corrupted edges per round.","The super-message routing procedure itself is a deterministic $O(1)$-round primitive for any routing instance with $k=O(1/\\alpha)$ sources and targets and $O(\\alpha n)$-bit messages, giving bounded-degree adversarial settings a Lenzen-style routing tool."],"supporting_citations":[{"why":"Introduces the bounded-degree faulty-edge model for graph sparsification and supplies the motivation that degree caps yield linearly more faults at little extra cost.","marker":"[11]"},{"why":"Prior mobile-edge compiler over $\\Theta(n)$ total faults per round; its tree-based upcast breaks even at $\\alpha=1/n$, serving as the baseline this paper improves.","marker":"[32]"},{"why":"Supplies the constant-rate, constant-distance binary error-correcting code used to encode super-messages in the routing scheme.","marker":"[42]"},{"why":"Provides the non-adaptive locally decodable code with constant rate and distance and query complexity $q=\\exp(\\sqrt{\\log n \\log\\log n})$, which determines the adaptive adversary strength.","marker":"[46]"},{"why":"Gives the randomized cover-free set construction that the paper adapts to its weaker variant and then derandomizes.","marker":"[47]"},{"why":"Supplies the deterministic local-lemma algorithm used to make the cover-free family construction deterministic and polynomial-time.","marker":"[38]"},{"why":"Provides the sparse recovery sketches used to compress the set of corrupted messages at each node during the adaptive protocol.","marker":"[21]"},{"why":"Presents the fault-free Lenzen routing scheme that the super-message routing is designed to replace in the adversarial setting.","marker":"[49]"}],"fun_headline_variants":["O(1) rounds survive n^2 edge faults from mobile adversary","Constant-round comm with n^(2-o(1)) edge faults","Mobile edge adversary? Still O(1) rounds, n^2 faults","Quadratic faults for all-to-all comm: no extra rounds","From n to n^2 edge faults, rounds stay O(1)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the cover-free helper-set construction: for the parameters used, there must exist, computable in polynomial time, a family of helper sets in which any one helper set is almost entirely disjoint from the union of any $k-1$ other helper sets; if that construction fails, the routing theorem and every compiler in the paper fail with it.","fun_headline_variants_meta":{"raw":{"variants":["O(1) rounds survive n^2 edge faults from mobile adversary","Constant-round comm with n^(2-o(1)) edge faults","Mobile edge adversary? Still O(1) rounds, n^2 faults","Quadratic faults for all-to-all comm: no extra rounds","From n to n^2 edge faults, rounds stay O(1)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000848,"raw_usage":{"total_tokens":3784,"prompt_tokens":1136,"completion_tokens":2648,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":752,"completion_tokens_details":{"reasoning_tokens":2554}},"tokens_in":752,"tokens_out":2648,"duration_ms":21713,"temperature":1.0,"reasoning_tokens":2554,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:59:09.686891+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $n$ large enough for Lemma 4.3's hypotheses, say $k=\\lfloor n/\\log n\\rfloor$, $\\delta=1/50$, and $H$ the $2kn$ input and output index sets, run the deterministic local-lemma construction, and check every tuple in $H$: if any set $A_{i_0}$ has fewer than $(1-\\delta)|A_{i_0}|$ elements outside the union of any $k-1$ other sets from $H$, the routing lemma fails. A direct simulation alternative: run SMRoutingProtocol with an adaptive adversary that corrupts any chosen $\\alpha n$ edges per node per round; a single target node that fails to decode its super-message, meaning the received error fraction reaches $\\delta_C/2$, would refute the routing theorem's guarantees.","supporting_citations":[{"cited_title":"Fault-tolerant spanners against bounded- degree edge failures: Linearly more faults, almost for free","cited_arxiv_id":null,"evidence_quote":"Introduces the bounded-degree faulty-edge model for graph sparsification and supplies the motivation that degree caps yield linearly more faults at little extra cost."},{"cited_title":"Distributed CONGEST algorithms against mobile adversaries","cited_arxiv_id":null,"evidence_quote":"Prior mobile-edge compiler over $\\Theta(n)$ total faults per round; its tree-based upcast breaks even at $\\alpha=1/n$, serving as the baseline this paper improves."},{"cited_title":"Class of constructive asymptotically good algebraic codes","cited_arxiv_id":null,"evidence_quote":"Supplies the constant-rate, constant-distance binary error-correcting code used to encode super-messages in the routing scheme."},{"cited_title":"High-rate locally cor- rectable and locally testable codes with sub-polynomial query complexity","cited_arxiv_id":null,"evidence_quote":"Provides the non-adaptive locally decodable code with constant rate and distance and query complexity $q=\\exp(\\sqrt{\\log n \\log\\log n})$, which determines the adaptive adversary strength."},{"cited_title":"Coding constructions for blacklisting problems without computational assumptions","cited_arxiv_id":null,"evidence_quote":"Gives the randomized cover-free set construction that the paper adapts to its weaker variant and then derandomizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the deterministic local-lemma algorithm used to make the cover-free family construction deterministic and polynomial-time."},{"cited_title":"A unifying framework for l0-sampling algorithms","cited_arxiv_id":null,"evidence_quote":"Provides the sparse recovery sketches used to compress the set of corrupted messages at each node during the adaptive protocol."},{"cited_title":"Optimal deterministic routing and sorting on the congested clique","cited_arxiv_id":null,"evidence_quote":"Presents the fault-free Lenzen routing scheme that the super-message routing is designed to replace in the adversarial setting."}],"review_version":1}