{"id":"05e2c286-d977-4e32-a7d1-94b3f1fd13ff","arxiv_id":"2507.08348","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Content-oblivious leader election is possible in all 2-edge-connected networks (with a known size bound) and on unoriented rings (with no bound), resolving two open conjectures.","lead":"Two new algorithms solve leader election when messages carry no information and only pulses arrive: one for any 2-edge-connected network given a known node-count upper bound, and one for unoriented rings with no size bound. Both refute earlier conjectures that a preselected leader or orientation is required, and the ring result closes the gap between noisy and noiseless communication.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's ACCEPT verdict is justified. I re-read the full proof structure for both theorems. Theorem 1's correctness rests on the synchronization lemmas (12–15) and the induction over the directed DFS sequence with the chain-and-anchor property (Lemma 22). I checked the delicate point: Lemma 22 requires no DFS pulse on the chain P_{v,w}, and the argument that the in-flight edge e_{i+1} cannot lie on this chain is sound because e_{i+1} is oriented from the visited side to the unvisited side, while P_{v,w} enters the visited region. Theorem 2's correctness rests on Proposition 26 and the no-early-termination lemmas (35–38). The pulse counts in Lemma 33 are consistent: after rebalancing, the node has sent and received exactly ID2+2 pulses on each port, and Lemma 28 prevents a neighbor from being more than one iteration ahead, so a 3-pulse imbalance cannot arise accidentally. The proof of the weak local-min variant of Lemma 30 is abbreviated, but the global-min induction used for Corollary 37 is not endangered: the minimum-ID active node completes its shorter competing phase before larger-ID nodes can complete theirs, because the synchronization bound limits how far ahead any neighbor can run. Thus the central claims are well supported, and no machine-checked proof is provided but none is required for acceptance at this confidence level. I found no concrete counterexample or internal inconsistency.","tokens_in":29870,"tokens_out":63680,"duration_ms":712865,"concrete_test":"Run an exhaustive state-space search of Algorithm 3 on rings of size 2, 3, and 4 with all port labelings and all admissible single-pulse delivery orders up to a horizon covering the maximum-ID node's termination, verifying that the only Leader output is the maximum-ID node and that the system is quiescent at termination.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorems survive scrutiny. The most delicate step is the transparency invariant behind Proposition 26: after failing solitude, a node must be indistinguishable from a deleted node. The proof closes the off-by-one risks: Lemma 33 fixes sent/received counts at exactly ID2+2 on each port after rebalancing, and Lemma 28's local synchronization bound prevents a neighbor from being more than one iteration ahead, so a competing neighbor cannot produce a spurious 3-pulse imbalance (Lemma 35) before the maximum-ID node's termination group. For Theorem 1, the chain-and-anchor argument in Lemma 22 is valid because the directed orientation of G prevents the single in-flight DFS edge from lying on the chain P_{v,w} in the wrong direction. I do not find a load-bearing gap; the weaker local-min variant of Lemma 30 is sketched rather than fully expanded, but Corollary 37's induction only needs the global-min application, and the synchronization bound keeps the global minimum from being leapfrogged by larger-ID nodes.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies content-oblivious leader election in asynchronous fully-defective networks, where communication is reduced to pulses. It proves two main results. Theorem 1 gives a quiescently terminating leader election algorithm for every 2-edge-connected network, assuming a known upper bound N on the number of nodes, with message complexity O(m * N * IDmin); combined with the simulation of Censor-Hillel, Cohen, Gelles, and Sela, this removes the preselected-leader assumption from that simulation. Theorem 2 gives a uniform, quiescently terminating leader election algorithm for unoriented rings with message complexity O(n * IDmax), requiring neither orientation nor knowledge of N. The proofs are organized around a counting phase with near-synchronization, a DFS notification phase justified by a chain-and-anchor invariant, and, for rings, an inductive node-deletion argument based on transparency of relaying nodes.","tokens_in":29958,"tokens_out":21479,"duration_ms":249277,"significance":"If the results stand, they close two open problems in the content-oblivious model: the conjecture that a preselected leader is necessary for nontrivial computation in fully-defective networks is refuted under a known size bound, and the conjecture that quiescently terminating leader election is impossible on unoriented rings is refuted. The paper is careful and unusually detailed: the main invariants (small counter property, chain-and-anchor, node-deletion indistinguishability, no-early-termination) are stated precisely and the induction skeletons are explicit. The composition argument with prior simulation results is correctly aligned with the quiescent-termination and leader-last requirements. I checked the central proof skeleton and found no load-bearing gap; the delicate transparency argument behind Proposition 26 is closed by the exact count in Lemma 33 and the synchronization bound in Lemma 28. The paper does not provide machine-checked proofs or code, but the hand proofs are sufficiently detailed for a theory venue.","major_comments":[],"minor_comments":[{"comment":"The weaker local-minimum variant of Lemma 30 is stated only as a sketch ('it is still possible to adapt the proof'), and the formal induction in Corollary 37 iterates over global minima, so this does not affect the main theorem; nevertheless, the remark should either be proved or explicitly marked as non-essential, since as written it leaves the impression that a case distinction is being deferred.","section":"Section 5.1, Lemma 30"},{"comment":"In the proof of Lemma 14, the quantity x = min_{u in V\\S} Count(u) is infinite when S = V, and the instruction 'by choosing x = ...' is only meaningful for nonempty V\\S; the edge case is handled separately in Lemma 15, but the lemma statement or proof should state this convention explicitly.","section":"Section 4.1, Lemma 14"},{"comment":"The event SendExplore_j(v) is triggered before the 'wait until rho_j >= LeaderID + 1' on line 7, whereas the prose describes it as the moment a node 'starts sending' an explore-notification; this conflation of intention and actual first pulse should be clarified, because the timing of t^Send is used in the induction hypothesis H1.","section":"Section 4.2, Algorithm 2 and event definitions"},{"comment":"Observation 27 says a node 'has received i pulses' from each neighbor after i iterations, but in the asynchronous buffered model a node may have received additional pulses that it has not yet consumed; the statement should say 'has consumed i pulses in RcvPulse actions,' which is what Lemma 28 actually uses.","section":"Section 5.1, Observation 27"},{"comment":"The complexity calculation says vmax sends 4*IDmax + 3 pulses and attributes the factor 4 to doubling the identifiers, but this is only correct if IDmax denotes the original, predoubling identifier; the text should state explicitly whether IDmax in this calculation is the original or the doubled value.","section":"Section 5, proof of Theorem 2"}],"recommendation":"accept","confidential_remarks":"No confidential concerns beyond the minor editorial points listed above. The results are significant, the proofs are detailed, and the paper is suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a strong paper, and my verdict agrees with the reader's ACCEPT at moderate confidence. It gives the first quiescently terminating content-oblivious leader election for general 2-edge-connected networks (with a known size bound N) and for unoriented rings, and the ring result is uniform and matches the prior O(n·IDmax) bound. When combined with CCG+23, the first result removes the preselected-leader assumption under non-uniformity; the second refutes the FGG+24 conjecture that orientation is needed for termination. The algorithms are genuinely new, not modifications of the oriented-ring trick: the general case uses an Awerbuch-style synchronized counter plus a DFS notification phase, and the ring case uses a solitude check followed by transparent relaying, with the maximum-ID node as the last one standing.\n\nWhat the paper does well: the proof structure is explicit, with complete pseudocode. I checked the two places that looked most likely to break. The chain-and-anchor argument in Lemma 22 survives because the DFS orientation prevents the single in-flight edge from appearing on the chain. The transparency argument behind Proposition 26 is delicate, but Lemma 33 fixes the sent/received counts at ID2+2 after rebalancing, and Lemma 28's synchronization bound prevents a neighbor from creating a spurious three-pulse imbalance before the max-ID node's termination group. The off-by-one risks are addressed.\n\nSoft spots, in proportion: Theorem 1's need for a known N is a real limitation, and the paper says so honestly—the general conjecture is refuted only in the non-uniform setting, and the uniform case remains open. The ring proof has a sketched local-min variant of Lemma 30; it is not fully expanded, and a referee should ask for that to be written out. It does not seem load-bearing, because the induction in Corollary 37 can apply the global-min version to successively reduced rings. The proofs are long and not machine-checked, so a human referee will have to invest real time, but I did not find a gap. Citations are appropriate, including the self-citations; nothing looks inflated.\n\nWho should read it: anyone working on content-oblivious or beeping-style computation, and the distributed computing community generally. It deserves a serious referee, not a desk reject. I would send it out and ask for expansion of the local-min case plus a careful check of the ring induction.","headline":"Strong paper that closes the content-oblivious leader election question on rings and, under a modest size bound, on general 2-edge-connected graphs; the proofs are long but the delicate points hold up.","tokens_in":30528,"tokens_out":3540,"would_cite":true,"duration_ms":38794,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two algorithms show that leaders can be elected by pulse counting alone in fully defective networks, refuting the conjecture that a preselected leader is always required.","keywords":["content-oblivious computation","fully-defective networks","leader election","quiescent termination","2-edge-connected graphs","unoriented rings","pulse communication","asynchronous distributed algorithms"],"falsifier":"Run the ring algorithm on a three-node unoriented ring with adversarial pulse scheduling and identifiers spaced by two; if any non-maximum node ever terminates as Leader, or if any relaying node's Diff counter reaches 3 before the maximum-ID node sends its termination pulse, Theorem 2 fails. Equivalently, for the general algorithm, exhibit a 2-edge-connected graph and a delivery order in which some node's counter reaches $\\mathsf{ID}(v)$ before the DFS notification arrives, since the chain-and-anchor invariant guarantees $\\mathsf{Count}(v) \\leq \\mathsf{ID}(r) + N - 1 < \\mathsf{ID}(v)$ for every non-leader at all times.","tokens_in":29636,"feed_emoji":"📡","tokens_out":9261,"duration_ms":89336,"temperature":0.7,"pith_summary":"In the fully-defective communication model, every message may be arbitrarily corrupted, so nodes are left with only the timing of arrivals—pulses—as information. Earlier work proved that any noiseless algorithm can be simulated in such a network, but only if a leader is chosen in advance, and it conjectured that this preselected leader is unavoidable. This paper refutes that conjecture: it presents a pulse-only leader election algorithm that quiescently terminates in any 2-edge-connected network, given only an upper bound on the number of nodes, and a second algorithm that needs no such bound on unoriented rings. Because the elected leader is the last node to stop, the earlier simulation can be composed with the election, so any noiseless algorithm becomes simulable without a preselected leader. The ring result also matches the best known message bound, showing that orientation of the ring is not needed after all.","feed_headline":"Pulse counting elects a leader in fully defective networks","feed_subtitle":"A standing conjecture said preselected authority was unavoidable; this shows it is not.","key_machinery":"The engine of Theorem 1 is a near-synchronized counter: each node broadcasts a pulse after each increment and its counter equals the minimum number of pulses received on any port, so neighboring counters differ by at most one. Identifiers are first multiplied by $N$ so that only the smallest-ID node can ever reach its own counter value. The leader then announces itself by a DFS notification that sends a fixed surplus of $\\mathsf{ID}(r) + N + 2$ pulses along each edge; the surplus defeats the counter's bounds and forces each neighbor to detect an anomaly. The proof rests on a chain-and-anchor argument along shortest paths in the strongly connected orientation of the graph built from a DFS tree, which keeps every unvisited node's counter below its own identifier until the announcement arrives. For Theorem 2 the mechanism is a solitude check followed by transparency: a node that fails its check sends two balancing pulses and then relays every pulse to the opposite port, behaving as an asynchronous link; the induction deletes such nodes one at a time until only the maximum-ID node remains, whose termination pulse travels around the ring and is recognized by a three-pulse imbalance.","core_discovery":"The paper's central claim is that quiescently terminating content-oblivious leader election is possible without a preselected leader. Theorem 1 constructs an algorithm that works in every 2-edge-connected network when the nodes share an upper bound $N$ on the network size, electing the node with the smallest identifier using $O(m \\cdot N \\cdot \\mathsf{ID}_{\\min})$ pulses, where $m$ is the number of edges and $\\mathsf{ID}_{\\min}$ the smallest identifier; the leader is the last node to terminate, which is exactly the property that lets a following simulation algorithm run safely. Theorem 2 removes the need for $N$ on unoriented rings: a uniform algorithm elects the largest identifier with $O(n \\cdot \\mathsf{ID}_{\\max})$ pulses, matching the previous bound for oriented rings and refuting the claim that orientation is required for termination detection. Together the theorems imply that fully-defective and noiseless communication are computationally equivalent on rings, and equivalent whenever a size bound is known in general 2-edge-connected topologies.","pith_inferences":["The surplus-pulse notification suggests a general recipe: in a 2-edge-connected network, a node can force recognition of any event by sending more pulses than any untouched counter can plausibly accumulate; the same trick may yield other content-oblivious primitives, such as broadcast or renaming, without a leader.","The ring algorithm's transparency argument hints that uniform election might extend to general 2-edge-connected graphs: if a non-leader can always be made indistinguishable from a deleted node while the maximum-ID node keeps competing, the inductive deletion may not need the size bound $N$ at all—a question the paper leaves open.","The paper's own remark that a node cannot notify all neighbors at once, because that would break the chain-and-anchor guarantee, suggests that any speedup of the DFS notification must find a different anchor structure rather than simply flooding.","The Diff-threshold idea used for the ring's termination signal could serve as a generic content-oblivious 'end of computation' marker when composing multiple tasks, since every non-leader terminates only after relaying the leader's third pulse."],"forward_implications":["Whenever an upper bound on the number of nodes is known, every algorithm designed for a noiseless 2-edge-connected network can be executed in a fully-defective network with no preselected leader: run the election, then run the known simulation from the elected leader.","On unoriented rings, no bound on the network size and no consistent orientation are needed; quiescent termination is achieved with $O(n \\cdot \\mathsf{ID}_{\\max})$ messages, the same bound previously attainable only with orientation.","The standing conjectures—that a preselected leader is necessary for any non-trivial content-oblivious computation, and that terminating election is impossible in unoriented rings—are both false.","The dependency on identifiers improves from the maximum identifier to the minimum identifier in general topologies, at the price of the size bound $N$.","Since the leader terminates last, the election composes cleanly with subsequent algorithms: nodes can tell which pulses belong to which phase."],"supporting_citations":[{"why":"Defines the fully-defective model, proves the two-party impossibility, supplies the simulation from a preselected leader that Theorem 1 composes with, and states the conjecture being refuted.","marker":"[CCG+23]"},{"why":"Provides the oriented-ring quiescently terminating election with $O(n \\cdot \\mathsf{ID}_{\\max})$ that Theorem 2 must match, the stabilizing unoriented-ring result, and the conjecture that terminating election is impossible in unoriented rings.","marker":"[FGG+24]"},{"why":"Supplies the synchronizer that keeps the pulse counters of neighboring nodes within one of each other, the basis of both the counting phase and the chain-and-anchor bound.","marker":"[Awe85]"}],"fun_headline_variants":["Leader election without a preselected leader is possible now","Conjecture false: no preset leader required for content-oblivious tasks","Defective networks compute leader election with no prior setup","Rings: fully defective equals noiseless for leader election"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The general-topology result collapses if the shared upper bound $N$ on the number of nodes is wrong, since identifiers are spaced $N$ apart so that only the smallest-ID node can reach its own counter value; the ring result instead collapses if a node that fails its solitude check cannot be made perfectly transparent, because its neighbors must never detect it through an off-by-one pulse imbalance.","fun_headline_variants_meta":{"raw":{"variants":["Leader election without a preselected leader is possible now","Conjecture false: no preset leader required for content-oblivious tasks","Defective networks compute leader election with no prior setup","Rings: fully defective equals noiseless for leader election"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000434,"raw_usage":{"total_tokens":2307,"prompt_tokens":1139,"completion_tokens":1168,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":755,"completion_tokens_details":{"reasoning_tokens":1098}},"tokens_in":755,"tokens_out":1168,"duration_ms":10941,"temperature":1.0,"reasoning_tokens":1098,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:23:00.365157+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the ring algorithm on a three-node unoriented ring with adversarial pulse scheduling and identifiers spaced by two; if any non-maximum node ever terminates as Leader, or if any relaying node's Diff counter reaches 3 before the maximum-ID node sends its termination pulse, Theorem 2 fails. Equivalently, for the general algorithm, exhibit a 2-edge-connected graph and a delivery order in which some node's counter reaches $\\mathsf{ID}(v)$ before the DFS notification arrives, since the chain-and-anchor invariant guarantees $\\mathsf{Count}(v) \\leq \\mathsf{ID}(r) + N - 1 < \\mathsf{ID}(v)$ for every non-leader at all times.","supporting_citations":[],"review_version":1}