{"id":"f72f142a-1580-4546-b893-442e17460a98","arxiv_id":"2501.00021","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"CASSANDRA lets partitioned replicas speculatively order requests during a partition and claims that at least one partition's transactions will persist after recovery.","lead":"This paper proposes that during a network partition, a distributed system can keep serving a subset of clients at non-zero throughput, and presents a Paxos-style protocol called CASSANDRA to support this 'partial progress'. The claim is framed as a conjecture, not a proved theorem, and the protocol is tested on a 100-replica social-media workload.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Suffix-comparison rules leave divergent committed logs incomparable; with two partitions committing different transactions, Max is undefined and the partial-progress guarantee fails.","rationale":"The reader's verdict of REJECT is supported. The most load-bearing weakness is not just a missing proof but a concrete gap in the deterministic selection mechanism: the suffix-comparison rules are not total over the relevant state space. Two partitions that each commit a different transaction produce logs that the rules cannot compare, so replicas may disagree on the strongest proposal, and the guarantee that transactions from at least one partition persist is unsubstantiated. The Figure 3 pseudocode errors further confirm the protocol is not well-specified. My concern sharpens the reader's weakest-assumption point by isolating a concrete incomparable state, rather than relying only on the unfinished ellipsis entries. As a result, the central claim fails on correctness grounds, and the reader's rejection stands unchanged.","tokens_in":10901,"tokens_out":4097,"duration_ms":37313,"concrete_test":"Enumerate the six suffix-comparison rules in Section III-A against logs hist_i = [T0, Ta] and hist_j = [T0, Tb] (Ta != Tb, both committed). If no rule returns a unique strongest proposer, the protocol cannot guarantee that any partition's committed transactions persist, refuting the headline claim. Also, simulate Figure 3 with a received proposal whose log is a strict superset of the local log; the pseudocode sets Max to DRF(i), contradicting the prose and the Section II-E rules, which would break selection even in a single partition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that CASSANDRA guarantees transactions from at least one partition will persist after a network partition (Section II, Partial Progress under Network Partition). For this to hold, every replica must deterministically identify the same strongest proposal after recovery, using the suffix-comparison rules in Section III-A. Those rules only cover cases where logs share a common prefix and then diverge in prepared/uncommitted entries (rules 1-6). They do not handle the fundamental scenario where two partitions have each committed a different transaction at the same log position — e.g., hist_i = {T0, Ta} and hist_j = {T0, Tb} with Ta != Tb. Rule 1 requires identical suffixes; rules 2-3 compare a log with no committed entry beyond T0 against one with a committed entry; rule 4 requires one side to have only prepared the transaction; rules 5-6 involve prepared entries. None apply to two committed divergent logs, so the strongest proposer is undefined and replicas in different partitions can select different Max. The persistence guarantee is therefore unsupported. In addition, the Figure 3 pseudocode is internally inconsistent with the prose: Lines 10-14 set Max := DRF(i) when the received proposal has a longer log or higher rank, when it should update to DRF(j). Even ignoring this typo, the rules as written do not define a total order over the relevant set of logs, and no proof of uniqueness or of the 'at least one partition persists' property is provided.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper argues that the CAP theorem's 'P' should be broadened from partition tolerance to 'partial progress,' and it presents CASSANDRA, a Paxos-like consensus protocol intended to allow replicas to keep ordering client requests during network partitions. The protocol selects a 'strongest proposer' by comparing replica ranks and the suffixes of committed logs, uses timers for convergence, and is evaluated on a 100-replica Twitter-like workload. The paper frames the central result as a conjecture, provides informal selection rules and pseudocode, and claims that transactions from at least one partition will persist once the network recovers.","tokens_in":11238,"tokens_out":9311,"duration_ms":91356,"significance":"The question of what progress guarantees are achievable during partitions is genuinely relevant, and the paper's attempt to provide a concrete protocol and a real deployment is useful. The experimental deployment is a strength. However, as a correctness contribution the paper does not currently support its claims: the central persistence guarantee is asserted rather than proved, the proposal-selection pseudocode is internally inconsistent, the suffix-comparison rules are incomplete for the divergent-committed-log case that partitions create, and the experimental setup does not exercise the claimed guarantee. If the protocol were repaired, fully specified, and formally verified, the results could be valuable, but this version does not establish them.","major_comments":[{"comment":"The pseudocode for proposal selection sets Max := DRF(i) in both branches: when the received log Lj is a superset of Li, and when Lj = Li and DRF(j) > Max. This assigns the local replica's own rank, not the incoming proposal's rank. The prose in Section II-B states the opposite: 'if a received proposal's log has larger suffix, we update Max to that proposal.' As written, every replica always keeps its own proposal as strongest, so the protocol cannot converge to a common proposal. Even if this is a typographical error, the paper must provide corrected pseudocode and a proof that the corrected selection converges.","section":"Figure 3, Lines 10-14 and Section II-B"},{"comment":"The modified strongest-proposal rules do not cover the fundamental case in which two replicas have committed different transactions at the same log position, e.g., hist_i = {T0, Ta} and hist_j = {T0, Tb} with Ta != Tb. Rule 1 requires identical suffixes, Rules 2-3 compare a log with no committed entry beyond T0 against one with a committed entry, and Rules 4-6 involve prepared entries. None of these rules applies to two committed divergent suffixes, so Max is undefined exactly in the scenario that a partition is designed to produce. Different replicas in the same partition can therefore select different strongest proposals, and the persistence guarantee that 'transactions from at least one partition will persist' is unsupported. The paper needs a total order on the relevant histories, or a proof that the order is unique, before this claim can be evaluated.","section":"Section III-A (Rules 1-6)"},{"comment":"The protocol is under-specified and the central guarantee is not proved. Figure 3 is labeled the failure-free path, while the vote timer, prepare timer, and merge procedure are described only in prose and are not integrated into the pseudocode. Section II-B asserts that 'CASSANDRA is safe and live without timers,' yet Section II-D argues that timers are necessary for uninterrupted transaction processing, and the protocol uses timers throughout. More importantly, Section VI says 'To prove our claim,' but no theorem, invariant, or induction appears anywhere in the paper. The property that transactions from at least one partition persist is the paper's headline claim, so this missing proof is load-bearing; the informal two-bullet argument in Section II-E explains why suffix comparison is chosen but does not establish the guarantee.","section":"Sections II-B, II-D, III-A.1, VI"},{"comment":"The experimental evaluation does not test the paper's stated guarantee. It reports a 60-second partition in which no partition has a majority (f+1) of the replicas; under the protocol's own quorum rule, no partition can then finalize any transaction, so the claim that at least one partition's transactions persist cannot be validated by this setup. The 6x throughput peak after recovery demonstrates buffered speculative execution during the partition, but it does not demonstrate that the speculatively ordered transactions of any particular partition are preserved after recovery. The evaluation should use a configuration with a majority partition or otherwise directly measure the persistence property.","section":"Section IV (Figure 4)"}],"minor_comments":[{"comment":"The text says 'throughput peeks' and later 'throughout peeks'; these should be 'throughput peaks.'","section":"Abstract, Section IV"},{"comment":"Rule 5 contains a malformed expression, 'P rep(Tz, ...})' with an unmatched bracket, and the ellipsis notation for unprepared and uncommitted log entries is introduced informally but never given a precise grammar.","section":"Section III-A (Rule 5)"},{"comment":"Example 2 says R1's log is 'missing entries for T2 and T3,' but the example only introduces T0, T1, and T2; the reference should be to T1 and T2.","section":"Section II-E (Example 2)"},{"comment":"The event-driven pseudocode does not specify round numbers or the behavior for proposals and votes arriving from earlier rounds, which is essential for the merge procedure discussed in Section III-A.1.","section":"Figure 3 and Section III"},{"comment":"The vote timer and prepare timer are introduced as parameters, but the paper does not state how their values should be chosen relative to any synchrony bound; since liveness is only claimed during synchrony, these parameter assumptions should be made explicit.","section":"Section III (Failure Detection)"}],"recommendation":"reject","confidential_remarks":"I recommend rejection rather than major revision because the central guarantee is not merely unproved: the prototype pseudocode is inconsistent with the prose, the ordering rules are incomplete for the divergent-log case, and the evaluation does not exercise the claimed property. If the authors wish to pursue this direction, a revised submission would need a fully specified state machine, a corrected Figure 3, a total order on relevant histories, and either a formal proof or a clearly bounded claim about the persistence guarantee. Alternatively, the paper could be reframed as a speculative position/vision statement that explicitly disclaims correctness proofs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the idea—treating 'partial progress' as a property worth adding to CAP—is genuinely worth discussing, and the paper does a fair job of situating it against PACELC, CAC, BASE, and CALM. Second, as it stands the protocol cannot support the central claim. The suffix-comparison rules in Section III-A do not define a strongest proposal when two partitions have both committed different transactions at the same log position, for example hist_i = {T0, Ta} and hist_j = {T0, Tb} with Ta != Tb. None of rules 1–6 applies to that case, so different replicas can pick different strongest proposals and the 'at least one partition persists' guarantee is unproved. On top of that, the pseudocode in Figure 3 (Lines 10–14) sets Max to DRF(i) when a received log is a superset or has higher rank, whereas the prose says it should become DRF(j). This could be a typo, but as written it defeats the selection logic.\n\nCredit where due: the paper honestly labels its central claim a conjecture. It gives a concrete protocol design, a clear two-phase structure, and a sensible discussion of why naive schemes will not converge. The evaluation deploys on 100 VMs with a Twitter-like workload and reports a 6x throughput peak after recovery. That is real implementation work.\n\nThe soft spots are substantial, though. The novelty is more modest than claimed: strongest-proposer by log suffix is close to Raft's log-completeness rule, and soft commits with later rollback are standard behavior in optimistic replication and BASE systems. The paper says CASSANDRA is the first to guarantee partial progress, but no guarantee is actually proved. The evaluation has no code, no baseline, no error bars, and only three runs; the 6x number is hard to interpret without knowing what fraction of requests were pending during the partition. The text also claims the protocol is safe and live without timers while making timers essential to convergence; that distinction needs care.\n\nWho is this for? Someone thinking about CAP variants and speculative ordering might read it as a discussion piece, not as a protocol paper. Does it deserve a serious referee? Not in this form: the load-bearing ordering problem is unsolved, and the pseudocode error undermines the central artifact. I would desk reject, with an invitation to resubmit if the authors supply a complete and proved ordering relation, repaired pseudocode, and a comparative evaluation. A workshop or position-paper venue could be appropriate for the conjecture.","headline":"A provocative framing and a plausible direction, but CASSANDRA's core is not yet coherent: the strongest-proposer order is incomplete and the pseudocode contradicts the prose.","tokens_in":11729,"tokens_out":3587,"would_cite":false,"duration_ms":34741,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper argues that under network partitions, non-CALM applications can still make progress, and presents the CASSANDRA consensus protocol as a concrete way to achieve it.","keywords":["partial progress","CAP theorem","CALM conjecture","consensus protocol","network partition","strongest proposal","deterministic ranking function","speculative execution"],"falsifier":"Construct a 3-replica run where two replicas end up in the same partition after a split and their logs differ per the modified rules, one having suffix {Tx, Prep(Ty)} and the other {Tx, Tz} with y < z, with ranks assigned so the comparison outcome depends on rule 5 versus rule 6. If after their timers expire the two replicas select different strongest proposals, then the merge procedure cannot reconcile them and the persistence guarantee fails; a concrete check is whether both replicas send their VOTE message to the same replica ID after the timeout.","tokens_in":10701,"feed_emoji":"⚡","tokens_out":3407,"duration_ms":31031,"temperature":0.7,"pith_summary":"The paper asks whether the “P” in CAP could be broadened to mean “partial progress” rather than “partition tolerance,” and answers yes for crash-fault-tolerant replicated systems. It argues that even when a network partitions and no partition holds a majority, replicas can keep processing client requests speculatively, and at least one partition's transactions will persist once connectivity returns. The vehicle is the CASSANDRA consensus protocol, which extends Paxos with a “strongest proposal” selection rule based on a deterministic rank plus the suffix of each replica's committed log. If correct, this gives coordination-requiring applications a way to appear responsive to a subset of clients during partitions and to achieve nonzero throughput during failure windows.","feed_headline":"A partition can still make progress, new protocol argues","feed_subtitle":"CASSANDRA lets partitioned replicas keep ordering client requests, with at least one partition's work persisting after recovery.","key_machinery":"The central object is the “strongest proposal” selection procedure. Each proposer assigns itself a rank with a deterministic ranking function (DRF), and each replica's proposal carries the hash of its ordered log hist, the client transaction, and the rank. A replica marks a proposal as strongest if its proposer has the most committed transactions, and ties are broken by highest rank. The modified merge-procedure rules extend log suffixes with ellipsis entries to represent unprepared, uncommitted transactions and resolve conflicts when replicas prepared different transactions. This selection procedure carries the argument: it is the step that lets partitioned replicas converge on one proposal, vote, and later merge states with the guarantee that committed transactions persist.","core_discovery":"The paper claims that partial progress under network partitions is possible for non-CALM applications, and presents CASSANDRA as the first consensus protocol to guarantee it. CASSANDRA guarantees that transactions from at least one partition will persist after the network heals, provided each replica can identify the strongest proposal after a timeout. The protocol selects the strongest proposal by comparing the deterministic rank of proposers and, when ranks do not decide, comparing the suffixes of the replicas' logs of committed and prepared transactions. The claim is supported empirically by a 100-replica deployment over Twitter-like transaction workloads in which throughput peaks at 6× steady state after partition recovery.","pith_inferences":["If the suffix-comparison rules were proven to yield a unique strongest proposal, the approach could be adapted to Byzantine settings, though malicious replicas could lie about their logs and weaken the comparison.","The conjecture that “P” can be broadened to partial progress suggests a new design axis for geo-replicated systems: instead of choosing consistency versus availability upfront, systems could choose which partition's clients to serve during a split.","A testable extension would be measuring how the 6× recovery throughput depends on partition duration and on the fraction of conflicting transactions, to see whether partial progress scales beyond the Twitter workload."],"forward_implications":["Applications that need coordination can keep serving a subset of clients during a partition instead of stopping entirely.","After the network heals, the system can replay and commit the speculative orders, so the partition's work is not lost.","The design can be layered on Paxos-style crash-fault-tolerant protocol skeletons and, per the paper, may be extendable to modern CFT protocols.","The guarantee that transactions from at least one partition will persist gives a weaker but nonzero availability target under partitions than classic CAP's binary choice."],"supporting_citations":[{"why":"Supplies the CAP theorem that the paper reinterprets by broadening “partition” to “partial progress.”","marker":"[1]"},{"why":"Provides the Paxos consensus structure that CASSANDRA extends with proposal-selection and merge phases.","marker":"[6]"},{"why":"Defines the crash-fault and quorum model that CASSANDRA inherits for its vote and prepare phases.","marker":"[7]"},{"why":"Establishes the impossibility of consensus with one faulty process, motivating why liveness is only guaranteed during synchrony.","marker":"[8]"},{"why":"States the CALM theorem that coordination-free monotonic applications are easy, the baseline that CASSANDRA aims to go beyond.","marker":"[11]"},{"why":"Connects the CALM idea to CRDTs, showing why those approaches do not cover coordination-requiring applications.","marker":"[12]"},{"why":"Represents leader-based consensus that CASSANDRA contrasts with its timer-based, leader-free convergence.","marker":"[14]"}],"fun_headline_variants":["CASSANDRA: partial progress during network partitions","While network splits, CASSANDRA keeps one side writing","At least one partition's writes survive, says CASSANDRA","CASSANDRA claims partial progress under asynchrony"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee rests on the assumption that after a timeout, every replica in a partition will identify the same “strongest proposal” from the suffix-comparison rules, and the paper gives no proof of this uniqueness while the pseudocode's update rule (Lines 10–14) actually sets Max to the local rank when a received proposal has a longer log, which would break the selection.","fun_headline_variants_meta":{"raw":{"variants":["CASSANDRA: partial progress during network partitions","While network splits, CASSANDRA keeps one side writing","At least one partition's writes survive, says CASSANDRA","CASSANDRA claims partial progress under asynchrony"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000675,"raw_usage":{"total_tokens":2996,"prompt_tokens":794,"completion_tokens":2202,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":410,"completion_tokens_details":{"reasoning_tokens":2133}},"tokens_in":410,"tokens_out":2202,"duration_ms":17526,"temperature":1.0,"reasoning_tokens":2133,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:36:51.652753+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a 3-replica run where two replicas end up in the same partition after a split and their logs differ per the modified rules, one having suffix {Tx, Prep(Ty)} and the other {Tx, Tz} with y < z, with ranks assigned so the comparison outcome depends on rule 5 versus rule 6. If after their timers expire the two replicas select different strongest proposals, then the merge procedure cannot reconcile them and the persistence guarantee fails; a concrete check is whether both replicas send their VOTE message to the same replica ID after the timeout.","supporting_citations":[{"cited_title":"The part-time parliament,","cited_arxiv_id":null,"evidence_quote":"Provides the Paxos consensus structure that CASSANDRA extends with proposal-selection and merge phases."},{"cited_title":"Towards robust distributed systems (abstract),","cited_arxiv_id":null,"evidence_quote":"Supplies the CAP theorem that the paper reinterprets by broadening “partition” to “partial progress.”"},{"cited_title":"Practical byzantine fault tolerance and proactive recovery,","cited_arxiv_id":null,"evidence_quote":"Defines the crash-fault and quorum model that CASSANDRA inherits for its vote and prepare phases."},{"cited_title":"Keeping calm: When distributed consistency is easy,","cited_arxiv_id":null,"evidence_quote":"States the CALM theorem that coordination-free monotonic applications are easy, the baseline that CASSANDRA aims to go beyond."},{"cited_title":"Keep calm and crdt on,","cited_arxiv_id":null,"evidence_quote":"Connects the CALM idea to CRDTs, showing why those approaches do not cover coordination-requiring applications."},{"cited_title":"In search of an understandable consensus algorithm,","cited_arxiv_id":null,"evidence_quote":"Represents leader-based consensus that CASSANDRA contrasts with its timer-based, leader-free convergence."}],"review_version":1}