{"id":"3358f8f3-8862-49dc-8ac0-e7dc5fc042e2","arxiv_id":"2509.05870","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"An adaptive attack defeats the HYZ12 distributed counting protocol, and a simplified round-based sampling protocol achieves optimal communication with white-box robustness.","lead":"This paper shows that a widely used randomized protocol for distributed counting can be broken by an adaptive adversary, then gives a simpler protocol that stays accurate even against white-box attackers. The new protocol matches the best known communication cost for the problem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The attack proof assumes every estimate change is a Report from the targeted site, but BoundaryReached updates also change \\hat n, so the round-robin pointer can advance without a report and Lemma 2.13's bias argument does not follow.","rationale":"The reader's weakest assumption identifies exactly the soft spot: the attack analysis in Section 2.4 assumes that every change in the server's published estimate is caused by a Report from the currently injected site. Careful reading of Algorithm 2 confirms that BoundaryReached events also update \\hat n through the random Z_i adjustments and the new transmission probability p. Since Algorithm 3 observes only \\hat n, it cannot distinguish these causes, so the round-robin pointer can advance without any report. This breaks both the counting argument in Lemma 2.9 and the per-site bias decomposition in Lemma 2.13. The circularity in Observation 2.12 is even more serious: the attack's event stream depends on the observed \\hat n, which depends on server-side randomness, so fixing a reporting transcript does not fix the attack's behavior. This is not a mere presentation issue; the proof of Theorem 2.1 depends on R*_n >= k/2, and if boundary-induced switches are frequent for some parameter regimes, the adversary may fail to accumulate the claimed bias. The concern is load-bearing for the negative result, not for the positive protocol: the robustness and accuracy arguments for Algorithm 4 rest on symmetry and per-round tail bounds that appear sound, and the empirical evaluation supports the qualitative conclusions. The verdict should remain conditional pending a repaired attack proof or an explicit modified attack that is robust to boundary-induced estimate changes.","tokens_in":24820,"tokens_out":26088,"duration_ms":238109,"concrete_test":"Modify the simulator used for Figure 1 so that every pointer advance in Algorithm 3 is tagged as Report-caused or Boundary-caused, and separately count R*_n, the number of distinct sites that actually report in [n/14, n], for the parameter regime of Theorem 2.1 (e.g., k=64, epsilon=0.125, n=500 sqrt(k)/epsilon). If boundary-caused advances occur with non-negligible frequency and R*_n < k/2 on a non-negligible fraction of runs, then Corollary 2.10 and Lemma 2.13 fail as written. As an analytical companion, re-derive Lemma 2.9 with an extra term for BoundaryReached events, using Observation 2.8 to bound their number by O(log n), and verify whether R > k/8 still holds for all claimed parameters, in particular small k where log(sqrt(k)/epsilon) can exceed k/8.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Section 2.4, Lemma 2.9 asserts: \"Each update to the published estimate is caused by a Report message from the site currently injected by the attack.\" This is false for Algorithm 2. On a BoundaryReached event the server changes p and subtracts zero-inflated geometric Z_i from every \\bar n_i, then republishes \\hat n; the estimate can change with no Report from the active site. Algorithm 3 observes only \\hat n, so it treats such boundary-induced changes as report events and advances the round-robin pointer. Consequently, the number R of distinct sites that actually report is not bounded below by the number of observed estimate changes; Corollary 2.10's R*_n >= k/2 and Lemma 2.13's decomposition into one active site with m* events since its last report and k-1 sites with zero events since their last report do not follow from the stated definitions. Observation 2.12 is also circular: the attack's event stream is a function of the published \\hat n, which depends on the server-side Z_i randomness, so a reporting transcript (fixing only site-side randomness) does not uniquely determine the attack's states or the sequence of events. If a non-negligible fraction of pointer advances are boundary-induced, the set of sites with fresh reports can be much smaller than k/2, and the claimed bias Omega(sqrt(k) epsilon n) in Theorem 2.1 lacks support. This is the load-bearing defect in the negative result; the robust protocol in Sections 3-5 appears independent and well-supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the distributed counting problem under adaptive (white-box) adversaries. It makes two claims. First, it constructs an adaptive attack (Section 2) that is said to force the HYZ12 randomized protocol of Huang, Yi, and Zhang to fail with high probability, thereby showing that HYZ12 is not robust. Second, it presents a new protocol, called Robust (Algorithm 4), which is a simplified variant of the HYZ12 scheme and is proven to achieve ε-accuracy for every event index and uniformly over N events, with optimal communication O(√k/ε log N) for ε ≤ 1/√k. The robustness argument rests on a symmetry observation: the server's state and published estimate depend only on the total event count and the number of sampled report messages, not on which site generated the events. The accuracy analysis combines standard concentration bounds for geometric random variables with a renewal-process argument that converts per-round guarantees into per-event-index guarantees.","tokens_in":25138,"tokens_out":14116,"duration_ms":125993,"significance":"If the robust protocol result is correct, it is a significant advance: it gives the first protocol matching the optimal oblivious communication bound in the adaptive white-box setting, with a protocol that is arguably simpler than the prior robust construction of Xiong, Zhu, and Huang, and it resolves an open question explicitly raised in that work. The symmetry-based robustness proof is elegant and convincing, and the concentration arguments are standard. The negative result on HYZ12, if valid, would also be valuable, but the proof as written contains a load-bearing gap concerning the effect of boundary-triggered estimate changes on the attack's round-robin pointer. The positive contribution stands independently and is well supported; the negative contribution needs substantial repair or reframing.","major_comments":[{"comment":"The proof of Lemma 2.9 asserts: 'Each update to the published estimate is caused by a Report message from the site currently injected by the attack.' This is false for Algorithm 2. When a BoundaryReached event occurs, the server subtracts the zero-inflated geometric random variable Z_i from every stored counter ¯n_i and republishes the estimate, so the value of ˆn can change without any Report message from the active site. Algorithm 3 only observes ˆn, so it cannot distinguish a boundary-induced change from a report-induced change and may advance its round-robin pointer prematurely. Consequently, the number R of distinct sites that actually send Report messages is not bounded below by the number of observed estimate changes, and the Chernoff bound applied to Bin(n0, √k/(4εn0)) does not bound R. Corollary 2.10's conclusion that R*_n ≥ k/2 therefore does not follow from the stated argument.","section":"Section 2.4, Lemma 2.9"},{"comment":"Observation 2.12 claims that a reporting transcript, which fixes only the site-side randomness, uniquely determines the sequence of round-start indices, the configured probabilities, the states of the attack, and the event stream. This is incorrect: the attack's decisions are based on the published estimate ˆn, which depends on the server-side randomness Z_i used in the boundary adjustments. Because the event stream is itself a function of ˆn, fixing the site-side randomness alone does not fix the attack's behavior or the resulting event sequence. The conditioning argument in Lemma 2.13 is therefore circular. Additionally, the decomposition into one active site with m* events since its last report and k-1 sites with zero events since their last report is only valid if every pointer advance corresponds to a genuine report from the active site; boundary-induced advances break that decomposition. The bias lower bound in Lemma 2.13, and hence Theorem 2.1, is not established by the present proof.","section":"Section 2.4, Observation 2.12 and Lemma 2.13"}],"minor_comments":[{"comment":"The expression 'p←2 min{0,⌊log2 √k/(εn')⌋}' appears to be missing the exponentiation: it should be 'p←2^{min{0,⌊log2(√k/(εn'))⌋}}' to denote a power of two. This typesetting issue also affects the display in Observation 2.7.","section":"Algorithm 2 and Observation 2.7"},{"comment":"In the proof of Lemma 2.13, the text reads 'Since R*_n ≥ k/8', but the lemma assumes R*_n ≥ k/2. This appears to be a typo; the constants in the bias calculation should be checked for consistency once the attack proof is repaired.","section":"Lemma 2.13 proof"},{"comment":"The bit-complexity lemma is only sketched. In particular, the claim that each site can broadcast its value to an additive error of O(max{1, ε ¯n'/k}) and that this 'can be converted to a high probability or in-expectation bound' is vague and should be made precise, including how sites obtain the proxy ¯n'.","section":"Section 4.2.2, Lemma 4.2"},{"comment":"The term 'reporting transcript' is introduced informally. Since the subsequent analysis conditions on it, a formal definition of which site-side random variables are fixed (e.g., the Bernoulli samples at each site) would improve clarity and help expose the dependence issue raised above.","section":"Definition 2.11"},{"comment":"The empirical section is informative, but the text could briefly note that the observed attack does not by itself constitute a proof of the theorem, and that the simulations of Robust use c=1 while the theoretical guarantees require a c that depends on the failure probability δ.","section":"Section 6"}],"recommendation":"major_revision","confidential_remarks":"The robust protocol and its analysis appear sound and constitute a strong contribution: the symmetry argument is clean, the per-round tail bounds are standard, and the renewal-process reduction is plausible. The attack on HYZ12, however, is not proved as written. The key issue is that boundary updates change the published estimate without a Report from the active site, breaking the synchronization between the attack's round-robin pointer and the set of genuinely reporting sites. This is a load-bearing defect in the negative result, which is one of the two headline contributions. I would ask the authors to either repair the attack proof (e.g., by designing the attack to detect or ignore boundary-induced estimate changes, or by showing such changes are rare enough not to affect the argument) or to remove/reformulate the negative claim. If the negative result cannot be fixed, the paper could still be publishable as a positive result about the robust protocol, but that would be a substantial reframing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Cole—quick take. The paper splits into two halves. The second half—the robust protocol—is the real contribution and looks good. The protocol in Algorithm 4 is genuinely simple, matches the optimal O(√k/ε log N) communication bound in the white-box model, and improves on XZH23's polylog(k) overhead. The symmetry argument for robustness is clean, and the accuracy analysis (especially the per-round to per-event-index conversion, Lemma 4.5) is a nice piece of work that goes beyond a standard union bound. Sections 3–5 are carefully done; I did not find a load-bearing flaw there. The simulations are a reasonable sanity check, though not essential.\n\nThe first half—the adaptive attack on HYZ12—is where I part ways with the current write-up. The paper's Theorem 2.1 says HYZ12 fails under an adaptive attack that watches the server's estimate and round-robins to the next site whenever the estimate changes. The problem is that the estimate changes for two reasons: site reports and boundary adjustments. On a BoundaryReached event the server updates the transmission probability, subtracts zero-inflated geometric noise from every stored counter, and republishes \\hat n. Algorithm 3 only sees \\hat n, so it cannot distinguish a genuine report from a boundary adjustment. Lemma 2.9's opening line—'Each update to the published estimate is caused by a Report message from the site currently injected'—is false. That invalidates the R ≥ k/8 claim and Corollary 2.10's k/2, which Lemma 2.13 leans on for the bias. Also, Observation 2.12's claim that a reporting transcript uniquely determines the attack's behavior is circular: the attack's events depend on \\hat n, which depends on server-side randomness, so fixing only site-side randomness does not pin down the event stream.\n\nThis matters because Theorem 2.1 is the reason the open question is resolved. The empirical plots in Section 6 suggest the vulnerability is real, and I suspect the theorem is true, but the written proof doesn't establish it yet. The fix may be straightforward—maybe argue that boundary adjustments also create the same bias, or bound the number of boundary-induced changes and handle them separately—but as written the proof has a hole.\n\nBottom line: send it to a serious referee. The robust protocol alone is worth the review, and the attack question is important enough that a careful repair of Section 2 should be the main request. For me, this is a 'major revision' rather than a reject.","headline":"The robust protocol is a genuine advance, but Theorem 2.1 (the HYZ12 attack) rests on a proof gap that needs fixing before the negative result is credible.","tokens_in":25617,"tokens_out":3237,"would_cite":true,"duration_ms":28207,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"A simple variant of the classic randomized distributed-counting protocol is robust against white-box adaptive adversaries and achieves optimal communication complexity, while the original protocol is breakable by an explicit adaptive…","keywords":["distributed counting","adaptive adversary","white-box robustness","communication complexity","randomized algorithms","oblivious vs adaptive setting","geometric random variables","distributed functional monitoring"],"falsifier":"Run the round-robin attack of Algorithm 3 against both protocols with $k = 256$, $\\varepsilon = 0.125$, and $N = 10^5$, as the paper's simulations do. The attack theorem predicts HYZ12's relative error to climb toward $\\sqrt{k}\\,\\varepsilon \\approx 2$; repeated runs that keep the estimate within $[1-\\varepsilon, 1+\\varepsilon]\\cdot n$ throughout would refute the bias-accumulation analysis. The robustness theorem predicts the new protocol's relative error stays below $\\varepsilon = 0.125$ with high probability under the same attack; a median relative error that clearly exceeds $\\varepsilon$ at any point in the second half of the run, across independent seeds, would refute the robustness guarantee.","tokens_in":24637,"feed_emoji":"📊","tokens_out":15099,"duration_ms":119973,"temperature":0.7,"pith_summary":"This paper settles an open question about the distributed counting problem, in which a server must continuously estimate the total number of events occurring across $k$ sites while keeping communication small. The authors first show that the classic randomized protocol of [HYZ12], previously analyzed only against inputs fixed in advance, is not robust: an adaptive attack that feeds events to one site until the published estimate moves, then switches to the next site, drives the estimate to a positive bias of order $\\sqrt{k}\\,\\varepsilon n$, far above the target accuracy $\\varepsilon n$. They then present a slightly modified protocol that is robust even against a white-box adversary who sees the protocol's internal state, while achieving the optimal communication bound $O(\\sqrt{k}/\\varepsilon \\cdot \\log N)$. The resolution matters because it shows that, in this setting, robustness against adaptive inputs costs no extra communication and needs no external machinery such as differential privacy.","feed_headline":"Tiny twist makes distributed counting robust at optimal cost","feed_subtitle":"Classic counter breaks under adaptive attack; a symmetric rewrite keeps worst-case accuracy at the same asymptotic cost.","key_machinery":"The load-bearing object of the positive result is the round structure with exact-count synchronization: at the start of each round the server gathers the exact total $\\bar{n}$, sets a transmission probability $p \\approx \\sqrt{k}/(\\varepsilon \\bar{n})$, and counts sample messages until exactly $k$ have arrived, so each round's event count is a sum of $k$ independent geometric variables with parameter $p$ and no estimation error carries across a round boundary. The robustness proof then rests on site-symmetry — server state is a function only of aggregate counts and message counts — which reduces every white-box adaptive adversary to an oblivious stream confined to one site. Inside a round, accuracy comes from a maximal partial-sum deviation bound for geometric variables (Claim 4.4), and a renewal-process analysis (Lemma 4.5) shows that for any fixed event index only $O(1)$ relevant rounds need to be considered, converting per-round accuracy into per-event accuracy without paying for a union bound over all rounds. On the attack side, the central object is the zero-inflated geometric variable $Z_{q,p} = B \\cdot G$ with $B \\sim \\mathrm{Bernoulli}(1 - q/p)$ and $G \\sim \\mathrm{Geom}(q)$; its telescoping identity (Lemma 2.5) shows that the server's random round-boundary corrections preserve the attacker's bias exactly in distribution, and a Bernstein-type tail bound for sums of such variables (Lemma 2.6) controls the fluctuations.","core_discovery":"The paper makes two claims. First, the HYZ12 protocol loses accuracy under adaptively chosen inputs: for every event count $n \\ge c_3\\sqrt{k}/\\varepsilon$, there is an attack under which $\\Pr[\\hat{n} - n > c_1\\sqrt{k}\\,\\varepsilon n] \\ge 1 - e^{-c_2 k}$. The attack exploits the protocol's per-site estimator, which is the last reported local count plus an expectation correction of roughly $1/p - 1$: the adversary injects events into one site until the published estimate changes, which reveals that the site has just reported, and then abandons that site, freezing a positive bias into its estimate; randomized adjustments at round boundaries preserve the expected bias, so it accumulates across sites. Second, a protocol that starts each round by collecting exact counts from every site and then counts only the number $B$ of sample messages — each site sends a ``1'' message with probability $p = \\min\\{1, c\\sqrt{k}/(\\varepsilon \\bar{n})\\}$ per event, the server estimates $\\bar{n} + B/p$, and the round ends when $B$ reaches exactly $k$ — is robust in the white-box model with optimal communication. Robustness follows from site-symmetry: the server's state and outputs depend only on the total event count and the number of sample messages, never on which site sent them, so every adaptive placement of events is equivalent to an oblivious stream at a single site.","pith_inferences":["The site-symmetry argument is a general recipe: for distributed functional monitoring problems, any protocol whose server state depends only on aggregate counts and counts of protocol messages inherits robustness from its oblivious analysis, which may remove the need for privacy-based robustification in other tracking tasks.","The renewal-process conversion is a reusable tool: any round-based protocol whose round lengths are sums of light-tailed random variables can obtain per-time accuracy from per-round accuracy while considering only $O(1)$ relevant rounds, instead of union-bounding over all rounds.","The attack's effectiveness suggests a broader pattern — publishing an estimate built from per-site counters leaks exactly the timing information an adaptive adversary needs. A natural testable extension is to measure how much output perturbation (noise or coarsening) is required to break the round-robin attack against arbitrary per-site-counting protocols."],"forward_implications":["The HYZ12 protocol must not be used as-is when event streams can depend on published estimates; under the paper's attack its error scales as $\\sqrt{k}\\,\\varepsilon n$, a factor $\\sqrt{k}$ above the target.","Optimal communication and robustness are compatible in this problem: the new protocol matches the $\\Omega(\\sqrt{k}/\\varepsilon \\cdot \\log N)$ lower-bound regime while remaining correct against white-box adaptive adversaries, making it the first to do so.","The new protocol avoids the differential-privacy layer that the previous robust protocol needed, and it removes the $\\mathrm{polylog}(k)$ communication factor, while defending against a strictly stronger (white-box) attack model.","On non-adaptive streams the new protocol performs essentially like the classic one, so the robustness guarantee comes at no practical asymptotic cost; the paper's simulations show comparable communication and accuracy on uniform inputs."],"supporting_citations":[{"why":"The oblivious randomized two-way protocol that the paper attacks and then minimally modifies; supplies the baseline estimator structure and the round-based probability scheme.","marker":"[HYZ12]"},{"why":"The deterministic doubling protocol that HYZ12 uses as its round-triggering background and that motivates the new protocol's round structure.","marker":"[KCR06]"},{"why":"The previous robust protocol whose polylog(k) blow-up, differential-privacy layer, and black-box-only guarantee frame the open question and the comparison.","marker":"[XZH23]"},{"why":"Provides the concentration inequality (maximal partial-sum deviation for geometric variables) that carries the per-round accuracy bound.","marker":"[BLM13]"},{"why":"Provides the Chernoff lower-tail bound used to show that many distinct sites report during the attack window.","marker":"[MU17]"},{"why":"The differential-privacy robustification framework the new protocol deliberately avoids; its communication cost and black-box limitation define the gap being closed.","marker":"[HKM+20]"},{"why":"Establishes the deterministic lower bound that the randomized improvements are measured against.","marker":"[YZ09]"}],"fun_headline_variants":["Robust counting: simple protocol matches optimal bound","Adaptive attacks break classic counter; simple rewrite fixes it","Symmetric trick makes distributed counting robust at optimal cost","Counting across sites: simple protocol resists adaptive attacks","Distributed counting gets a simple, optimal, attack-proof protocol"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The attack analysis assumes that every change the attacker observes in the published estimate is caused by a genuine Report message from the site it is currently feeding, so that the round-robin pointer stays synchronized with the reporting sites. If a round-boundary transition (a BoundaryReached alert or the server's random counter adjustment) moves the estimate without such a report, the claimed synchronization — and with it the bias-accumulation argument of Lemma 2.13 — no longer follows from the stated definitions.","fun_headline_variants_meta":{"raw":{"variants":["Robust counting: simple protocol matches optimal bound","Adaptive attacks break classic counter; simple rewrite fixes it","Symmetric trick makes distributed counting robust at optimal cost","Counting across sites: simple protocol resists adaptive attacks","Distributed counting gets a simple, optimal, attack-proof protocol"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00023,"raw_usage":{"total_tokens":1577,"prompt_tokens":1134,"completion_tokens":443,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":750,"completion_tokens_details":{"reasoning_tokens":365}},"tokens_in":750,"tokens_out":443,"duration_ms":4514,"temperature":1.0,"reasoning_tokens":365,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:21:25.194566+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the round-robin attack of Algorithm 3 against both protocols with $k = 256$, $\\varepsilon = 0.125$, and $N = 10^5$, as the paper's simulations do. The attack theorem predicts HYZ12's relative error to climb toward $\\sqrt{k}\\,\\varepsilon \\approx 2$; repeated runs that keep the estimate within $[1-\\varepsilon, 1+\\varepsilon]\\cdot n$ throughout would refute the bias-accumulation analysis. The robustness theorem predicts the new protocol's relative error stays below $\\varepsilon = 0.125$ with high probability under the same attack; a median relative error that clearly exceeds $\\varepsilon$ at any point in the second half of the run, across independent seeds, would refute the robustness guarantee.","supporting_citations":[],"review_version":1}