REVIEW 4 major objections 5 minor 34 references
Did we miss P In CAP? Partial Progress Conjecture under Asynchrony
T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Figure 3, Lines 10-14 and Section II-B] 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 III-A (Rules 1-6)] 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.
- [Sections II-B, II-D, III-A.1, VI] 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 IV (Figure 4)] 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.
minor comments (5)
- [Abstract, Section IV] The text says 'throughput peeks' and later 'throughout peeks'; these should be 'throughput peaks.'
- [Section III-A (Rule 5)] 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 II-E (Example 2)] 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.
- [Figure 3 and Section III] 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 III (Failure Detection)] 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.
Circularity Check
No significant circularity: the paper's partial-progress claim is an unproven conjecture and protocol design, not a derivation from its own definitions.
full rationale
The paper does not present a derivation chain that reduces to its inputs. 'Partial progress' is defined as non-zero throughput or persistence of at least one partition's requests, and the paper then asserts, without proof, that its CASSANDRA protocol provides this property. That is an unsupported correctness claim, not a circular derivation: the protocol, ranking function, timers, and merge rules are independent constructs that could in principle be checked against the stated guarantee. The modified strongest-proposal rules (Section III-A) are incomplete and appear to contain a pseudocode error at Figure 3 lines 10-14, and no uniqueness proof is given, but these are correctness gaps, not circularity. Self-citations in the related-work and BFT background are not load-bearing for the central conjecture. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work. Therefore the circularity score is 0.
Assumptions & free parameters
free parameters (3)
- proposal timer tau_p =
unspecified
- DRF ranks =
admin-chosen per round
- vote timer and prepare timer =
unspecified
assumptions (3)
- domain assumption Partial synchrony: safety under asynchrony, liveness only during synchrony; at most f crash faults with n=2f+1.
- ad hoc to paper Because all replicas start with the same state and a majority is needed to commit, comparing log suffixes is sufficient to select the strongest proposer.
- ad hoc to paper Timers guarantee that replicas eventually converge on one strongest proposal.
Cite this review
Pith. "Pith review of Did we miss P In CAP? Partial Progress Conjecture under Asynchrony." pith.science (2026). https://pith.science/paper/GGL4ONWK
@misc{pith2026250100021,
author = {Pith},
title = {Pith review of: Did we miss P In CAP? Partial Progress Conjecture under Asynchrony},
year = {2026},
howpublished = {\url{https://pith.science/paper/GGL4ONWK}},
note = {Machine review of arXiv:2501.00021}
}
read the original abstract
Each application developer desires to provide its users with consistent results and an always-available system despite failures. Boldly, the CALM theorem disagrees. It states that it is hard to design a system that is both consistent and available under network partitions; select at most two out of these three properties. One possible solution is to design coordination-free monotonic applications. However, a majority of real-world applications require coordination. We resolve this dilemma by conjecturing that partial progress is possible under network partitions. This partial progress ensures the system appears responsive to a subset of clients and achieves non-zero throughput during failures. To this extent, we present the design of our CASSANDRA consensus protocol that allows partitioned replicas to order client requests.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Towards robust distributed systems (abstract),
E. A. Brewer, “Towards robust distributed systems (abstract),” in Pro- ceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing , ser. PODC ’00. New York, NY , USA: Association for Computing Machinery, 2000, p. 7
work page 2000
-
[2]
A critique of the CAP theorem,
M. Kleppmann, “A critique of the CAP theorem,” CoRR, vol. abs/1509.05393, 2015. [Online]. Available: http://arxiv.org/abs/1509.05393
arXiv 2015
-
[3]
Perspectives on the cap theorem,
S. Gilbert and N. A. Lynch, “Perspectives on the cap theorem,” Com- puter, vol. 45, no. 02, pp. 30–36, feb 2012
work page 2012
-
[4]
C. Cheng, M. Han, N. Xu, S. Blanas, M. D. Bond, and Y . Wang, “Developer’s responsibility or database’s responsibility? rethinking con- currency control in databases,” in 13th Conference on Innovative Data Systems Research, CIDR 2023, Amsterdam, The Netherlands, January 8-11, 2023. www.cidrdb.org, 2023
work page 2023
-
[5]
Is scalable OLTP in the cloud a solved problem?
T. Ziegler, P. A. Bernstein, V . Leis, and C. Binnig, “Is scalable OLTP in the cloud a solved problem?” in 13th Conference on Innovative Data Systems Research, CIDR 2023, Amsterdam, The Netherlands, January 8-11, 2023. www.cidrdb.org, 2023
work page 2023
- [6]
-
[7]
Practical byzantine fault tolerance and proactive recovery,
M. Castro and B. Liskov, “Practical byzantine fault tolerance and proactive recovery,” ACM Trans. Comput. Syst., vol. 20, no. 4, pp. 398– 461, 2002
work page 2002
-
[8]
Impossibility of distributed consensus with one faulty process,
M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,” Journal of the ACM , vol. 32, no. 2, pp. 374–382, 1985
1985
Show all 34 references
-
[9]
The network is reliable: An informal survey of real-world communications failures,
P. Bailis and K. Kingsbury, “The network is reliable: An informal survey of real-world communications failures,” ACM Queue , vol. 12, no. 7, 2014
2014
-
[10]
An analysis of network-partitioning failures in cloud systems,
A. Alquraan, H. Takruri, M. Alfatafta, and S. Al-Kiswany, “An analysis of network-partitioning failures in cloud systems,” in Proceedings of the 13th USENIX Conference on Operating Systems Design and Implemen- tation, ser. OSDI’18. USA: USENIX Association, 2018, p. 51–68
2018
-
[11]
Keeping calm: When distributed consistency is easy,
J. M. Hellerstein and P. Alvaro, “Keeping calm: When distributed consistency is easy,” Commun. ACM, vol. 63, no. 9, p. 72–81, aug 2020
2020
-
[12]
Keep calm and crdt on,
S. Laddad, C. Power, M. Milano, A. Cheung, N. Crooks, and J. M. Hellerstein, “Keep calm and crdt on,” Proc. VLDB Endow. , vol. 16, no. 4, p. 856–863, dec 2022
2022
-
[13]
Metastable failures in the wild,
L. Huang, M. Magnusson, A. B. Muralikrishna, S. Estyak, R. Isaacs, A. Aghayev, T. Zhu, and A. Charapko, “Metastable failures in the wild,” in 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22) . Carlsbad, CA: USENIX Association, Jul. 2022, pp. 73–90
2022
-
[14]
In search of an understandable consensus algorithm,
D. Ongaro and J. Ousterhout, “In search of an understandable consensus algorithm,” in ATC, 2014
2014
-
[15]
DPaxos: Managing Data Closer to Users for Low-Latency and Mobile Applications,
F. Nawab, D. Agrawal, and A. El Abbadi, “DPaxos: Managing Data Closer to Users for Low-Latency and Mobile Applications,” in Pro- ceedings of the 2018 International Conference on Management of Data , ser. SIGMOD ’18. New York, NY , USA: Association for Computing Machinery, 2018...
2018
-
[16]
Transaction processing techniques for modern hardware and the cloud,
J. J. Levandoski, S. Sengupta, R. Stutsman, and R. Wang, “Transaction processing techniques for modern hardware and the cloud,” IEEE Data Eng. Bull., vol. 38, no. 1, pp. 50–57, 2015
2015
-
[17]
Chemistry behind agreement,
S. Gupta, M. J. Amiri, and M. Sadoghi, “Chemistry behind agreement,” in 13th Conference on Innovative Data Systems Research, CIDR 2023, Amsterdam, The Netherlands, January 8-11, 2023 . www.cidrdb.org, 2023
2023
-
[18]
Proof-of- Execution: Reaching consensus through fault-tolerant speculation,
S. Gupta, J. Hellings, S. Rahnama, and M. Sadoghi, “Proof-of- Execution: Reaching consensus through fault-tolerant speculation,” in Proceedings of the 24th International Conference on Extending Database Technology, 2021
2021
-
[19]
ResilientDB: Global scale resilient blockchain fabric,
S. Gupta, S. Rahnama, J. Hellings, and M. Sadoghi, “ResilientDB: Global scale resilient blockchain fabric,” Proc. VLDB Endow., vol. 13, no. 6, pp. 868–883, 2020
2020
-
[20]
ByShard: sharding in a byzantine environ- ment,
J. Hellings and M. Sadoghi, “ByShard: sharding in a byzantine environ- ment,” VLDB J., vol. 32, no. 6, pp. 1343–1367, 2023
2023
-
[21]
RCC: Resilient Concurrent Consensus for High-Throughput Secure Transaction Processing,
S. Gupta, J. Hellings, and M. Sadoghi, “RCC: Resilient Concurrent Consensus for High-Throughput Secure Transaction Processing,” in 37th IEEE International Conference on Data Engineering . IEEE, 2021, pp. 1392–1403
2021
-
[22]
Spotless: Concur- rent rotational consensus made practical through rapid view synchroniza- tion,
D. Kang, S. Rahnama, J. Hellings, and M. Sadoghi, “Spotless: Concur- rent rotational consensus made practical through rapid view synchroniza- tion,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024, pp. 1916–1929
2024
-
[23]
The bedrock of byzantine fault tolerance: A unified platform for {BFT} protocols analysis, implementation, and experimen- tation,
M. J. Amiri, C. Wu, D. Agrawal, A. El Abbadi, B. T. Loo, and M. Sadoghi, “The bedrock of byzantine fault tolerance: A unified platform for {BFT} protocols analysis, implementation, and experimen- tation,” in 21st USENIX Symposium on Networked Systems Design and Implementation ...
2024
-
[24]
Verifiable random functions,
S. Micali, M. Rabin, and S. Vadhan, “Verifiable random functions,” in 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), 1999, pp. 120–130
1999
-
[25]
Pricing via processing or combatting junk mail,
C. Dwork and M. Naor, “Pricing via processing or combatting junk mail,” in Advances in Cryptology — CRYPTO’ 92 . Springer, 1992, pp. 139–147
1992
-
[26]
Gupta, J
S. Gupta, J. Hellings, and M. Sadoghi, Fault-Tolerant Distributed Trans- actions on Blockchain , ser. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2021
2021
-
[27]
Power-of- collaboration: A sustainable resilient ledger built democratically,
J. Chen, S. Gupta, S. Rahnama, and M. Sadoghi, “Power-of- collaboration: A sustainable resilient ledger built democratically,” IEEE Data Engineering Bulletin , 2022
2022
-
[28]
Consistency tradeoffs in modern distributed database system design: Cap is only part of the story,
D. Abadi, “Consistency tradeoffs in modern distributed database system design: Cap is only part of the story,” Computer, vol. 45, no. 2, p. 37–42, feb 2012
2012
-
[29]
FIT: A distributed database performance tradeoff,
J. M. Faleiro and D. J. Abadi, “FIT: A distributed database performance tradeoff,” IEEE Data Eng. Bull. , vol. 38, no. 1, pp. 10–17, 2015
2015
-
[30]
Trade-offs in replicated systems,
R. Guerraoui, M. Pavlovic, and D. Seredinschi, “Trade-offs in replicated systems,” IEEE Data Eng. Bull. , vol. 39, no. 1, pp. 14–26, 2016
2016
-
[31]
Base: An acid alternative: In partitioned databases, trading some consistency for availability can lead to dramatic improvements in scalability
D. Pritchett, “Base: An acid alternative: In partitioned databases, trading some consistency for availability can lead to dramatic improvements in scalability.” Queue, vol. 6, no. 3, p. 48–55, may 2008
2008
-
[32]
Conflict- free replicated data types,
M. Shapiro, N. M. Preguic ¸a, C. Baquero, and M. Zawirski, “Conflict- free replicated data types,” in Stabilization, Safety, and Security of Distributed Systems - 13th International Symposium, SSS 2011, Greno- ble, France, October 10-12, 2011. Proceedings , ser. Lecture Notes ...
2011
-
[33]
Spanner: Google’s Globally-Distributed Database,
J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kan- thak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y . Saito, M. Szymaniak, C. Taylor, R. Wang, a...
2012
-
[34]
Sequoia: A fault-tolerant tighly coupled multiprocessor for transaction processing,
P. A. Bernstein, “Sequoia: A fault-tolerant tighly coupled multiprocessor for transaction processing,” Computer, vol. 21, no. 2, pp. 37–45, 1988
1988
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.