{"id":"0967726d-3637-4cc7-b709-b18405487285","arxiv_id":"1908.01458","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A protocol-agnostic design that runs multiple parallel consensus instances with distinct primaries, deterministic hash-based ordering, and soft-failure handling to reduce leader load and malicious impact.","lead":"This paper proposes a way to run several copies of a leader-based Byzantine fault tolerance consensus protocol side by side, so no single leader becomes a bottleneck or a single point of failure. If it works, permissioned blockchain systems could get higher throughput and better resilience to malicious leaders without rewriting their consensus core.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.4 is asserted without proof and its soft-failure rule assumes a locally detected lag can be turned into a unanimous F decision; the black-box model gives no such primitive, so the wait-free upper bound is unsupported.","rationale":"The reader's weakest assumption correctly identifies the soft-failure coordination problem. My reading of the full text finds no proof of Theorem 4.4, and the proof of Theorem 4.6 depends directly on it. The core issue is that Definition 4.3 assumes a local soft-failure detection can be escalated into a unanimous F through the underlying protocol's fault-detection infrastructure, but Definition 3.1's black-box model does not provide this escalation. Real primary-backup protocols such as PBFT can preserve a prepared value across a view change, meaning the round may decide S(CR) even when one replica locally believes the instance is lagging. This is a genuine gap in the argument rather than a mere disagreement with external consensus. The paper also provides no experimental validation, but the missing proof of the main theorem is the more load-bearing deficiency. I therefore agree with the reader's conditional verdict and see no reason to move it: the design is plausible, but the central wait-free theorem requires a rigorous proof or a more precise protocol interface.","tokens_in":14139,"tokens_out":7154,"duration_ms":79440,"concrete_test":"Formalize the soft-failure rule on top of a concrete primary-backup protocol (e.g., PBFT with n=4, f=1) in a model checker such as TLA+ or ByMC. Configure two parallel instances, and make instance I2's primary non-faulty but slow, so that at one non-faulty replica I2 is still in round ρ while I1 is in round ρ+σ, while at another non-faulty replica I2 has a prepared certificate for round ρ. Check whether all non-faulty replicas decide the same value for round ρ and whether the acceptance-to-execution delay is bounded by σ+ε in every reachable run. If a reachable run yields S(CR) at one replica and F at another, Theorem 4.4 is false; if all runs are non-divergent and bounded, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 4.4: instances are wait-free and the delay from acceptance to execution is upper-bounded. This theorem has no proof, and Theorem 4.6 explicitly relies on it. The hidden assumption is in Definition 4.3: 'Each replica locally detects the soft failure of its instance Ii ... and uses the fault detection infrastructure of the underlying consensus protocol to work towards ending the ongoing consensus round with a decision F.' The black-box consensus model (Definition 3.1) only guarantees that a round ends with F when all non-faulty replicas observe a failure; it does not provide a primitive by which one replica's local observation can force a unanimous F. In PBFT, for example, a backup that times out initiates a view change, but if another non-faulty replica already has a prepared certificate for the round, the decided value is S(CR), not F. Thus the soft-failure rule can put non-faulty replicas in inconsistent states: one has accepted the client request for round ρ, while another treats the round as failed and jumps to ρ+ε. The paper does not prove this cannot happen. The promised upper bound on execution delay is also never derived from explicit synchrony assumptions, despite relying on timing parameters σ and ε. Without a proof of Theorem 4.4 or a precise interface for the underlying fault-detection primitive, the wait-free claim is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a protocol-agnostic paradigm for parallelizing primary-backup Byzantine fault-tolerant consensus protocols. The approach runs m instances of an underlying consensus protocol in parallel, with distinct primaries per instance. Section 3 develops a step-wise design: a deterministic round-execution protocol that orders accepted client requests via a hash-derived permutation, and a unified primary-replacement protocol that keeps the set of primaries distinct across instances. Section 4 introduces a wait-free redesign. The key idea is that instances should not wait for one another: successful instances proceed to future rounds, while lagging instances are declared to suffer a \"soft failure\" (Definition 4.3) and skip the next ε rounds. The paper claims in Theorem 4.4 that instances are wait-free and that the delay between accepting a client request and executing it is upper-bounded, and in Theorem 4.6 that the paradigm yields a high-performance parallelized wait-free consensus protocol with balanced load and minimized impact of faulty replicas. The proof of Theorem 4.6 is given, but it relies on Theorem 4.4, for which no proof is supplied.","tokens_in":14487,"tokens_out":2761,"duration_ms":29460,"significance":"If established, the result would be practically significant: it offers a black-box way to reduce primary load and mitigate the throughput impact of faulty or slow primaries in permissioned blockchain systems. The paper has real strengths: the black-box round model (Definition 3.1) is a clean abstraction; the deterministic ordering protocol (Section 3.1) is coherent; and the unified primary-replacement protocol comes with a stated invariant and a proof (Proposition 3.7). The paper also ships a formal-looking theorem structure, and the wait-free goal is clearly defined. However, the central wait-free claim is not proven, and the soft-failure mechanism relies on an unstated assumption about the underlying protocol's fault-detection interface. Because the headline contribution depends on these points, the significance is conditional until the missing proof and assumptions are supplied.","major_comments":[{"comment":"Theorem 4.4 is the load-bearing claim of the paper, but it is asserted without proof. The theorem states that instances are wait-free and that the delay between accepting a client request and executing it is upper-bounded. No argument is given for either conjunct, and the bound is not derived from any explicit timing model. The text informally relates σ to network latency and timeouts, and ε to σ and primary-replacement time, but Definition 4.3 does not define a formal round structure or synchrony assumptions under which such a bound can be proven. The manuscript needs either a full proof of Theorem 4.4 or a precise statement of the timing assumptions and a derivation of the bound.","section":"Section 4.1, Theorem 4.4"},{"comment":"The soft-failure rule assumes a capability that the black-box consensus model of Definition 3.1 does not provide. Definition 3.1 guarantees that a round fails with decision F only when all non-faulty replicas observe the failure; it gives no primitive by which a single replica that locally detects a lag can force the round to end with a unanimous F. In the soft-failure description, each replica locally detects the soft failure and \"uses the fault detection infrastructure of the underlying consensus protocol to work towards ending the ongoing consensus round with a decision F.\" This leaves open the possibility that one non-faulty replica treats round ρ as failed and moves to ρ+ε while another non-faulty replica has already accepted S(CR) for round ρ. Such a split would violate the non-divergence invariant on which Proposition 3.7 and the overall correctness argument depend. The paper must either specify a fault-detection interface that guarantees a coordinated unanimous F decision, or change the soft-failure mechanism to one that provably maintains non-divergence.","section":"Section 4.1, Definition 4.3"},{"comment":"The proof of Theorem 4.6 explicitly invokes Theorem 4.4 for the wait-free property and for the claim that the impact of faulty replicas is minimized. Since Theorem 4.4 is unsupported, the main conclusions of Theorem 4.6 are also unsupported. Additionally, the proof's termination argument is too brief: it says termination follows directly from termination of the underlying consensus protocol, but for the client-side guarantee (every client eventually sees its requests executed) one must also argue that a client assigned to an instance with a faulty primary eventually reaches a non-faulty primary or is reassigned, and that soft-failure skipping does not indefinitely defer the client's request. These points should be made explicit.","section":"Section 4.3, Theorem 4.6"}],"minor_comments":[{"comment":"The title contains a line-break artifact \"paralle lization\" in the supplied text; this should be corrected to \"parallelization.\"","section":"Abstract and title"},{"comment":"The pseudocode calls fS(Hash(S) mod |S(Dρ)|!) but the domain of fS is {0, ..., |S|!-1}. Since |S| = |S(Dρ)|, the modulo expression is in range, but the notation is easy to misread; a short clarifying sentence would help.","section":"Section 3.1, Figure 3"},{"comment":"The instance-change mechanism says a client is reassigned \"in round ρ + 2σ,\" but σ is a time duration while ρ is a round number. The manuscript uses σ, ε, and ρ in the same expressions without formally relating rounds to time; this makes the description hard to interpret and should be clarified.","section":"Section 4.2, client instance-change"},{"comment":"The paragraph says that \"natural fluctuations in the performance of an instance can cause an unjust replacement of its primary\" and then describes a recovery mechanism, but no invariant or proof is given for the combined soft-failure-plus-replacement behavior. This is related to the major concern about coordinated failure decisions and should be addressed in the revision.","section":"Section 4.1, paragraph after Definition 4.3"}],"recommendation":"major_revision","confidential_remarks":"The step-wise construction in Section 3 is coherent and the primary-replacement invariant is proven, so the paper has a solid core. The problem is that the paper's main advertised contribution, the wait-free extension in Section 4, is not proven and appears to rely on an extra capability (locally triggered unanimous failure) that the stated black-box model does not include. This is fixable within the manuscript's scope by adding a formal timing model, specifying the fault-detection interface, and proving Theorem 4.4, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before you read. The step-wise parallelization — m distinct-primary instances, hash-based deterministic ordering across rounds, unified primary replacement — is a genuine, well-presented protocol-agnostic contribution. The wait-free part that the title and the performance claims are built on is not. Theorem 4.4, 'instances are wait-free,' is stated without proof, and the soft-failure mechanism in Definition 4.3 assumes a primitive the black-box model does not provide.\n\nWhat is new and good: running m consensus instances with distinct primaries and a deterministic hash-based permutation of accepted requests per round is a clean way to cut primary load and blunt malicious-primary influence without touching the underlying protocol. The unified primary replacement protocol (Section 3.2.2) is coherent; the invariant proof in Proposition 3.7 goes through if the underlying consensus gives all non-faulty replicas the same set F(Dρ) each round. The client-to-instance assignment and the instance-change request for non-replacing environments are sensible. The formal bits that are actually proved look correct to me.\n\nThe soft spots are real and load-bearing. Theorem 4.4 has no proof; it is asserted after Definition 4.3. The definition says each replica 'locally detects' a soft failure and then 'uses the fault detection infrastructure' to push the round to a decision F. But the black-box model (Definition 3.1) only guarantees F when all non-faulty replicas see failure. Nothing in the model lets one non-faulty replica force a unanimous F. In PBFT, a backup that times out can trigger a view change, but if another non-faulty replica has a prepared certificate for that round, the round decides S(CR), not F. So the soft-failure rule can leave non-faulty replicas inconsistent: one has accepted a client request for round ρ, another treats the round as failed and jumps to ρ+ε. That breaks the non-divergence invariant used in Proposition 3.7 and invalidates the wait-free claim. The promised upper bound on execution delay also depends on σ and ε, but no explicit synchrony assumptions are stated. There are no experiments, so 'high-performance' is a claim, not a result.\n\nThe citation pattern is fine; RBFT, Spinning, Prime, and leader-free protocols are discussed, and the novelty claim relative to them holds.\n\nWho is this for? Someone building a BFT transformation layer will get value from the step-wise parallelization, which can likely be fixed and used. The wait-free layer needs a proof or a precise failure-detection interface. I would send this to peer review — a serious referee should spend time on it — but the verdict should hinge on Theorem 4.4. If the authors cannot supply a proof or a stricter soft-failure rule, the paper should be revised to present only the step-wise design.","headline":"Step-wise parallelization is a genuine protocol-agnostic contribution; the wait-free theorem that supports the title is asserted, not proved, and rests on an unstated coordination assumption.","tokens_in":14929,"tokens_out":2980,"would_cite":false,"duration_ms":29405,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Any primary-backup Byzantine fault-tolerant consensus protocol can be parallelized into wait-free instances, so a slow or malicious leader throttles only its own instance and delays stay bounded.","keywords":["Byzantine fault tolerance","primary-backup consensus","wait-free parallelization","soft failure detection","blockchain consensus","deterministic execution order","client assignment","protocol-agnostic design"],"falsifier":"Deliver the same round rho on instance I_i to two non-faulty replicas over asymmetric links, and start round rho+sigma on another instance so that one replica's soft-failure detector classifies I_i as failed while the other has already accepted S(CR_rho) for I_i. If the first replica records F and the second records S(CR_rho) for the same instance and round, non-divergence is broken and Theorem 4.4 is refuted.","tokens_in":13951,"feed_emoji":"🔗","tokens_out":11073,"duration_ms":109360,"temperature":0.7,"pith_summary":"Permissioned blockchains and replicated databases often use primary-backup consensus, where one server—the primary—coordinates each round; if that server is slow or malicious, the whole system waits. This paper proposes to run m parallel instances of the same underlying consensus protocol, each with a different primary, and to combine their decisions into a single execution order. Its central claim is that this can be done in a wait-free way: an instance led by a healthy primary keeps making progress whatever the other instances do, and the time between accepting a client request and executing it stays bounded. The paper further claims the method applies to any well-behaved primary-backup protocol as a black box, evens out replica load, and shrinks the damage a faulty primary can cause.","feed_headline":"Faulty leaders no longer stall blockchain consensus","feed_subtitle":"Running several consensus instances in parallel bounds delays and spreads load across replicas.","key_machinery":"The load-bearing mechanism is the soft-failure principle (Definition 4.3) with the related gap size sigma and skip size epsilon. Each replica locally watches whether its instance is still working on round rho while another instance has already moved to round rho+sigma; if so, it treats the instance's primary as possibly faulty and pushes the instance's current round toward the failure decision F. The skip size epsilon then excludes the recovered instance from the next epsilon rounds so it can catch up, and the paper shows this keeps the per-request execution delay bounded even when one primary crashes or throttles. Two supporting mechanisms complete the design: the unified primary-replacement protocol, which deterministically selects a fresh, unused primary for every failed instance so that all non-faulty replicas agree on the same primary assignment without coordination, and the deterministic round-execution protocol, which orders the client requests accepted in a round by the permutation f_S(Hash(S) mod |S|!) of the accepted requests, so every replica executes them in the same order while no instance has a permanent position of privilege.","core_discovery":"The central claim is Theorem 4.4: when several instances of a primary-backup consensus protocol run in parallel under this design, each instance is wait-free—it can keep making successful consensus decisions without outside interference, and the delay between an instance accepting a client request and replicas executing it is upper-bounded. To get this, the paper introduces a soft-failure rule: an instance that falls more than sigma rounds behind the fastest instance is treated as failed, excluded from the next epsilon rounds, and its current round is moved to a failure decision using the underlying protocol's fault-detection machinery. Combined with a unified primary-replacement rule that lets all replicas pick the same new primary for a failed instance while keeping primaries distinct, and a deterministic hash-seeded permutation that orders each round's accepted requests identically on every replica, the paper argues that the whole parallelized protocol still satisfies termination and non-divergence. Theorem 4.6 states that this method turns any general primary-backup consensus protocol into a high-performance parallelized wait-free protocol in which every client eventually sees its requests executed, non-faulty replicas share load evenly, and faulty replicas have minimal impact.","pith_inferences":["The wait-free guarantee in Theorem 4.4 is inherited from a coordination assumption: a local soft-failure observation must be converted by the underlying protocol into a unified F decision across all non-faulty replicas; the paper treats this as infrastructure, so any implementation must supply it.","Since the ordering digest is unknown to primaries until the round completes, the same hash-seeded ordering could be lifted out and used as a standalone front-running defence in any primary-backup protocol; the paper notes the unpredictability but does not develop this as an independent tool.","A natural next step is empirical: run the design over m instances of an existing PBFT-style implementation, vary m, and compare measured acceptance-to-execution delays with the bound predicted from sigma and epsilon; the paper itself reports no experiments."],"forward_implications":["A single faulty primary can no longer throttle the entire replicated service; only the instance it leads stalls, and it either skips epsilon rounds or is replaced while the other instances keep committing.","The delay between accepting a client request and executing it is bounded by parameters tied to network latency and timeouts, rather than by the slowest or most malicious instance.","Existing PBFT-style implementations can be parallelized without rewriting their internals, because the method only assumes well-defined rounds, termination, and non-divergence.","With round-robin client assignment and instance-change requests, every client eventually sees its request executed, and load is spread evenly across non-faulty replicas.","The same wait-free parallelization applies to partial-consensus protocols, whose eventual checkpoint and recovery steps restore full agreement."],"supporting_citations":[{"why":"Defines the primary-backup PBFT design that the method wraps, and supplies the n > 3f resilience assumption.","marker":"[11]"},{"why":"PBFT with proactive recovery, cited alongside [11] for the termination, non-divergence, and n > 3f assumptions.","marker":"[12]"},{"why":"RBFT's assumption that non-faulty instances progress at comparable speeds is the stated basis of the soft-failure principle.","marker":"[5]"},{"why":"Provides the collision-resistant hash used in the deterministic execution-order permutation.","marker":"[29]"},{"why":"Supplies the consensus requirements of termination and non-divergence that all correctness arguments invoke.","marker":"[39]"}],"fun_headline_variants":["Wait-free parallel consensus spreads leader load","Parallel instances make consensus wait-free","Faulty leaders no longer stall consensus rounds","Consensus without waiting via parallel backup","Parallel protocol reduces leader bottleneck"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole design assumes that when one replica locally decides an instance is lagging, the underlying protocol's fault-detection machinery can make every non-faulty replica end that instance's current round with the same failure decision F, even though different replicas may have different views of who is lagging.","fun_headline_variants_meta":{"raw":{"variants":["Wait-free parallel consensus spreads leader load","Parallel instances make consensus wait-free","Faulty leaders no longer stall consensus rounds","Consensus without waiting via parallel backup","Parallel protocol reduces leader bottleneck"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000145,"raw_usage":{"total_tokens":1172,"prompt_tokens":931,"completion_tokens":241,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":181}},"tokens_in":547,"tokens_out":241,"duration_ms":3337,"temperature":1.0,"reasoning_tokens":181,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:12:41.040223+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Deliver the same round rho on instance I_i to two non-faulty replicas over asymmetric links, and start round rho+sigma on another instance so that one replica's soft-failure detector classifies I_i as failed while the other has already accepted S(CR_rho) for I_i. If the first replica records F and the second records S(CR_rho) for the same instance and round, non-divergence is broken and Theorem 4.4 is refuted.","supporting_citations":[{"cited_title":"Practical byzantine f ault tolerance","cited_arxiv_id":null,"evidence_quote":"Defines the primary-backup PBFT design that the method wraps, and supplies the n > 3f resilience assumption."},{"cited_title":"Menezes, Scott A","cited_arxiv_id":null,"evidence_quote":"Provides the collision-resistant hash used in the deterministic execution-order permutation."},{"cited_title":"Introduction to Distributed Algorithms","cited_arxiv_id":null,"evidence_quote":"Supplies the consensus requirements of termination and non-divergence that all correctness arguments invoke."}],"review_version":1}