Cassandra: Consensus with Partial Progress via Robust Partitionable View Synchronization

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Cassandra: Consensus with Partial Progress via Robust Partitionable View Synchronization

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

Cassandra: Consensus with Partial Progress via Robust Partitionable View Synchronization Shaokang Xie

Dakai Kang

Junchao Chen

University of California, Davis

Suyash Gupta

Daniel P. Hughes∗

Mohammad Sadoghi

University of Oregon

Radix DLT Ltd.

University of California, Davis

arXiv:2607.02856v1 [cs.DC] 3 Jul 2026

Abstract Replicated databases and permissioned blockchains rely on Byzantine Fault-Tolerant (BFT) consensus to maintain a consistent transaction order across replicas. These protocols preserve safety even under asynchrony, as they commit a transaction only after agreement among a strong quorum of replicas. During network partitions, however, when no strong quorum is reachable, they lose liveness and cannot make useful progress. In this paper, we present Cassandra, a consensus protocol that enables partial progress without sacrificing safety. Cassandra achieves this through a two-tier certification framework that decouples availability from commitment, allowing each partition to extend its own chain and reconcile these chains once the network is restored. To support this, Cassandra introduces a pacemaker that advances views without requiring a strong quorum and calibrates each replica’s timeout off the critical path. Our evaluation results show that Cassandra remains competitive with state-of-the-art BFT protocols under stable conditions, sustaining 900K TPS at 16 replicas and 480K TPS at 104 replicas, with latency ranging from 0.31s at 16 replicas to 0.75s at 104 replicas. Under severe partitions, Cassandra maintains non-zero speculative throughput through PoA-backed progress, preserving work that can be reconciled once connectivity is restored.

Introduction

Decentralized systems offer their clients an immutable ledger even in the presence of faulty or Byzantine behavior. To achieve this, they employ a Byzantine Fault-Tolerant (BFT) consensus protocol that allows multiple distributed parties to maintain a single, globally consistent transaction order over a shared state [22, 45]. Because these parties often hold the same data, they are termed replicas. State-of-the-art BFT protocols, which have served as the foundational building blocks of permissioned blockchains, provide strong fault tolerance and achieve high throughput and low latency under stable network conditions [11, 51]. In practice, however, networks are not always stable. Transient network partitions, delay asymmetries, and intermittent connectivity can disrupt communication among replicas. High-impact production incidents reported by major technology providers such as Amazon and Cloudflare demonstrate that network partitions are not merely a theoretical concern but a recurring operational reality with severe consequences [4, 5, 12–14]. For example, a major Amazon EC2/EBS outage in the us-east-1 region revealed how misrouted traffic and aggressive recovery storms can effectively ∗ In loving memory of Daniel P. Hughes, a valued friend and colleague, whose founda-

tional contributions, ideas, and passion continue to inspire and shape this work.

Traditional BFT (Stalled)

Cassandra (Partial Progress)

Network Partition

Global Log

Group A Local Log

Group B Local Log

✓ ✓ ✓ COMMIT BLOCKED FROZEN

Requires > 2/3 Quorum (3 nodes) Now available: 2 nodes Status: STALLED (Throughput = 0)

✓ ✓ ✓ ACTIVE

ACTIVE

Requires > 1/3 Quorum (2 nodes) Now available: 2 nodes Status: PARTIAL PROGRESS

Figure 1: Comparison between traditional BFT protocols and Cassandra under a network partition. In a 2-2 partition scenario, traditional protocols stall as they cannot reach the required 2/3 quorum, whereas Cassandra maintains partial progress using its Proof of Availability (PoA) mechanism. partition storage clusters, rendering data unavailable for extended periods and causing widespread downtime across SaaS providers and financial platforms, with aggregate losses reaching millions of dollars [5]. Similarly, Cloudflare has experienced outages in which routing anomalies, overloaded or impaired interconnects, and regional reachability failures created partitions between cloud regions [12, 13]. The impact is even more pronounced in decentralized and blockchain systems: network congestion–induced outages in Solana have led to millions of dollars in losses for individual traders [14]. Moreover, partitions are not always accidental: routinglayer attacks, such as BGP hijacks, have been shown to isolate nodes and split the Bitcoin network into disconnected components [7]. These incidents highlight partition-like failures as a practical risk for geo-distributed services. For BFT replicated systems, such partition-like failures create a quorum-stall problem: protocols preserve safety—that is, no two correct replicas commit conflicting transactions—but fail to process new requests when no connected component contains a sufficiently large quorum. This tension between safety and availability is a consequence of the CAP theorem (Consistency, Availability, and Partition tolerance), which states that in the presence of network partitions, a distributed system cannot simultaneously guarantee both consistency and availability [9, 19]. Consequently, BFT systems designed for mostly reliable networks can lose availability under partitions, even though they continue to preserve safety.

Conference’17, July 2017, Washington, DC, USA

Shaokang Xie, Dakai Kang, Junchao Chen, Suyash Gupta, Daniel P. Hughes, and Mohammad Sadoghi

BFT-based decentralized systems can stall under network partitions because the underlying consensus protocol suffers from the following structural dependencies: C1: Strong-Quorum Dependence. Traditional BFT protocols operate under the assumption that the system has at least 𝑛 = 3𝑓 +1 replicas, where 𝑓 denotes the number of faulty replicas. To guarantee that all correct replicas agree on a single transaction order, these protocols require a strong quorum—at least 𝑛−𝑓 (2𝑓 +1)—of replicas to certify a proposal. Under a network partition, replicas are divided into multiple connected components and replicas in different components are unable to communicate with each other (refer to Fig. 1). If no connected component contains a strong quorum (has fewer than 𝑛−𝑓 replicas), then no proposal can form a certificate that justifies non-conflicting commitment. C2: Designated-Leader Dependence. Classic BFT protocols (such as PBFT [10] and HotStuff [51]) operate in rounds, each with a designated leader responsible for determining the order of transactions. However, under a network partition, the leader is unreachable for all but the replicas in its connected component. When progress stalls, replicas assume that the leader has failed and initiate the recovery protocol to replace the leader. However, the recovery protocol itself requires participation of a quorum of replicas. If no partition contains a strong quorum, replicas repeatedly attempt leader replacement without ever making progress. C3: Round-Overlap under Varying Network Delay. Certificate formation also requires replicas to remain in the same round long enough to exchange proposals and votes. Thus, progress depends on sufficient round overlap among replicas in the same connected component. However, under partial synchrony, the effective delay bound is unknown before stabilization and may vary across stabilized periods [10, 17]. A timeout that is too small may cause replicas to leave a round before messages arrive, while an overly conservative timeout increases latency. Consequence: Zero Useful Progress. Together, strong-quorum dependence, leader dependence, and round-overlap requirements imply that existing BFT protocols make no useful progress during a partition unless some connected component can both gather the required quorum and keep enough replicas synchronized in the same round. Replicas may continue retransmitting messages and triggering recovery attempts, but no new transactions can be committed, resulting in zero throughput. In this paper, we present Cassandra, a novel consensus protocol that revisits the practical implications of CAP in decentralized replicated systems [22]. Rather than attempting to achieve full liveness during partitions, Cassandra enables Partial Liveness, allowing partial progress while strictly preserving safety during network partitions. Cassandra addresses the above challenges through three complementary mechanisms. First, Cassandra introduces a two-tier certification mechanism for each transaction: • Proof of Availability (PoA), a certificate formed by collecting votes from a weak quorum of 𝑓 +1 replicas. • Proof of Reliability (PoR), a certificate formed by collecting votes from a strong quorum of 𝑛−𝑓 replicas.

A PoA certificate enables replicas to make partial progress during a network partition. However, to guarantee consistency, Cassandra requires PoR certificates to commit transactions. Second, Cassandra does not designate any replica as “the leader”; instead, it allows all replicas to propose transactions. Each replica then applies our deterministic proposal priority rule to independently select the strongest proposal among those it has received. As a result, even during a network partition, every replica can always identify a locally strongest proposal to vote for. Third, Cassandra deploys a novel decoupled pacemaker for round or view synchronization. Traditional pacemakers do perform round synchronization, but they face the following challenge: C4: Pacemaker Constraints. Existing pacemakers guarantee sufficient round overlap among a strong quorum of 2𝑓 +1 replicas, which may be unavailable under network partitions. Achieving this requires the pacemaker to perform two tasks: advancing replicas’ rounds (or views), and calibrating their timers so that these rounds overlap. However, the pacemaker performs both tasks on the critical consensus path, which degrades system performance. Cassandra decouples these tasks as follows: logical round advancement remains certificate-driven on the critical consensus path, while timeout calibration runs in the background—each replica adjusts its local round timeout independently, without blocking consensus progress. However, one challenge still remains unresolved. C5: Convergence. Although PoA certificates enable progress under network partitions, they also allow different connected components to advance along distinct PoA-backed branches. Because replicas can observe different subsets of proposals, conflicting PoA certificates can coexist, and Byzantine replicas may further equivocate across competing branches. Consequently, once the network is restored, Cassandra must ensure that these divergent partial histories can be reconciled into a single committed order. Cassandra addresses this challenge in two ways. First, its deterministic proposal-priority rule makes reconciliation implicit: once connectivity is restored, correct replicas identify the highestpriority branch as the strongest, vote for it, and extend it with new PoRs. Second, the decoupled pacemaker enables lagging replicas to catch up whenever they observe higher-round certificates. As a result, once a strong quorum becomes reachable again, all correct replicas—whether previously stalled or progressing within separate partitioned components—reconcile their histories by extending the same strongest branch. Our evaluation demonstrates that Cassandra sustains partial progress during network partitions while remaining competitive under stable network conditions. Under steady-state, Cassandra achieves 900K TPS at 16 replicas and 480K TPS at 104 replicas, retaining 53.6% of its throughput, while its latency increases from 0.31s at 16 replicas to 0.75s at 104 replicas. During network partitions, Cassandra achieves a ‘0-to-1’ breakthrough by sustaining Continuous PoA Generation with a speculative throughput of 500K TPS even when global consensus stalls (Figure 12.c). This accumulated partial progress enables a rapid recovery burst upon network restoration, allowing the system to efficiently reconcile divergent histories and resume peak performance quickly. Specifically, we make the following contributions:

Cassandra : Consensus with Partial Progress via Robust Partitionable View Synchronization

• We introduce a two-tier certification mechanism that separates partial progress (PoA) from final commitment (PoR), enabling progress within connected components while preserving safety. • We eliminate reliance on a designated leader by allowing all replicas to propose continuously and to independently vote for the strongest proposal according to a deterministic proposal-priority rule. This design enables local chain extension during partitions. • We design a decoupled pacemaker that enables round advancement even with weak quorums, while calibrating local timeouts in the background, off the critical path. • We show that divergent PoA-backed histories accumulated during partitions can reconcile once connectivity is restored. • We conduct an extensive evaluation of Cassandra under both stable and partitioned network conditions. Our results demonstrate that Cassandra remains competitive with state-of-the-art protocols in synchronous settings while sustaining non-zero useful progress during severe partitions.

System Model

Adversary Model. We consider a distributed system consisting of 𝑛 replicas, each assigned a unique identifier 𝑖 ∈ {1, . . . , 𝑛}. We denote the replica with identifier 𝑖 by 𝑝𝑖 . The system tolerates up to 𝑓 Byzantine replicas, where 𝑛 ≥ 3𝑓 + 1. Byzantine replicas, also referred to as faulty replicas, may exhibit arbitrary or malicious behaviors that deviate from the consensus protocol. The remaining replicas are correct (or honest) and strictly follow the protocol. The system processes requests from clients, and we allow any number of clients to be arbitrarily faulty. Authenticated Communication. We assume an authenticated communication model based on standard public-key cryptography [31]. Each client and replica possesses a public–private key pair and uses digital signatures to authenticate messages. A sender signs a message using its private key, and any recipient can verify the signature using the corresponding public key. We denote by ⟨𝑚⟩𝑝𝑖 a digital signature over message 𝑚 produced by replica 𝑝𝑖 . Correct replicas accept only well-formed messages that carry valid signatures. We assume that Byzantine replicas are computationally bounded and cannot forge signatures or break the cryptographic primitives used by correct replicas. We further assume the existence of a collision-resistant hash function H(·), meaning it is computationally infeasible to find two distinct inputs 𝑥 ≠ 𝑦 such that H(𝑥) = H(𝑦). Threshold-Signature Setup. In addition to ordinary digital signatures, Cassandra uses threshold signatures for compact certificates: an (𝑓 +1, 𝑛) scheme for weak-quorum certificates and the deterministic threshold coin and a (2𝑓 +1, 𝑛) scheme for strong-quorum PoR certificates. We assume that the corresponding threshold verification keys and replica signing shares are generated before any runtime partition, either by a trusted dealer or by executing a standard DKG protocol [18, 44] while the replicas are fully connected. Network Model. We assume the partial synchrony model of Dwork et al. [17]. Existing BFT protocols assume the existence of a single Global Stabilization Time (GST) after which the network remains permanently synchronous [29, 51]. In contrast, we incorporate a more realistic setting that allows recurring network

Conference’17, July 2017, Washington, DC, USA

partitions. Specifically, we assume an unbounded sequence of stabilized periods, each beginning at a stabilization point GST𝑘 , where GST1 < GST2 < · · ·. During each stabilized period, the network is synchronous for a sufficiently long but possibly finite interval, meaning that messages between correct replicas are delivered within an unknown bound Δ. Outside such synchronous periods, we make no global timing or connectivity assumptions: the network may be asynchronous, partially connected, or partitioned into multiple connected components. Our partial-progress guarantees are therefore conditioned on any connected component in which messages among mutually reachable correct replicas are delivered within Δ.

Achieving Partial Progress under Network Partitions

Traditional BFT protocols cannot make progress during a network partition unless at least 2𝑓 +1 replicas can reach one another; we refer to such a set as a strongly connected component. Cassandra, by contrast, aims to enable partial progress while preserving safety even when no such strongly connected component exists. It achieves this goal through the following design principles: (1) Eliminating futile recovery traffic. When no strongly connected component exists, it is wasteful for replicas to repeatedly trigger recovery mechanisms in an attempt to achieve global synchronization. Instead, they should continue issuing new proposals based on locally available connectivity. (2) Partitionable leaders. During a network partition, not all replicas can necessarily reach the replica designated as leader. Instead, each replica should take over this role itself, independently selecting the strongest proposal from those it has received. (3) Weak-quorum ordering. During a network partition, replicas may be unable to reach a strongly connected component. In that case, they should order transactions based on weak quorums, while recognizing that such decisions are non-final and must be reconciled once a strong quorum becomes available. (4) Decoupled pacemaker. Traditional pacemakers are designed to synchronize a strong quorum of replicas, and they do so by placing all round-synchronization logic on the critical consensus path. Because such a quorum may be unavailable during a network partition, a pacemaker should instead be able to coordinate a weak quorum of replicas, while keeping much of this coordination off the critical path.

3.1

Tools for Partial Progress

To implement the aforementioned design principles, we introduces: (1) Partitionable Leader Election. (2) Decoupled Pacemaker Design. Next, we explain how these tools help Cassandra enable partial progress during network partition. (1) Partitionable Leader Election. Permitting leader election to proceed even when no strongly connected component exists allows each partition to make progress independently, without waiting for a dedicated leader. We achieve this goal through two new principles: two-tier certification and deterministic proposal priority.

Conference’17, July 2017, Washington, DC, USA

Shaokang Xie, Dakai Kang, Junchao Chen, Suyash Gupta, Daniel P. Hughes, and Mohammad Sadoghi

Proposal Exchange

Two-Tier Certification. Because no strongly connected component is available during a network partition, we allow replicas to make decisions based on weaker connected components. Consequently, to guarantee safety, we require two types of certificates. • Proof of Availability (PoA). A PoA requires votes from at least 𝑓 +1 replicas and guarantees that the proposal’s payload is retrievable within the system, but it does not guarantee a final commit. • Proof of Reliability (PoR). A PoR requires votes from at least 𝑛−𝑓 replicas. It certifies global consistency and prevents conflicting commits. Deterministic Proposal Priority Rule. Eliminating the need for replicas to wait for a designated leader means they must instead determine the next leader themselves, and this determination must be deterministic so that PoAs can be formed. Consequently, in each round, every replica broadcasts a proposal and independently identifies the leader from the proposals it receives. Each proposal is ranked according to the recency of the certificates it carries—first by the highest referenced PoR, and then by the highest referenced PoA. Intuitively, proposals backed by more recent strong-quorum evidence are preferred, while weak-quorum evidence serves as a tie-breaking signal reflecting more recent partial progress. If multiple proposals remain tied within the same round, replicas resolve the tie using a deterministic threshold-coin mechanism derived from proposal signature shares. This guarantees that all correct replicas observing the same proposal set select the same strongest proposal, enabling partition-local convergence without centralized leadership. Implicit Reconciliation on Network Recovery. During a network partition, replicas may form PoA certificates for diverging chains within different components. However, because proposal selection is deterministic and prioritized by certificate recency, correct replicas converge on the same strongest proposal and vote for it as soon as the network recovers. New PoRs then form on that branch, re-establishing a single, globally committed order. Reconciliation is thus not performed by an explicit merge protocol; it emerges naturally from deterministic proposal selection once certificate-driven round synchronization is restored. (2) Decoupled Pacemaker Design. Although partitionable leader election is necessary for progress, it is not sufficient. A successful election requires replicas to remain in the same round (or view) long enough to exchange proposals and votes, so a mechanism for round synchronization is essential. Prior work employs a pacemaker that aligns a strong quorum of 𝑛−𝑓 replicas on a common round, ensuring sufficient overlap for them to exchange messages. Moreover, the pacemaker runs on the critical consensus path and thus degrades consensus performance. We achieve this through a novel decoupled pacemaker that separates the pacemaker’s two tasks: round advancement and timeout calibration. Round advancement remains on the critical consensus path, while timeout calibration is now handled by a separate background mechanism. Round Advancement. A replica advances from round 𝑟 to 𝑟 +1 under two cases: (i) when a PoR is formed, indicating successful certification by a strong quorum; or (ii) when, after round 𝑟 times

Election and Certification

Next Round

P1𝑟

Vote P2𝑟

PoR-P2𝑟

P1𝑟 +1

...

P2𝑟

Vote P2𝑟

PoR-P2𝑟

P2𝑟 +1

...

P3𝑟

Vote P2𝑟

PoR-P2𝑟

P3𝑟 +1

...

P4𝑟

Vote P4𝑟

PoR-P2𝑟

P4𝑟 +1

...

R4 is Faulty

Figure 2: A round of Cassandra. out, a weak quorum of 𝑓 +1 replicas requests a round advancement. In both cases, there is sufficient information for lagging replicas to jump immediately to the highest certified round. Convergence toward a common round is guaranteed because round numbers increase monotonically and replicas accept certificates only for strictly higher rounds. During synchronous periods, certificates propagate within Δ, bounding divergence among correct replicas. Timeout Calibration. Another equally important role of the pacemaker is ensuring sufficient round overlap among replicas to facilitate the exchange of messages and proposals. This must happen even under unknown and time-varying delays, and it should remain off the critical path. We meet this goal not by forcing all replicas to synchronize on a single timeout value, but by allowing each replica to calibrate its own local timeout.

3.2

System Guarantees

In a system of 𝑛 = 3𝑓 +1 replicas, where up to 𝑓 replicas may be Byzantine, Cassandra offers the following guarantees: • Safety: If two correct replicas 𝑝𝑖 and 𝑝 𝑗 commit two transactions 𝑡𝑥 1 and 𝑡𝑥 2 at the same position in the log, then 𝑡𝑥 1 = 𝑡𝑥 2 . • Liveness: During any sufficiently long stabilized synchronous period, correct replicas continuously commit new proposals containing client transactions. Moreover, Cassandra offers partial liveness even during network partitions. Specifically, we introduce the following property: • Partial Liveness: While the network is partitioned, any synchronous connected component containing at least 𝑓 +1 correct replicas continues ordering new proposals containing client transactions.

Cassandra

Cassandra aims to drive BFT consensus among replicas while guaranteeing partial liveness even during periods of network partition. To this end, Cassandra must ensure the following: • Partitionable chain construction. This enables replicas within each connected component to keep proposing, allowing the chain to grow even when a strong quorum is unreachable. Cassandra achieves this through partitionable leader election. • Round synchronization. This keeps replicas sufficiently synchronized to exchange messages and form certificates, and provides lagging replicas a mechanism to catch up. Cassandra achieves this through the decoupled pacemaker.

4.1

Partitionable Chain Construction

Cassandra proceeds in a sequence of rounds (or views). Each round consists of two phases: proposal exchange and election and

Cassandra : Consensus with Partial Progress via Robust Partitionable View Synchronization

Structure of Proposal 𝑃𝑟 Round Number

Transactions

enterCert

Hash of Parent

Highest PoA & PoR

Local Log (Chain of Certificates) Proposal 1 PoR

Round 2 RC

Proposal 3 PoA

Proposal 4 PoR

Data Structure (replica 𝑝𝑖 ) : Data structures & State d 𝑃𝑜𝐴⟩ d Proposal Msg: 𝑃 ≜ ⟨𝑟, txs, parent, enterCert, 𝑃𝑜𝑅, d 𝑖 , 𝑃𝑜𝐴 d 𝑖 , 𝑙𝑜𝑐𝑘𝑖 Local State: 𝑟𝑖 (round), L𝑖 (log), 𝑃𝑜𝑅 Buffer State: P𝑖 [𝑟 ] (proposals), voteSet𝑖 (votes), Voted𝑖 (flag) Local Timers: 𝛿𝑖 , ExchangeTimer, ElectionTimer Helper Functions (replica 𝑝𝑖 ) :

Proposal 5 PoR

...

Figure 3: Cassandra’s Proposal and Local Log Chain. certification (refer to Figure 2). A replica enters a new round by following the pacemaker’s round advancement rules (§3.1). Phase 1: Proposal Exchange. At the start of round 𝑟 , each replica aggregates a set of pending client transactions into a proposal. Each proposal extends the last committed proposal; each replica maintains a local log L of committed proposals (Fig. 3) and sets the hash of the proposal at the tail as 𝑝𝑎𝑟𝑒𝑛𝑡 and its corresponding certificate as the highest PoR. Additionally, the proposal includes the highest PoA (if any) and a certificate, which proves that the sender is in round 𝑟 . This exchange takes place during an exchange window, in which replicas collect round-𝑟 proposals from one another. As in other partially synchronous protocols, Cassandra assumes that each replica 𝑖 maintains a local timeout parameter 𝛿𝑖 (with 𝛿𝑖 ≤ Δ) that delimits the phases within each round. However, in Cassandra the value of Δ is unknown a priori, so we make the value of 𝛿𝑖 able to calibrate dynamically over time (Section 4.2.3). Within a connected component, we assume an exchange window of size 2𝛿𝑖 , which should suffice for proposals from honest replicas to propagate under synchrony. Phase 2: Election and Certification. Next, from all the valid proposals a replica receives, it deterministically selects a Strongest Proposal and broadcasts its Vote. Concretely, each proposal P is ranked by its latest certificates (PoR and PoA), d , 𝑅𝑜𝑢𝑛𝑑 (P.𝑃𝑜𝐴) d , S(P) ≜ 𝑅𝑜𝑢𝑛𝑑 (P.𝑃𝑜𝑅) d and P.𝑃𝑜𝐴 d denote the highest-round PoR and PoA where P.𝑃𝑜𝑅 referenced by P and S(P) is the strongest proposal. Replicas use the following lexicographic ordering to compare proposals: (1) Highest PoR: A proposal whose log contains a PoR from a higher round is always preferred, as it represents a more recent globally reliable certificate. (2) Highest PoA: If two proposals have the same highest PoR round, the one with a higher PoA round is preferred, as it reflects more recent partial progress. If multiple proposals remain tied in round 𝑟 , replicas apply a deterministic common-coin tie-breaker. To support this, every proposal carries the proposer’s threshold signature share for round 𝑟 (refer to Section 2). Let 𝑆𝑟 be any set of 𝑓 +1 valid threshold signature shares from distinct proposals in round 𝑟 , and aggregating any valid set of 𝑓 +1 shares yields the same round coin 𝐶𝑟 . C𝑟 = ThresholdAggregate(𝑆𝑟 ) Score(P) = 𝐻 (C𝑟 ∥ P.sender).

Conference’17, July 2017, Washington, DC, USA

1: function ValidEnterCert(𝑐𝑒𝑟𝑡, 𝑟 ) do 2: return 𝑐𝑒𝑟𝑡 is well-formed and one of: 3: (i) 𝑐𝑒𝑟𝑡 = genesis and 𝑟 = 1, or 4: (ii) 𝑐𝑒𝑟𝑡 is PoR with round (𝑐𝑒𝑟𝑡 ) = 𝑟 − 1, or 5: (iii) 𝑐𝑒𝑟𝑡 is RC with round (𝑐𝑒𝑟𝑡 ) = 𝑟 − 1 6: function SafeToVote(𝑃 ) do 7: return 𝑃 is valid and either 8: (i) 𝑃 extends 𝑙𝑜𝑐𝑘𝑖 , or 9: (ii) 𝑃 carries a PoR from a strictly higher round 10: function SelectStrongest( P ) do 11: return the proposal in P with highest priority

⊲Section 4.1

12: event EnterRound (𝑟, 𝑐𝑒𝑟𝑡, 𝑡𝑥 ) do 13: if 𝑟 ≤ 𝑟𝑖 or ValidEnterCert (𝑐𝑒𝑟𝑡, 𝑟 ) = False then return 14: Cancel ExchangeTimer [𝑟𝑖 ] ; Cancel ElectionTimer [𝑟𝑖 ] 15: 𝑟𝑖 ← 𝑟 ; Voted𝑖 [𝑟𝑖 ] ← False 16: if P𝑖 [𝑟𝑖 ] is uninitialized then P𝑖 [𝑟𝑖 ] ← ∅ 17: start ExchangeTimer [𝑟𝑖 ] with timeout 𝑡𝑥 18: 𝑝𝑎𝑟𝑒𝑛𝑡 ← hash ( TailOfLog ( L𝑖 ) ) d 𝑖 , 𝑃𝑜𝐴 d𝑖) 19: 𝑃 ★ ← NewProposal (𝑟𝑖 , txs, 𝑝𝑎𝑟𝑒𝑛𝑡, 𝑐𝑒𝑟𝑡, 𝑃𝑜𝑅 d 𝑖 , 𝑃𝑜𝐴 d 𝑖 carry the highest known PoR and PoA ⊲𝑃𝑜𝑅 20: Broadcast( ⟨ Propose (𝑃 ★ ) ⟩ ) 21: P𝑖 [𝑟𝑖 ] ← P𝑖 [𝑟𝑖 ] ∪ {𝑃 ★ } ⊲self-proposal 22: function UpdateHiCert(𝑐𝑒𝑟𝑡 ) do d 𝑖 ) then 𝑃𝑜𝑅 d 𝑖 ← 𝑐𝑒𝑟𝑡 23: if 𝑐𝑒𝑟𝑡 is PoR and round (𝑐𝑒𝑟𝑡 ) > round ( 𝑃𝑜𝑅 d 𝑖 ) then 𝑃𝑜𝐴 d 𝑖 ← 𝑐𝑒𝑟𝑡 24: if 𝑐𝑒𝑟𝑡 is PoA and round (𝑐𝑒𝑟𝑡 ) > round ( 𝑃𝑜𝐴 25: function MaybeAdvanceLockAndCommit(𝑙𝑜𝑐𝑘𝑖 , 𝑐𝑒𝑟𝑡 ) do 26: ⊲Two-PoR Rule—lock on the 1st PoR, commit at the 2nd PoR 27: if 𝑐𝑒𝑟𝑡 and its ancestors form the required PoR chain then 28: update 𝑙𝑜𝑐𝑘𝑖 to the latest safely locked proposal 29: commit older proposals according to the above rule

Figure 4: Utility and Helper Functions for Cassandra

The proposal with the highest Score(·) is designated as the Strongest Proposal of round 𝑟 , which we denote as 𝑆𝑃𝑟 . Each replica then broadcasts a Vote for 𝑆𝑃𝑟 . If a proposal gathers 𝑄 = 2𝑓 +1 votes, a PoR is formed. If it times out before forming a PoR but gathers 𝑄 weak = 𝑓 +1 votes, a PoA is formed. 4.1.1 Locking and Commitment. Replicas independently interpret their local logs and finalize proposals by applying a deterministic locking and commit rule over PoRs. Locking Rule. Each replica maintains a local variable 𝑙𝑜𝑐𝑘𝑖 representing the highest PoR-certified proposal it has observed. A replica votes only for proposals that extend 𝑙𝑜𝑐𝑘𝑖 , unless it observes a PoR from a strictly higher round. Commitment Rule. A proposal 𝑏𝑟 is committed once it forms a twoPoR chain. Formally, if 𝑏𝑟 and its immediate successor 𝑏𝑟 +1 both obtain PoRs (i.e., 𝑃𝑜𝑅𝑟 and 𝑃𝑜𝑅𝑟 +1 ), and 𝑏𝑟 +1 extends 𝑏𝑟 , then 𝑏𝑟 and all its ancestors become committed (Figure 6). Safety Intuition. Each PoR is formed by a strong quorum of size 2𝑓 +1. Any two such quorums intersect in at least 𝑓 +1 replicas, including at least one honest replica. Once 𝑃𝑜𝑅𝑟 and 𝑃𝑜𝑅𝑟 +1 are

Conference’17, July 2017, Washington, DC, USA

Shaokang Xie, Dakai Kang, Junchao Chen, Suyash Gupta, Daniel P. Hughes, and Mohammad Sadoghi

Round Logic (replica 𝑝𝑖 ) : Initialization d 𝑖 , 𝑃𝑜𝐴 d 𝑖 to genesis; 𝑟𝑖 ← 0 initialize 𝑙𝑜𝑐𝑘𝑖 , 𝑃𝑜𝑅 Call EnterRound (1, genesis, 2𝛿𝑖 ) 1: event Received valid ⟨ Propose (𝑃𝑟 ) ⟩ from 𝑝 𝑗 do if 𝑃𝑟 .round < 𝑟𝑖 or ValidEnterCert (𝑃𝑟 .𝑒𝑛𝑡𝑒𝑟𝐶𝑒𝑟𝑡, 𝑃𝑟 .round ) = False 2: then return ⊲Outdated or invalid d ; UpdateHiCert (𝑃𝑟 .𝑃𝑜𝐴) d 3: UpdateHiCert (𝑃𝑟 .𝑃𝑜𝑅) d 4: MaybeAdvanceLockAndCommit (𝑙𝑜𝑐𝑘𝑖 , 𝑃𝑟 .𝑃𝑜𝑅) ⊲Update local safety state before processing this proposal 5: if 𝑃𝑟 .round > 𝑟𝑖 then ⊲Fast-forward to an existing higher round 6: Call pacemaker.ObserveHigherRound (𝑃𝑟 ) 7: if SafeToVote (𝑃𝑟 ) then 8: P𝑖 [𝑃𝑟 .round ] ← P𝑖 [𝑃𝑟 .round ] ∪ {𝑃𝑟 } 9: event ExchangeTimer [𝑟 ] timeout ⊲Exchange phase ends do 10: if 𝑟 ≠ 𝑟𝑖 or Voted𝑖 [𝑟 ] then return 𝑠𝑎𝑓 𝑒 11: P𝑖 [𝑟 ] ← {𝑃 ∈ P𝑖 [𝑟 ] | SafeToVote (𝑃 ) } 12: 13: 14: 15: 16: 17: 18:

𝑠𝑎𝑓 𝑒

if P𝑖 [𝑟 ] = ∅ then ExitRound (𝑟, ⊥) ; return 𝑠𝑎𝑓 𝑒 𝑃 𝑠𝑝 ← SelectStrongest ( P𝑖 [𝑟 ] ) voteSet𝑖 [𝑟, hash (𝑃 𝑠𝑝 ) ] ← voteSet𝑖 [𝑟, hash (𝑃 𝑠𝑝 ) ] ∪ {𝑝𝑖 } Broadcast( ⟨ Vote (𝑟, hash (𝑃 𝑠𝑝 ) ) ⟩ ) Voted𝑖 [𝑟 ] ← True start ElectionTimer [𝑟 ] with timeout 𝛿𝑖

19: event Received valid ⟨ Vote (𝑟, ℎ) ⟩ from 𝑝 𝑗 ⊲Collect votes do 20: if 𝑟 ≠ 𝑟𝑖 then return 21: voteSet𝑖 [𝑟, ℎ] ← voteSet𝑖 [𝑟, ℎ] ∪ {𝑝 𝑗 } 22: 𝑐 ← | voteSet𝑖 [𝑟, ℎ] | 23: if 𝑐 ≥ 𝑄 then ⊲strong quorum 𝑄 = 2𝑓 +1 24: ⟨ PoR, ℎ⟩ ← BuildCert (𝑟, ℎ, 𝑐, PoR ) 25: append ⟨ PoR, ℎ⟩ to L𝑖 26: UpdateHiCert ( ⟨ PoR, ℎ⟩ ) d𝑖 ) 27: MaybeAdvanceLockAndCommit (𝑙𝑜𝑐𝑘𝑖 , 𝑃𝑜𝑅 28: ExitRound (𝑟, ⟨ PoR, ℎ⟩ ) 29: event ElectionTimer [𝑟 ] timeout ⊲Election phase ends do 30: if 𝑟 ≠ 𝑟𝑖 then return 31: ℎ★ ← arg maxℎ | voteSet𝑖 [𝑟, ℎ] | 32: 𝑐 ★ ← | voteSet𝑖 [𝑟, ℎ★ ] | 33: if 𝑐 ★ ≥ 𝑄 𝑤𝑒𝑎𝑘 then ⊲weak quorum 𝑄 𝑤𝑒𝑎𝑘 = 𝑓 +1 34: ⟨ PoA, ℎ★ ⟩ ← BuildCert (𝑟, ℎ★, 𝑐 ★, PoA ) ★ 35: append ⟨ PoA, ℎ ⟩ to L𝑖 36: UpdateHiCert ( ⟨ PoA, ℎ★ ⟩ ) ⊲PoA preserves progress, but does not justify next-round entry 37: ExitRound (𝑟, ⊥) 38: event ExitRound (𝑟, 𝑐𝑒𝑟𝑡 ) do 39: if 𝑟 ≠ 𝑟𝑖 then return 40: Cancel ExchangeTimer [𝑟 ] ; Cancel ElectionTimer [𝑟 ] 41: Call pacemaker.CompleteRound (𝑟, 𝑐𝑒𝑟𝑡 )

Figure 5: Pseudocode of Round Logic in Cassandra

formed for a chain extending 𝑏𝑟 , at least 𝑓 +1 honest replicas participating in 𝑃𝑜𝑅𝑟 +1 become locked on the proposal containing 𝑏𝑟 . Due to quorum intersection and the single-vote rule, no conflicting proposal can subsequently gather a strong quorum in round 𝑟 +1 or beyond. Hence, two conflicting proposals cannot both satisfy the two-PoR commit condition, ensuring the safety of consensus.

4.2

Round Synchronization

To form either a PoR or a PoA, replicas must remain in the same round long enough to exchange proposals and votes. Classical pacemakers often place this synchronization logic directly on the critical consensus path and require a strong quorum of replicas for synchronization. Under network partitions, such designs stall.

Not ready to commit

Proposal 1 PoR

Round 2 RC

Proposal 3 PoA

Proposal 4 PoA

Proposal 5 PoR

A new PoR generated in round 6 Ready to commit

Skip this round

Ready to commit

Not ready to commit

Proposal 1 PoR

Round 2 RC

Proposal 3 PoA

Proposal 4 PoA

Proposal 5 PoR

Proposal 6 PoR

Figure 6: An Example of Two-PoR Commit Rule Cassandra instead deploys a decoupled pacemaker: round advancement remains certificate-driven on the critical path, while timeouts are calibrated off the critical path through a background synchronization service. This design simultaneously supports: (i) partial progress within weak connected components of at least 𝑓 +1 replicas, and (ii) fast catch-up and convergence once 2𝑓 +1 replicas become connected. 4.2.1 Round Advancement Conditions. After the election and certification phase, replicas participate in the round advancement phase. A replica in round 𝑟 advances to round 𝑟 +1 in exactly one of the following two cases: • PoR-based. If a proposal in round 𝑟 gathers a strong quorum of votes and forms a 𝑃𝑜𝑅𝑟 , replicas advance to round 𝑟 +1. • RC-based advancement. If no proposal forms a 𝑃𝑜𝑅𝑟 before the election timer expires, the replica broadcasts a WishNewRound(r) message. Once it collects 𝑓 +1 such messages, it forms a Round Certificate (𝑅𝐶 𝑟 ) and advances to round 𝑟 +1. Crucially, these rules control logical round advancement in the consensus path: replicas continue progressing through proposal exchange, voting, and PoR/RC formation without waiting for a separate timeout synchronization procedure to complete. 4.2.2 Quick Catch-Up and Fast Convergence. Once a replica forms a PoR or RC certificate, it broadcasts the certificate so that any lagging replica can immediately jump to the justified round. Concretely, if a replica is currently in round 𝑟 ′ and receives a valid PoR or RC formed in round 𝑟 > 𝑟 ′ , it advances to round 𝑟 +1. Since round numbers increase monotonically and replicas only accept certificates for strictly higher rounds, certificate dissemination induces convergence toward the highest justified round. If a lagging replica receives 𝑃𝑜𝑅𝑟 , it learns that round 𝑟 has successfully produced a strong certificate and advances accordingly. If it receives 𝑅𝐶 𝑟 , it learns that an honest replica in round 𝑟 could not form a PoR and synchronizes by advancing to round 𝑟 +1. During synchronous periods after GST, such certificates propagate within Δ, bounding round divergence among correct replicas by at most one message delay. This also explains why the Proposal Exchange phase spans 2𝛿𝑖 : one 𝛿𝑖 for round synchronization and one 𝛿𝑖 for proposal dissemination. In particular, once a strong quorum becomes connected again, certificate dissemination rapidly pulls lagging replicas toward the highest justified round, without requiring an explicit synchronization barrier on the critical path. 4.2.3 Background Timeout Calibration. Cassandra operates under a partially synchronous network model, in which message delays are bounded by some Δ that holds only during stabalized periods

Cassandra : Consensus with Partial Progress via Robust Partitionable View Synchronization

⟨𝑆𝑌 𝑁𝐶-𝑅𝐸𝐴𝐷𝑌 ⟩

Pacemaker𝑖 (Round Advancement & Timeout Calibration) : Local state: 𝑟𝑖 , 𝐾 𝛿𝑖 , 𝜈𝑖 Calibrating𝑖 𝑅𝑒𝑎𝑑 𝑦𝑆𝑒𝑡 [𝜈 ], 𝐶𝑒𝑟𝑡𝑆𝑒𝑡 [𝜈 ]

⊲current round and timeout calibration interval ⊲local timeout baseline and current sync view ⊲whether a calibration attempt is in progress ⊲valid ⟨𝑆𝑌 𝑁𝐶 ⟩ messages

1: function CompleteRound(𝑟, 𝑐𝑒𝑟𝑡 ) do 2: if 𝑟 𝑚𝑜𝑑 𝐾 = 0 then ⊲Reach the SyncTimeout boundary. 3: Call pacemaker.SyncTimeout 4: if 𝑐𝑒𝑟𝑡 is PoR then 5: Call EnterRound (𝑟 +1, 𝑐𝑒𝑟𝑡, 2𝛿𝑖 ) ⊲A PoR directly justifies entry into the next round 6: else Broadcast ⟨ WishNewRound (𝑟 ) ⟩ ⊲If no PoR, request for an RC for round advancement 7: event Received 𝑓 +1 ⟨ WishNewRound (𝑟 ) ⟩ messages do 8: ⟨𝑅𝐶𝑟 ⟩ ← AggregateSig ( 𝑓 +1 ⟨ WishNewRound (𝑟 ) ⟩ ) 9: Broadcast( ⟨𝑅𝐶𝑟 ⟩ ) 10: event Received ⟨𝑅𝐶𝑟 ⟩ do 11: Call EnterRound (𝑟 +1, 𝑅𝐶𝑟 , 2𝛿𝑖 ) ⊲An 𝑅𝐶𝑟 safely coordinates entry into round 𝑟 +1 12: function ObserveHigherRound(𝑃 ) do if 𝑃 .𝑟 ≤ 𝑟𝑖 or ValidEnterCert (𝑃 .𝑒𝑛𝑡𝑒𝑟𝐶𝑒𝑟𝑡, 𝑃 .𝑟 ) = False then return 13: ⊲The 𝑒𝑛𝑡𝑒𝑟𝐶𝑒𝑟𝑡 certifies the round entry ⊲Use a shortened timeout since round 𝑟 ′ is already in progress 14: Call EnterRound (𝑃 .𝑟, 𝑃 .𝑒𝑛𝑡𝑒𝑟𝐶𝑒𝑟𝑡, 𝛿𝑖 ) 15: event SyncTimeout do 16: if Calibrating𝑖 = False then 17: 𝜈𝑖 ← 𝜈𝑖 + 1; Calibrating𝑖 ← True 18: Broadcast( ⟨SYNC-READY, 𝜈𝑖 ⟩𝑖 ) 19: event Received valid ⟨SYNC-READY, 𝜈 ⟩ from 𝑝 𝑗 do 20: 𝑅𝑒𝑎𝑑 𝑦𝑆𝑒𝑡 [𝜈 ] [ 𝑗 ] ← ⟨SYNC-READY, 𝜈 ⟩ 𝑗 21: 𝑉 ℎ𝑖 ← {𝜈 ′ | 𝜈 ′ > 𝜈𝑖 and |𝑅𝑒𝑎𝑑 𝑦𝑆𝑒𝑡 [𝜈 ′ ] | ≥ 𝑓 + 1} 22: if 𝑉 ℎ𝑖 ≠ ∅ then 23: 𝜈𝑖 ← min 𝑉 ℎ𝑖 ; Calibrating𝑖 ← True 24: Broadcast( ⟨SYNC-READY, 𝜈𝑖 ⟩𝑖 ) 25: if CertSet𝑖 [𝜈 ] [𝑖 ] = ⊥ and |𝑅𝑒𝑎𝑑 𝑦𝑆𝑒𝑡 [𝜈 ] | ≥ 2𝑓 + 1 then 26: CertSet𝑖 [𝜈 ] [𝑖 ] ← ⟨SYNC-CERT, 𝜈 ⟩𝑖 27: Broadcast( ⟨SYNC-CERT, 𝜈 ⟩𝑖 ) 28: start 𝑆 𝑦𝑛𝑐𝑇 𝑖𝑚𝑒𝑟 [𝜈 ] with timeout 𝛿𝑖 29: event Received valid ⟨SYNC-CERT, 𝜈 ⟩ from 𝑝 𝑗 do 30: 𝐶𝑒𝑟𝑡𝑆𝑒𝑡 [𝜈 ] [ 𝑗 ] ← ⟨SYNC-CERT, 𝜈 ⟩ 𝑗 31: if 𝐶𝑒𝑟𝑡𝑆𝑒𝑡 [𝜈 ] [𝑖 ] ≠ ⊥ and |𝐶𝑒𝑟𝑡𝑆𝑒𝑡 [𝜈 ] | > 𝑓 + 1 then 32: Calibrating𝑖 ← False; Cancel 𝑆 𝑦𝑛𝑐𝑇 𝑖𝑚𝑒𝑟 [𝜈 ] ⊲𝛿𝑖 is sufficient; decrease if success was fast (Section 4.2.3) 33: event 𝑆 𝑦𝑛𝑐𝑇 𝑖𝑚𝑒𝑟 [𝜈 ] timeout do 34: if |𝐶𝑒𝑟𝑡𝑆𝑒𝑡 [𝜈 ] | ≤ 𝑓 then 35: 𝛿𝑖 ← 2𝛿𝑖 ; 𝜈𝑖 ← 𝜈𝑖 + 1 36: Broadcast( ⟨SYNC-READY, 𝜈𝑖 ⟩𝑖 )

Figure 7: Pseudocode of the Pacemaker (after some GST) and whose value is not known a priori. Because the actual delay can differ across stable periods—particularly after long partitions or asymmetric delays—replicas’ local timeouts may become misaligned. To address this, existing pacemakers perform timeout calibration, but they do so on the critical path. To address this, Cassandra runs a periodic background timeoutcalibration service, denoted SyncTimeout, which adjusts each replica’s local timeout value (𝛿𝑖 ). This service is off the critical path: it never blocks the chain construction process. Replicas initiate SyncTimeout periodically, e.g., once every 𝐾 rounds (𝐾 is a system parameter), provided that no prior calibration attempt is still in progress. Each calibration attempt is identified by a synchronization view number 𝜈. The view number is used to distinguish retries and

Conference’17, July 2017, Washington, DC, USA

⟨𝑆𝑌 𝑁𝐶 − 𝐶𝐸𝑅𝑇 ⟩

⟨𝑆𝑌 𝑁𝐶-𝑅𝐸𝐴𝐷𝑌 ⟩

⟨𝑆𝑌 𝑁𝐶-𝐶𝐸𝑅𝑇 ⟩

⟨𝑆𝑌 𝑁𝐶-𝑅𝐸𝐴𝐷𝑌 ⟩

⟨𝑆𝑌 𝑁𝐶-𝐶𝐸𝑅𝑇 ⟩

⟨𝑆𝑌 𝑁𝐶-𝑅𝐸𝐴𝐷𝑌 ⟩

⟨𝑆𝑌 𝑁𝐶-𝐶𝐸𝑅𝑇 ⟩

Figure 8: Timeout Calibration prevent replay of stale synchronization messages. If a calibration attempt fails, replicas keep retrying in the background using higher synchronization views, while the main protocol remains unchanged and continues running. Phase 1: ⟨SYNC-READY⟩. After every 𝐾-th round, if replica 𝑝𝑖 is not undergoing a timeout-calibration, it initiates a calibration attempt in synchronization view 𝜈 by broadcasting ⟨SYNC-READY, 𝜈⟩𝑖 . Replica 𝑝𝑖 keeps periodically retransmitting this message until it receives either 2𝑓 +1 such messages for view 𝜈 or 𝑓 +1 such messages for higher views 𝜈 ′ . In the latter case, replica 𝑝𝑖 abandons view 𝜈 and joins the smallest view 𝜈 ′ among these 𝑓 +1 messages by broadcasting ⟨SYNC-READY, 𝜈 ′ ⟩𝑖 . Phase 2: ⟨SYNC-CERT⟩. Once a replica 𝑝𝑖 collects 2𝑓 +1 valid SYNC -READY messages for its synchronization view 𝜈, it creates and broadcasts a ⟨SYNC-CERT, 𝜈⟩𝑖 , message. After that, 𝑝𝑖 waits on a timer of length 𝛿𝑖 for SYNC-CERT messages from other replicas. Success Condition. The calibration attempt in view 𝜈 succeeds at replica 𝑝𝑖 if: 𝑝𝑖 formed a ⟨SYNC-CERT, 𝜈⟩𝑖 , and within period 𝛿𝑖 , it received ⟨SYNC-CERT, 𝜈⟩ from at least 𝑓 + 1 distinct replicas (i.e., the total number of certificates, including its own, exceeds 𝑓 +1). This condition ensures that replica 𝑝𝑖 ’s current timeout 𝛿𝑖 is long enough to allow at least one honest replica to generate and send back a certificate under the current network condition. In this case, replica 𝑝𝑖 keeps its current timeout baseline unchanged. Failure handling. We distinguish two failure cases: (1) No local certificate formed. If replica 𝑝𝑖 cannot collect 2𝑓 +1 valid SYNC-READY messages for view 𝜈, it leaves 𝛿𝑖 unchanged and keeps retransmitting ⟨SYNC-READY, 𝜈⟩𝑖 . (2) Insufficient remote certificates received. If replica 𝑝𝑖 succeeds in forming ⟨SYNC-CERT, 𝜈⟩𝑖 but does not receive this certificate from at least 𝑓 +1 distinct replicas within time 𝛿𝑖 , the attempt is treated as a failure. In this case, replica 𝑝𝑖 doubles its local timeout period, i.e., 𝛿𝑖 ← 2𝛿𝑖 , advances to the next synchronization view 𝜈 ← 𝜈 + 1, and restarts the procedure by broadcasting a new ⟨SYNC-READY, 𝜈⟩. Timeout Decrease. Classical BFT protocols such as PBFT [11] double the view-change timeout whenever a view change fails to make progress, but never decrease it. As a result, a single transient period of high delay can leave rounds unnecessarily long well after the delay has subsided. Cassandra optionally permits decreasing 𝛿𝑖 upon a sufficiently fast calibration success. Concretely, if a calibration attempt succeeds and the elapsed time since replica 𝑝𝑖 formed its local ⟨SYNC-CERT, 𝜈⟩𝑖 is less than 𝛿𝑖 /𝛼 for a pre-set threshold 𝛼 > 1 (e.g., 𝛼 = 4), 𝑝𝑖 halves its local timeout baseline: 𝛿𝑖 ← max(𝛿𝑖 /2, 𝛿 min ), where 𝛿 min is a pre-configured lower bound. The subsequent calibration attempt then verifies whether the reduced timeout is still sufficient; if not, it is doubled back. This yields

Conference’17, July 2017, Washington, DC, USA

Shaokang Xie, Dakai Kang, Junchao Chen, Suyash Gupta, Daniel P. Hughes, and Mohammad Sadoghi

Generate Proposal Proposal Disseminate

Pacemaker (Timeout Calibration) (replica 𝑝𝑖 ) : Local State 𝛿𝑖 , 𝜈𝑖 Calibrating𝑖 𝑅𝑒𝑎𝑑 𝑦𝑆𝑒𝑡 [𝜈 ] 𝐶𝑒𝑟𝑡𝑆𝑒𝑡 [𝜈 ]

⊲local timeout baseline and current sync view ⊲whether a calibration attempt is in progress ⊲valid ⟨SYNC-READY, 𝜈 ⟩ messages ⊲valid ⟨SYNC-CERT, 𝜈 ⟩ messages

1: event SyncTimeout do 2: if Calibrating𝑖 = False then 3: 𝜈𝑖 ← 𝜈𝑖 + 1; Calibrating𝑖 ← True 4: Broadcast( ⟨SYNC-READY, 𝜈𝑖 ⟩𝑖 ) 5: event Received valid ⟨SYNC-READY, 𝜈 ⟩ from 𝑝 𝑗 do 6: 𝑅𝑒𝑎𝑑 𝑦𝑆𝑒𝑡 [𝜈 ] [ 𝑗 ] ← ⟨SYNC-READY, 𝜈 ⟩ 𝑗 7: 𝑉 ℎ𝑖 ← {𝜈 ′ | 𝜈 ′ > 𝜈𝑖 and |𝑅𝑒𝑎𝑑 𝑦𝑆𝑒𝑡 [𝜈 ′ ] | ≥ 𝑓 + 1} 8: if 𝑉 ℎ𝑖 ≠ ∅ then 9: 𝜈𝑖 ← min 𝑉 ℎ𝑖 ; Calibrating𝑖 ← True 10: Broadcast( ⟨SYNC-READY, 𝜈𝑖 ⟩𝑖 ) 11: if CertSet𝑖 [𝜈 ] [𝑖 ] = ⊥ and |𝑅𝑒𝑎𝑑 𝑦𝑆𝑒𝑡 [𝜈 ] | ≥ 2𝑓 + 1 then 12: CertSet𝑖 [𝜈 ] [𝑖 ] ← ⟨SYNC-CERT, 𝜈 ⟩𝑖 13: Broadcast( ⟨SYNC-CERT, 𝜈 ⟩𝑖 ) 14: start 𝑆 𝑦𝑛𝑐𝑇 𝑖𝑚𝑒𝑟 [𝜈 ] with timeout 𝛿𝑖 15: event Received valid ⟨SYNC-CERT, 𝜈 ⟩ from 𝑝 𝑗 do 16: 𝐶𝑒𝑟𝑡𝑆𝑒𝑡 [𝜈 ] [ 𝑗 ] ← ⟨SYNC-CERT, 𝜈 ⟩ 𝑗 17: if 𝐶𝑒𝑟𝑡𝑆𝑒𝑡 [𝜈 ] [𝑖 ] ≠ ⊥ and |𝐶𝑒𝑟𝑡𝑆𝑒𝑡 [𝜈 ] | > 𝑓 + 1 then 18: Calibrating𝑖 ← False; Cancel 𝑆 𝑦𝑛𝑐𝑇 𝑖𝑚𝑒𝑟 [𝜈 ] ⊲𝛿𝑖 is sufficient; decrease if success was fast (Section 4.2.3) 19: event 𝑆 𝑦𝑛𝑐𝑇 𝑖𝑚𝑒𝑟 [𝜈 ] timeout do 20: if |𝐶𝑒𝑟𝑡𝑆𝑒𝑡 [𝜈 ] | ≤ 𝑓 then 21: 𝛿𝑖 ← 2𝛿𝑖 ; 𝜈𝑖 ← 𝜈𝑖 + 1 22: Broadcast( ⟨SYNC-READY, 𝜈𝑖 ⟩𝑖 )

Figure 9: Pseudocode of Background Timeout Calibration a multiplicative-increase/multiplicative-decrease pattern analogous to TCP congestion control [28], adapted to the BFT setting where safety is never at risk because 𝛿𝑖 affects only round duration, not the correctness of voting or certification.

4.3

Merge after Network Recovery

A PoA-backed branch guarantees data availability, provides ordering evidence, and reduces wasted work after recovery. However, it is provisional and does not imply final commitment. During a network partition, different connected components may therefore extend the same PoR along divergent PoA chains. The same reasoning applies to asymmetric partitions in which a Byzantine replica selectively forwards proposals across components: forwarding may create additional provisional PoA branches, which introduces additional computation costs linear in the number of PoAs for verification, but does not force a pairwise merge of all branches or roll back any committed state. When network connectivity is restored, replicas resume exchanging proposals in the proposal exchange phase. Each proposal carries its sender’s highest known PoR and PoA, summarizing the strongest certificates that replica has observed. During the election phase, replicas then apply the deterministic proposal-priority rule: proposals anchored at a higher-round PoR are always preferred, and ties are broken by the highest-round PoA and then the threshold coin. Consequently, once proposals from previously disconnected components become visible across the network, correct replicas deterministically converge on the same strongest branch and vote for it. This allows a new PoR to form on that branch, re-establishing a single, globally agreed PoR. The remaining PoA branches—those not extended by a subsequent PoR—stop growing and are eventually

P1𝑟

Vote Collection by 𝐿𝑟 +1

PoR Next Aggregation Round

Vote P1𝑟

PoR P1𝑟

P2𝑟 +1

R4 Figure 10: Fast Path Workflow in Good Cases

superseded. Because PoA formation guarantees data availability, the proposals on these branches remain retrievable; however, only the branch incorporated into a subsequent PoR can be finalized. Merging in Cassandra is therefore implicit and protocol-driven: no separate reconciliation procedure is required, as the normal proposal-selection and certification process automatically converges the system back to a single chain once connectivity is restored.

Cassandra: Dual-path Design

Although Cassandra achieves partial progress under network partitions, it relies on all-to-all proposal exchange and conservative timeouts; as a result, it incurs quadratic communication complexity and forgoes optimistic responsiveness [51], preventing replicas from proceeding at network speed even when the network is stable. In this section, we present an optimized version of Cassandra based on a dual-path design. In the absence of leader or network failures, the system runs an optimistic fast path that assumes a designated leader and lets replicas reach consensus with linear communication. If the fast path fails, replicas fall back to the base path (§4).

5.1

Linear-Complexity Fast Path

Cassandra’s fast-path assumes a dedicated leader for each round; let 𝐿𝑟 be the leader for round 𝑟 (leaders are selected in a round-robin manner). The fast-path undergoes the following steps (Fig. 10). • Fast-path proposal. On entering round 𝑟 (i.e., on receiving a 𝑃𝑜𝑅𝑟 −1 or an 𝑅𝐶𝑟 −1 ), the leader 𝐿𝑟 broadcasts a proposal 𝑏𝑟 . This proposal extends the highest known branch and carries the sender’s d and 𝑃𝑜𝐴 d certificates (similar to the base path). latest 𝑃𝑜𝑅 • Linear vote collection. Upon receiving 𝑏𝑟 , each replica verifies that it is valid and lock-compatible (cf. Section 4.1.1). If this is the case, the replica sends its vote share to a designated collector, e.g., the next-round leader 𝐿𝑟 +1 . • Pipelined certificate formation. Once 𝐿𝑟 +1 collects a strong quorum of vote shares for 𝑏𝑟 , it aggregates them into a 𝑃𝑜𝑅𝑟 . This 𝑃𝑜𝑅𝑟 then serves as the justification to enter round 𝑟 +1, allowing 𝐿𝑟 +1 to immediately propose the next block. In summary, the fast path modifies only the message-collection pattern used to form a PoR; it does not alter the safety rule, the locking rule, or the certificate semantics. As a result, under stable conditions, Cassandra substantially reduces its communication complexity, from quadratic to linear.

5.2

Fallback to the Base Path

Each replica maintains a dedicated Fast-Path Timer to detect failures. For example, if a replica does not receive a valid fast-path proposal from 𝐿𝑟 in time, or if the designated collector fails to gather a strong

Cassandra : Consensus with Partial Progress via Robust Partitionable View Synchronization

Fast Path

R1 R2

Leader Failed

Base Path

Next Round

P1𝑟

Vote P2𝑟

PoR-P2𝑟 P1𝑟 +1

P2𝑟

Vote P2𝑟

PoR-P2𝑟

P3𝑟

Vote P2𝑟

PoR-P2𝑟

R4 P4𝑟

PoR-P2𝑟 Fast-Path Timeout Fallback to Base Path

Figure 11: Fallback from Fast Path to Base Path quorum of vote shares before the timer expires, the replica abandons the fast path and falls back to the base path (Fig. 11). The base Path resumes within the same round and follows the steps described in Section 4.1. Concretely, each replica broadcasts its own round-𝑟 proposal and participates in the proposal exchange and election and certification phases. These proposals include locally d and 𝑃𝑜𝐴 d certificates, so safety and proposal known highest 𝑃𝑜𝑅 priority remain unchanged. On entering the next round, replicas again attempt the fast path. The transition between the fast and base paths is therefore seamless: the fast path is a performance optimization layered on the base protocol, not a separate consensus protocol.

5.3

Dissemination Layer in Cassandra

Prior work such as Narwhal [15] and AutoBahn [20] introduce the notion of a dissemination layer that decouples data dissemination from ordering. Concretely, the dissemination layer continuously broadcasts batches of transactions and certifies their availability across replicas, while the ordering layer concurrently proposes references to the already-disseminated data. This decoupling is complementary to Cassandra’s design and can be integrated with modest changes.

5.4

Speculative Execution over PoA

A PoA certificate in Cassandra does not guarantee final commitment, but it does certify that a proposal has made recoverable partial progress. To avoid leaving this certified work idle during a partition, replicas may speculatively execute PoA-backed proposals before they are committed via a PoR. The execution result can be returned to the client as speculative output, though it does not constitute a final commit. After recovery, if the branch becomes the strongest branch, its speculative execution is reused on the committed path; otherwise, the speculative state is discarded, and its transactions must be re-proposed through the normal path. Speculative execution thus provides a meaningful way to measure partial progress.

Conference’17, July 2017, Washington, DC, USA

Proof Sketch

This section summarizes the main arguments behind Cassandra’s safety, liveness under partial synchrony, and partial liveness. Full proofs are deferred to Appendix A [1]. Theorem 1 (Safety). No two correct replicas commit (finalize) conflicting proposals. Proof sketch. The argument follows from three ingredients. First, any two strong quorums of size 2𝑓 +1 intersect in at least 𝑓 +1 replicas, and therefore share at least one correct replica. Second,

a correct replica casts at most one vote per round. Hence, two conflicting proposals cannot both obtain valid PoR certificates in the same round. Across rounds, safety is preserved by the locking rule. Once a correct replica observes a PoR for a proposal, it locks that proposal (or a later descendant on the same branch) and will not vote for a conflicting one unless it observes a strictly higher-round PoR on the competing proposal’s certified ancestry. Therefore, once a proposal becomes commit-ready under the Two-PoR rule, the second PoR contains at least 𝑓 +1 correct voters that are locked on that branch. By quorum intersection, any later strong quorum for a conflicting branch must intersect this locked set in at least one correct replica, which prevents the conflicting branch from gathering the certified chain needed for commitment. □

6.1

Liveness

Theorem 2 (Liveness (with probability 1)). During any sufficiently long stabilized synchronous period, correct replicas commit new proposals continuously; over an unbounded sequence of such stabilized periods, commits occur infinitely often with probability 1. Proof sketch. During a sufficiently long stabilized synchronous period, the background timeout-calibration mechanism eventually makes every correct replica’s local timeout baseline 𝛿𝑖 sufficiently large relative to the actual network delay bound. Once local timeouts are sufficient, PoRs and RCs are delivered within the underlying synchronous delay bound. Since every valid higher-round proposal carries one of these certificates as its enterCert, certificate dissemination together with proposal-driven fast catch-up eventually re-aligns correct replicas into recurring good rounds, in which all correct replicas enter the same round early enough to complete proposal exchange and vote collection. In each good round, all correct replicas observe the same set of honest proposals. If there is a unique strongest proposal, they all vote for it directly. Otherwise, ties are broken by the common coin; 2𝑓 +1 with probability at least 𝑛 , the selected top-scoring proposer is honest, in which case all correct replicas converge on the same proposal and form a valid PoR. Since good rounds recur and each one succeeds with non-zero probability, PoRs occur infinitely often almost surely. Whenever two consecutive rounds produce extending PoRs, the Two-PoR rule commits the earlier proposal in the chain. □

6.2

Partial Liveness

Theorem 3 (Partial Liveness). Cassandra satisfies the Partial Liveness property. Specifically, during network partitions, any connected component that contains at least 𝑓 +1 correct replicas and whose internal message delays are bounded by Δ, and whose correct replicas use local timeout baselines satisfying 𝛿𝑖 ≥ Δ, continues to advance rounds locally and produce PoA-certified partial progress. After network recovery, this accumulated partial progress remains recoverable and can be incorporated into subsequent PoR-backed commitment. Proof sketch. Consider any connected component containing at least 𝑓 +1 correct replicas and timely internal communication. Within such a component, correct replicas can still exchange proposals within one local round and apply the same priority rule to

Conference’17, July 2017, Washington, DC, USA

Shaokang Xie, Dakai Kang, Junchao Chen, Suyash Gupta, Daniel P. Hughes, and Mohammad Sadoghi

identify a common strongest candidate. As a result, the component can assemble a weak quorum and form a PoA, thereby preserving certified partial progress even without a global strong quorum. If no PoR is formed in that round, correct replicas eventually time out and broadcast WishNewRound; since the component contains at least 𝑓 +1 correct replicas, they can form an RC for the next round and continue advancing locally. Thus, under partition, Cassandra preserves both round progression and recoverable partial progress. A PoA does not imply commitment, but it does imply data availability: at least one correct replica stores the certified proposal. Once global connectivity is restored, a strong quorum becomes reachable again, and replicas resume forming PoRs on the strongest recoverable branch. Through the catch-up and back-fill mechanisms, previously accumulated PoA-backed progress can be retrieved, extended, and incorporated into the committed prefix. □

Evaluation

To validate our partial-progress claims, we implement Cassandra and evaluate it against several state-of-the-art BFT protocols: Tusk [15], AutoBahn [20], PBFT [10], HotStuff [51], SpotLess [30], and RCC [23]. Our evaluation targets two key metrics—throughput and latency—and aims to address the following research questions: • Q1: How does Cassandra scale under stable network conditions compared with existing BFT protocols? (Section 7.2) • Q2: How does Cassandra behave under network partitions, from 𝑓 partitioned replicas to balanced partitions? (Section 7.3) • Q3: How robust is Cassandra under Byzantine behaviors such as intentional delay and tail-forking attacks? (Section 7.4) • Q4: What do the ablation study and latency breakdown reveal about Cassandra’s performance? (Section 7.5) • Q5: How does Cassandra perform under geo-distributed regional partitions? (Section 7.6)

7.1

Implementation and Evaluation Setup

Implementation. We implement Cassandra in C++ [2] as a core consensus component within the open-source Apache ResilientDB platform [6, 24], a scalable blockchain infrastructure. The prototype reuses ResilientDB’s networking, batching, execution, monitoring, and key-management pipeline. Messages are authenticated through ResilientDB’s Crypto++ verifier, and our experiments use Ed25519 replica keys generated by ResilientDB’s key-generation tool. PoA, PoR, and RC certificates are formed by collecting authenticated replica votes and checking corresponding thresholds. Unless stated otherwise, Cassandra enables the fast path, the dissemination layer, and speculative execution. Speculative execution lets replicas execute a PoA-backed proposal before final PoR commitment. This avoids long execution queues and reduces executor idleness during partitions, which in turn speeds up recovery once the network is restored. For experiments involving network partitions, we report speculative throughput, which counts PoA-backed proposals that have been locally ordered and executed but not yet finally committed. Evaluation Setup. We deploy c5.4xlarge instances (16 vCPUs, 32 GB memory) on AWS in Northern Virginia. For geo-distributed experiments, we use four regions: Northern Virginia, São Paulo,

Frankfurt, and Singapore. Each replica is assigned a dedicated client so that all proposers propose at the same rate, and each client issues transactions in an open loop at a rate sufficient to saturate its replica. We also batch transactions for processing. For benchmarking, we use ResilientDB’s key-value service, in which each transaction is a randomly generated key-value insertion of a fixed size (50 bytes). All reported numbers are averaged over three runs.

7.2

Performance Under Normal Conditions

First, we study the scalability of Cassandra under stable network conditions (no failures). Figure 12(a) varies the number of replicas from 16 to 104. All protocols exhibit a similar trend: as the number of replicas grows, throughput decreases and latency increases, because more participants must reach agreement. All protocols except PBFT and HotStuff sustain high throughput, as they are not constrained by a single-leader design. PBFT achieves higher throughput than HotStuff because its replicas can process transactions out of order, whereas HotStuff’s rotating-leader design prohibits this. Cassandra has a deterministic proposal-priority rule and dissemination, while Tusk, AutoBahn, RCC, and SpotLess employ similar multiproposer or decoupled data paths. Cassandra’s partial-progress mechanisms, however, marginally increase latency relative to the lowest-latency baselines. At 104 replicas, Cassandra’s throughput is within 1.5% of AutoBahn’s.

7.3

Performance under Network Partitions

Next, we study the impact of network partitions on different protocols by increasing the number of partitioned replicas. 7.3.1 0 → 𝑓 → 0 Partition. First, we ensure that only 𝑓 replicas are partitioned (from 24s to 44s), i.e., a strongly connected component of 2𝑓 +1 replicas still exists (Figure 12(b)). All protocols except PBFT experience a drop in throughput (and a rise in latency) during this partition; PBFT remains relatively stable because its leader lies within the 2𝑓 +1 connected component. HotStuff, Tusk, and AutoBahn degrade due to their rotating-leader designs. Tusk’s wave-based consensus periodically completes a large batch of requests whenever the leader is not partitioned away, while AutoBahn’s dissemination layer helps it sustain higher throughput after a brief period of zero throughput caused by its HotStuff-style ordering layer. RCC and SpotLess both run multi-leader protocols: after an initial drop, RCC retains two-thirds of its steady-state performance once it excludes the 𝑓 partitioned replicas, whereas SpotLess’s multiple rotational-leader instances make it behave similarly to AutoBahn, since some views always have partitioned leaders. Cassandra, in contrast, continues forming PoR certificates and finalizing transactions. It does incur a 33.7% throughput drop relative to stable settings, due to the smaller set of connected replicas and the switching between fast and base paths. 7.3.2 𝑓 → 𝑓 +1 → 𝑓 Partition. Next, we assume all protocols run in a state where 𝑓 replicas are always partitioned, and then (from 24s to 32s) one additional replica is partitioned, bringing the total to 𝑓 +1, so that the largest connected component contains only 2𝑓 replicas (Figure 12(c)). All protocols except Cassandra drop to zero throughput once more than 𝑓 replicas are partitioned, since they require a strong quorum to run consensus. Cassandra, in contrast,

Cassandra : Consensus with Partial Progress via Robust Partitionable View Synchronization

Cassandra

Latency (s) Throughput (TPS)

Latency (s)

Throughput (TPS)

AutoBahn

1.2

Latency (s) Throughput (TPS)

Tusk

(a) Protocol Scalability under Failure-free Conditions

105

16 105

104

0.4 0.0

(d) Partitioned Replicas: f

n/2

Replicas

0.8

f Partitioned

n/2 Partitioned

Replicas

104

Normal

f Partitioned

Throughput (TPS)

0 Normal

8 4 0 4 3 2 1 0

20 105

Running Time (s) 40 (e) Slow-Leader Attack

Normal

f Slow Leaders

Normal

0 1.5 1.0 0.5 0.0

1.0 0.5

Running Time (s) 40

0.0

105 8

Normal

Partition: 0

No-Diss-No-Spec

f Partitioned

No-Spec

Normal

Cassandra

f Partitioned

Running Time (s) 40

Partition: f

f+1 Partitioned

f+1

1.2

f Partitioned

0.4 0

1.0 0.5 0

Running Time (s)

105

f+1 Partitioned

f f Partitioned

Running Time (s) 40 (f) Tail-forking Attack

Normal

Tail-forking Attack Enabled

(h) Geo-Distributed Regional Partition: 0 Normal

f Partitioned

0.8

0 1.5

0.0

f Partitioned

RCC f+1

Normal

0 4 3 2 1 0

0 105

SpotLess 105

0 4 3 2 1 0

(g) Ablation Study

Latency (s)

HotStuff f

f f Partitioned

PBFT (b) Partitioned Replicas: 0

105

Conference’17, July 2017, Washington, DC, USA

4 3 2 1 0

20 Running Time (s) 40 f+1 (a whole region) f 0

f+1 Partitioned One region partitioned

Running Time (s)

f Partitioned

Normal

Figure 12: Evaluation summary across scalability and partition scenarios. observes only a 15% drop in throughput (and a 52% increase in latency), because PoAs require just 𝑓 +1 votes and thus continue to drive partial progress through speculative execution. Once the system returns to an 𝑓 -replica partition, the strong quorum becomes reachable again and all protocols resume committing blocks. AutoBahn shows the largest throughput burst, as its dissemination layer keeps operating as long as 𝑓 +1 replicas remain connected; however, because those proposals cannot be ordered during the partition, it also exhibits high latency. 7.3.3 𝑓 → ⌊𝑛/2⌋ → 𝑓 Partition. Next, we consider a scenario in which roughly 50% of all replicas are partitioned (from 24s to 32s), leaving a single connected set of ⌈𝑛/2⌉ replicas (Figure 12(d)). As in the previous experiment, all protocols except Cassandra drop to zero throughput, since they stop processing transactions altogether. In Cassandra, the connected replicas can still generate PoAs and speculatively execute transactions, though throughput falls by 21% due to the smaller connected set. Once the system is restored to an 𝑓 -replica partition, all protocols behave as described above. For Cassandra, however, the recovery burden is greater than in §7.3.2, as far more replicas must be reconciled.

7.4

Performance under Byzantine Behavior

Next, we study the impact of Byzantine attacks on the different protocols. First, in Figure 12(e), we consider a leader delay attack in which 𝑓 Byzantine replicas delay proposals and messages by 50 ms. All protocols show only a marginal drop in throughput and return to steady state quickly, but they do suffer a large latency spike. Cassandra incurs only a 40% latency increase during the delay interval, whereas HotStuff increases by nearly 300%. This is because Cassandra can switch between the fast and base paths when the leader is delayed.

Next, we evaluate the impact of a tail-forking attack (Figure 12(f)). In a tail-forking attack, 𝑓 faulty replicas are strategically placed across rounds and leader positions to create short forks or unfinished tails. As a result, all protocols except PBFT experience a sustained throughput drop, as proposals are dropped before they can commit—under leader rotation, the next leader may itself be faulty. PBFT’s throughput is unaffected, since we do not designate its leader as faulty. Cassandra’s latency, however, is less volatile than that of the other protocols: whenever the leader is faulty, replicas fall back to the base path and select the strongest proposal. This raises latency but keeps it predictable. In contrast, the other protocols rely on their ordering layer to resolve or bypass these unfinished tails.

7.5

Ablation Study and Latency Breakdown

In Figure 12(g), we isolate the effect of Cassandra’s various optimizations under network partitions: (i) No-Diss-No-Spec disables both the dissemination layer and speculative execution; and (ii) No-Spec enables dissemination but disables speculative execution. In the 0 → 𝑓 → 0 case, a strongly connected component remains reachable, so the real impact comes from enabling or disabling the dissemination layer. Enabling dissemination improves partitionperiod throughput by 2.27×, because unselected proposals remain available and can be reused rather than discarded as wasted work. In the 𝑓 → 𝑓 +1 → 𝑓 case, the middle interval lacks a strong quorum, so this experiment isolates the benefit of speculative execution. Without it, the No-Diss-No-Spec and No-Spec variants yield zero speculative throughput during the interval in which 𝑓 +1 replicas are partitioned (24s to 32s). The dissemination layer’s benefits appear only once a strongly connected component exists, since by then transactions are already available for ordering.

Conference’17, July 2017, Washington, DC, USA

Shaokang Xie, Dakai Kang, Junchao Chen, Suyash Gupta, Daniel P. Hughes, and Mohammad Sadoghi

Latency Breakdown. Next, we dissect Cassandra’s latency to understand where it actually spends time. Roughly 70% of Cassandra’s latency goes to forming a PoR certificate—which requires collecting votes and disseminating the certificate—and to committing, which entails forming two consecutive PoRs. Proposal dissemination and execution each contribute 10%, strongest-proposal election 6%, cryptography only 1%, and other overheads 3%. Thus, cryptography and proposal selection are not the bottleneck; latency is dominated by the commit path and by communication and certificate coordination.

7.6

Geo-Distributed Regional Partition

Finally, in Figure 12(h), we study the impact of deploying replicas in a geo-distributed setting: we deploy 𝑛 = 31 replicas across four regions, with regional group sizes of 8/8/8/7. The experiment follows the path: normal connectivity → 𝑓 partitioned replicas → 𝑓 +1 partitioned replicas → 𝑓 partitioned replicas → recovery. We distribute the 𝑓 partitioned replicas across the four regions as 1/1/1/6, and the 𝑓 +1 partitioned replicas as 1/1/1/7, which renders one full region unavailable. WAN latency, bandwidth heterogeneity, and cross-region quorum communication reduce throughput and increase latency for all protocols, but the qualitative behavior matches the partition results above. During the 𝑓 -partitioned phase, a quorum of 2𝑓 +1 replicas remains available, so all protocols continue committing proposals, albeit with a decrease similar to that in §7.3.1. During the 𝑓 +1partitioned phase, all protocols except Cassandra are unable to commit any blocks, whereas Cassandra continues to speculatively execute blocks. After reconnection, cross-region quorum paths are restored and all protocols return to their steady-state performance.

Related Work

The design of Cassandra draws inspiration from and builds upon several decades of research in BFT consensus. We categorize the most relevant literature into four primary domains: partition-tolerant consensus, sharding protocols, asynchronous BFT, and view synchronization. Network Partition. The challenge of maintaining consistency and availability under network partitions is fundamentally tied to the CAP theorem. Traditional BFT protocols typically prioritize safety and stall indefinitely when a strong quorum (2𝑓 +1) cannot be assembled. Partitionable Blockchain Consensus [27] was among the first to formalize this problem. It proves impossibility in a fully asynchronous model, then leverages external partition detectors to coordinate the partition. Raptr [49] introduces prefix consensus: replicas maintain safety by finalizing only the common transaction prefix. Then it reconciles divergent suffixes upon restoration. More recently, AutoBahn [20] preserves a limited form of partial progress under network disruptions, but this progress is largely confined to the dissemination layer rather than the ordering layer, and thus does not directly address designated-leader dependence. In contrast to these approaches, Cassandra neither relies on external partition detectors nor confines partial progress to data dissemination alone. Instead, its core ordering path allows partitions to independently order transactions that are later integrated through an implicit merge method.

View Synchronization. View synchronization is fundamental for aligning replicas within a common round to ensure sustained consensus progress. While classic protocols like PBFT [10] utilize an exponential back-off strategy for eventual convergence, HotStuff [51] decouples this logic into a dedicated pacemaker. Building on this modularity, state-of-the-art mechanisms have evolved to address the quadratic communication overhead inherent in traditional designs. Notable advancements include Lewis-Pye’s hierarchical, epoch-based framework [36, 37], which achieves amortized 𝑂 (𝑛) communication complexity, and Lumiere [38], which further optimizes steady-state performance with optimistic responsiveness. While these advancements significantly enhance steady-state performance, they remain fundamentally dependent on a 2𝑓 +1 strong quorum of “new-view” messages to transition between rounds, leading to total system stalls during network partitions. Cassandra fills this operational void by introducing a novel pacemaker that facilitates round advancement through the evidence from 𝑓 +1 replicas, thereby sustaining partial progress where other state-of-the-art pacemakers fail to coordinate. Dual-Path Design BFT. A common theme in practical BFT systems is to expose an optimistic fast path that achieves low latency and linear communication when the network is stable and the active leader is responsive, while retaining a fallback path that preserves safety under faults and delays. Prior dual-path BFT protocols [21, 35, 42] achieve low latency via an optimistic fast path but typically remain leader-driven in the common case and rely on leader-based recovery to fall back under adverse conditions. DAG-based designs such as Bullshark [46] similarly incorporate a predefined leader in the synchronous path, while relying on a random coin to select a fallback leader for global convergence. In contrast, although Cassandra also employs a coin, it is used only as a tie-breaker when multiple proposals remain indistinguishable under the deterministic priority rule, rather than as a mechanism for leader election or round synchronization. As a result, Cassandra removes designated-leader (and coin-driven leaderelection) dependence from its core ordering path via partitionable leader selection and deterministic proposal priority, enabling components to continue making order-relevant partial progress even when global leader reachability or coin-driven coordination becomes ineffective under partitions. Sharding Protocols. Sharded systems aim to improve scalability by partitioning replicas into smaller committees that process disjoint subsets of state or transactions in parallel. Early systems such as Chainspace [3] explored object-centric sharding with BFT committees and atomic object locking. Building on this, OmniLedger [34] utilized secure randomness for epoch-based committee assignment, while RapidChain [52] pipelines block production across shards. Cerberus [25] further evolved this by employing per-shard DAGs to eliminate single-leader bottlenecks. Extending this line of work, ByShard [26] optimizes this paradigm by introducing a sharded database framework that efficiently integrates BFT consensus with atomic cross-shard coordination. RCanopus [33] geographically divides replicas into Byzantine Groups (BGs) that run local BFT, while a super-consensus orders the BG outputs. While these systems significantly improve horizontal scalability, they still inherently stall if fewer than 2𝑓 +1 replicas remain in a

Cassandra : Consensus with Partial Progress via Robust Partitionable View Synchronization

shard after a partition. Cassandra ’s partial-progress technique is orthogonal. It could serve as an intra-shard consensus component, allowing each committee to process local transactions with nonzero throughput even when a partition leaves only 𝑓 +1 honest replicas connected. Concurrent and Multi-Leader BFT. Recent work [8, 23, 30, 39–41, 47, 48] has also explored allowing multiple replicas to concurrently drive consensus, which helps reduce the bottleneck of a single designated leader under stable conditions. At a high level, this design may appear to mitigate leader dependence, since progress is no longer tied to one pre-assigned proposer. However, these protocols still require global coordination to reconcile concurrent proposals and remain constrained by the strong quorum dependence. While they improve steady-state throughput, they do not directly address the partition setting considered in Cassandra: failing to make useful progress during network partitions. Asynchronous Protocols. Fully asynchronous protocols, such as HoneyBadgerBFT [43] and BEAT [16], eliminate timing assumptions by combining reliable broadcast with threshold cryptography. Recent advancements in DAG-based BFT, including DAG-Rider [32] and Tusk [15], further optimize performance by decoupling data dissemination from ordering, achieving optimal resilience and amortized 𝑂 (𝑛 2 ) complexity. Fides [50] further enhances this model by offloading critical operations into trusted hardware for an optimized threshold and better performance. Despite their resilience to asynchrony, these protocols remain bound by the Strong Quorum Dependence: none can make progress once fewer than a quorum of replicas are reachable, since they still require a classical quorum to form certificates. In contrast, Cassandra addresses this by allowing a weaker quorum to construct weaker certificates, achieving non-zero progress during weak quorums—a breakthrough from 0 to 1.

Conclusion

We presented Cassandra, a BFT protocol that breaks the all-ornothing progress model of traditional consensus by enabling partial, safety-preserving progress even when no strong quorum is reachable. Cassandra achieves this through three key design ideas: a two-tier certification framework that decouples partial progress (via weak-quorum) from final commitment (via strong-quorum), a deterministic proposal-priority rule that allows any connected component of 𝑓 +1 correct replicas to select a non-predefined leader and advance ordering independently, and a decoupled pacemaker that drives round progression via certificates rather than synchronized timeouts. Together, these mechanisms enable isolated partitions to accumulate useful ordering progress that is implicitly reconciled once the network heals, eliminating the need for an explicit recovery protocol. Our evaluation shows that Cassandra remains competitive with state-of-the-art BFT protocols under stable conditions, while delivering continuous partial throughput during partitions and reducing wasted work upon reconnection.

Acknowledgements

This work is partially funded by NSF Award Number 2245373.

Conference’17, July 2017, Washington, DC, USA

References [1] [n. d.]. Cassandra: Consensus with Partial Progress via Robust Partitionable View Synchronization (Extended Version). https://github.com/apache/incubatorresilientdb/blob/cassandra/Cassandra_extended.pdf. [2] [n. d.]. Cassandra Source Code. https://github.com/apache/incubator-resilientdb/ tree/cassandra. [3] Mustafa Al-Bassam, Alberto Sonnino, Shehar Bano, Dave Hrycyszyn, Sarah Meiklejohn, and George Danezis. 2018. Chainspace: A Sharded Smart Contracts Platform. In NDSS. [4] Ahmed Alquraan, Hatem Takruri, Mohammed Alfatafta, and Samer Al-Kiswany. 2018. An Analysis of Network-Partitioning Failures in Cloud Systems. In USENIX OSDI. 51–68. [5] Amazon Web Services. 2025. Summary of the Amazon DynamoDB Service Disruption in the Northern Virginia (US-EAST-1) Region. https://aws.amazon. com/message/101925/. (Accessed: 07-01-2026). [6] Apache ResilientDB. [n. d.]. Apache ResilientDB (Incubating). https://resilientdb. apache.org/. [7] Maria Apostolaki, Aviv Zohar, and Laurent Vanbever. 2017. Hijacking Bitcoin: Routing Attacks on Cryptocurrencies. In 2017 IEEE Symposium on Security and Privacy (SP). IEEE, 375–392. doi:10.1109/SP.2017.29 [8] Balaji Arun and Binoy Ravindran. 2022. Scalable Byzantine Fault Tolerance via Partial Decentralization. In PVLDB. [9] Eric A. Brewer. 2000. Towards Robust Distributed Systems. In ACM PODC. [10] Miguel Castro and Barbara Liskov. 1999. Practical Byzantine Fault Tolerance. In USENIX OSDI. 173–186. [11] Miguel Castro and Barbara Liskov. 2002. Practical Byzantine Fault Tolerance and Proactive Recovery. In ACM Transactions on Computer Systems. 398–461. [12] Cloudflare. 2025. Cloudflare outage on December 5, 2025. https://blog.cloudflare. com/5-december-2025-outage/. Accessed: 07-01-2026. [13] Cloudflare. 2025. Cloudflare outage on November 18, 2025. https://blog.cloudflare. com/18-november-2025-outage. Accessed: 07-01-2026. [14] Cryptonary. 2021. Solana Network Went Down Again; Mainnet Beta Restarts After 7 Hours of Outage. In Online resource. [15] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Narwhal and Tusk: A DAG-Based Mempool and Efficient BFT Consensus. In ACM EuroSys. [16] Sisi Duan, Michael K. Reiter, and Haibin Zhang. 2018. BEAT: Asynchronous BFT Made Practical. In ACM CCS. [17] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the Presence of Partial Synchrony. In Journal of the ACM. 288–323. [18] Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. 1999. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. In EUROCRYPT. 295–310. [19] Seth Gilbert and Nancy Lynch. 2012. Perspectives on the CAP Theorem. In IEEE Computer. [20] Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. 2024. AutoBahn: Seamless High Speed BFT. In ACM SOSP. [21] Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019. SBFT: A Scalable and Decentralized Trust Infrastructure. In IEEE DSN. [22] Suyash Gupta, Jelle Hellings, and Mohammad Sadoghi. 2021. Fault-Tolerant Distributed Transactions on Blockchain. In Synthesis Lectures on Data Management. [23] Suyash Gupta, Jelle Hellings, and Mohammad Sadoghi. 2021. RCC: Resilient Concurrent Consensus for High-Throughput Secure Transaction Processing. In IEEE ICDE. [24] Suyash Gupta, Sajjad Rahnama, Jelle Hellings, and Mohammad Sadoghi. 2020. ResilientDB: Global Scale Resilient Blockchain Fabric. In PVLDB. 868–883. [25] Jelle Hellings, Daniel P. Hughes, Joshua Primero, and Mohammad Sadoghi. 2023. Cerberus: Minimalistic Multi-Shard Byzantine-Resilient Transaction Processing. In Journal of Systems Research. [26] Jelle Hellings and Mohammad Sadoghi. 2021. ByShard: Sharding in a Byzantine Environment. In PVLDB. [27] Kendric Hood, Joseph Oglio, Mikhail Nesterenko, and Gokarna Sharma. 2021. Partitionable Asynchronous Cryptocurrency Blockchain. In IEEE ICBC. [28] Van Jacobson. 1988. Congestion Avoidance and Control. In ACM SIGCOMM. [29] Dakai Kang, Suyash Gupta, Dahlia Malkhi, and Mohammad Sadoghi. 2025. HotStuff-1: Linear Consensus with One-Phase Speculation. In SIGMOD. [30] Dakai Kang, Sajjad Rahnama, Jelle Hellings, and Mohammad Sadoghi. 2024. SpotLess: Concurrent Rotational Consensus Made Practical Through Rapid View Synchronization. In IEEE ICDE. [31] Jonathan Katz and Yehuda Lindell. 2014. Introduction to Modern Cryptography (2nd Edition). In Chapman and Hall/CRC. [32] Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021. All You Need is DAG. In ACM PODC. [33] S. Keshav, W. Golab, B. Wong, S. Rizvi, and S. Gorbunov. 2018. RCanopus: Making Canopus Resilient to Failures and Byzantine Faults. In arXiv preprint arXiv:1810.09300.

Conference’17, July 2017, Washington, DC, USA

Shaokang Xie, Dakai Kang, Junchao Chen, Suyash Gupta, Daniel P. Hughes, and Mohammad Sadoghi

[34] Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ismail Khoffi, Lars M. Fischer, and Bryan Ford. 2018. OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding. In IEEE S&P. [35] Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. 2007. Zyzzyva: Speculative Byzantine Fault Tolerance. In ACM SOSP. [36] Andrew Lewis-Pye. 2022. Quadratic Worst-Case Message Complexity for State Machine Replication in the Partial Synchrony Model. In arXiv preprint arXiv:2201.01107. [37] Andrew Lewis-Pye and Ittai Abraham. 2023. Fever: Optimal Responsive View Synchronisation. In arXiv preprint arXiv:2301.09881. [38] Andrew Lewis-Pye, Dahlia Malkhi, Oded Naor, and Kartik Nayak. 2024. Lumiere: Making Optimal BFT for Partial Synchrony Practical. In ACM PODC. [39] Hanzheng Lyu, Shaokang Xie, Jianyu Niu, Ivan Beschastnikh, Yinqian Zhang, Mohammad Sadoghi, and Chen Feng. 2025. Orthrus: Accelerating Multi-BFT Consensus Through Concurrent Partial Ordering of Transactions. In IEEE ICDE. [40] Hanzheng Lyu, Shaokang Xie, Jianyu Niu, Chen Feng, Yinqian Zhang, and Ivan Beschastnikh. 2025. Ladon: High-Performance Multi-BFT Consensus via Dynamic Global Ordering. In ACM EuroSys. [41] Hanzheng Lyu, Shaokang Xie, Jianyu Niu, Mohammad Sadoghi, Yinqian Zhang, Cong Wang, Ivan Beschastnikh, and Chen Feng. 2025. HYDRA: Breaking the Global Ordering Barrier in Multi-BFT Consensus. In arXiv preprint arXiv:2511.05843. [42] Jean-Philippe Martin and Lorenzo Alvisi. 2005. Fast Byzantine Consensus. In IEEE DSN. [43] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. 2016. The Honey Badger of BFT Protocols. In ACM CCS. [44] Torben P. Pedersen. 1991. A Threshold Cryptosystem without a Trusted Party. In EUROCRYPT. 522–526. [45] Mohammad Sadoghi. 2025. The Problems of Consensus: An Ethical Inquiry into Democratic and Decentralized Principles. In SpringerBriefs in Philosophy. [46] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris KokorisKogias. 2022. Bullshark: DAG BFT Protocols Made Practical. In ACM CCS. [47] Chrysoula Stathakopoulou, Tudor David, Matej Pavlovic, and Marko Vukolic. 2022. Mir-BFT: Scalable and Robust BFT for Decentralized Networks. In Journal of Systems Research. [48] Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolic. 2022. State Machine Replication Scalability Made Simple. In ACM EuroSys. [49] Andrei Tonkikh, Balaji Arun, Zhuolun Xiang, Zekun Li, and Alexander Spiegelman. 2025. Raptr: Prefix Consensus for Robust High-Performance BFT. In arXiv preprint arXiv:2504.18649. [50] Shaokang Xie, Dakai Kang, Hanzheng Lyu, Jianyu Niu, and Mohammad Sadoghi. 2025. Fides: Secure and Scalable Asynchronous DAG Consensus via Trusted Components. In arXiv preprint arXiv:2501.01062. [51] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In ACM PODC. [52] Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. 2018. RapidChain: Scaling Blockchain via Full Sharding. In ACM CCS.

Cassandra : Consensus with Partial Progress via Robust Partitionable View Synchronization

Correctness Proof

This section provides the full proofs of Theorems 1, 2, and 3.

A.1

Safety

We assume a Byzantine fault model with 𝑛 = 3𝑓 +1 replicas, where at most 𝑓 replicas are Byzantine. A strong quorum requires 𝑄 = 2𝑓 +1 votes, and a weak quorum requires 𝑄 weak = 𝑓 +1 votes. We say two proposals conflict if neither is an ancestor of the other. Lemma 1 (Quorum Intersection). Any two strong quorums of size 2𝑓 +1 intersect in at least 𝑓 +1 replicas; in particular, they share at least one correct replica. Proof. Let 𝑄 1 and 𝑄 2 be two strong quorums with |𝑄 1 | = |𝑄 2 | = 2𝑓 +1. Since 𝑛 = 3𝑓 +1, |𝑄 1 ∩ 𝑄 2 | ≥ |𝑄 1 | + |𝑄 2 | − 𝑛 = (2𝑓 +1) + (2𝑓 +1) − (3𝑓 +1) = 𝑓 +1. As at most 𝑓 replicas are Byzantine, 𝑄 1 ∩ 𝑄 2 contains at least one correct replica. □ Lemma 2 (No Double Vote). A correct replica votes for at most one proposal in a given round. Proof. Correct replicas follow the protocol. In each round 𝑟 , a correct replica selects a single candidate proposal according to the priority rule and broadcasts Vote messages for exactly that proposal. □ Lemma 3 (PoR Uniqeness). For any round 𝑟 , there cannot exist two valid PoR certificates that certify conflicting proposals. Proof. Assume for contradiction that there exist two valid PoRs in round 𝑟 certifying conflicting proposals 𝑏 and 𝑏 ′ . Each PoR requires 2𝑓 +1 votes. By Lemma 1, the two voter sets intersect in at least one correct replica. That replica would have voted for both 𝑏 and 𝑏 ′ in round 𝑟 , contradicting Lemma 2. □ Lemma 4 (Lock Monotonicity). For any correct replica 𝑝𝑖 , its lock 𝑙𝑜𝑐𝑘𝑖 is monotonically non-decreasing in round number. Moreover, once 𝑝𝑖 observes a PoR for a proposal, it locks that proposal and will not vote for any conflicting proposal unless it later observes a strictly higher-round PoR on the competing proposal’s certified ancestry. Proof. Whenever 𝑝𝑖 observes a valid PoR𝑟 for proposal 𝑏𝑟 , it updates 𝑙𝑜𝑐𝑘𝑖 to 𝑏𝑟 unless it is already locked on a descendant of 𝑏𝑟 . Thus round(𝑙𝑜𝑐𝑘𝑖 ) can only increase over time. After locking, SafeToVote allows 𝑝𝑖 to vote only for a proposal that either (i) extends the current locked branch, or (ii) carries a strictly higher-round PoR that justifies switching. By protocol validity, any such higher-round PoR must lie on the proposal’s certified ancestry. Therefore, 𝑝𝑖 never votes for a conflicting proposal unless it has first observed higher certified evidence that justifies the switch. □ Lemma 5 (Commit Implies a Locked Set). If a proposal 𝑤 = 𝑏𝑟 is committed by the Two-PoR commit rule via a certified chain 𝑏𝑟 ← 𝑏𝑟 +1 with PoRs 𝑃𝑜𝑅𝑟 and 𝑃𝑜𝑅𝑟 +1 , then there exists a set 𝐿 of at least 𝑓 +1 correct replicas such that every replica in 𝐿 is locked on 𝑤 (or its descendants).

Conference’17, July 2017, Washington, DC, USA

Proof. Let 𝑄𝑟 +1 be the voter set that formed 𝑃𝑜𝑅𝑟 +1 for 𝑏𝑟 +1 . Since |𝑄𝑟 +1 | = 2𝑓 +1 and at most 𝑓 replicas are Byzantine, 𝑄𝑟 +1 contains at least 𝑓 +1 correct replicas; let 𝐿 be those correct voters. By protocol validity, a correct replica votes for 𝑏𝑟 +1 only after verifying that it extends 𝑏𝑟 and that its certified justification includes the parent certificate 𝑃𝑜𝑅𝑟 on 𝑏𝑟 (carried either directly as the round-entry certificate or as the highest justified PoR on 𝑏𝑟 +1 ’s certified ancestry). Hence, every replica in 𝐿 has observed 𝑃𝑜𝑅𝑟 before voting for 𝑏𝑟 +1 . By Lemma 4, each such replica locks on 𝑤 = 𝑏𝑟 (or a descendant on the same branch). □ Theorem 1 (Safety). No two correct replicas commit (finalize) conflicting proposals. Proof of Theorem 1. Assume for contradiction that two correct replicas commit conflicting proposals 𝑤 and 𝑏, with round(𝑤) < round(𝑏). Since 𝑤 is committed, by Lemma 5, there exists a set 𝐿 of at least 𝑓 +1 correct replicas locked on 𝑤 (or its descendants). Since 𝑏 is committed, there must exist at least one PoR that certifies a proposal conflicting with 𝑤 in some round after round(𝑤). Let 𝑃𝑜𝑅★ be the earliest such PoR, certifying a proposal 𝑥 ★ that conflicts with 𝑤, and let 𝑄 ★ be its voter set. Because |𝑄 ★ | = 2𝑓 +1 and |𝐿| = 𝑓 +1, we have |𝑄 ★ ∩ 𝐿| ≥ (2𝑓 +1) + (𝑓 +1) − (3𝑓 +1) = 1. Thus, 𝑄 ★ intersects 𝐿 in at least one correct replica 𝑝. Replica 𝑝 is locked on the branch of 𝑤. For 𝑝 to vote for 𝑥 ★, SafeToVote requires that 𝑥 ★ either extends 𝑝’s locked branch or carries a strictly higher-round PoR on 𝑥 ★’s certified ancestry that justifies switching. However, 𝑥 ★ conflicts with 𝑤, so it does not extend the locked branch. Moreover, any such higher-round PoR on 𝑥 ★’s ancestry would itself certify a conflicting proposal earlier than 𝑃𝑜𝑅★, contradicting the choice of 𝑃𝑜𝑅★ as the earliest conflicting PoR after 𝑤. Therefore, 𝑝 cannot vote for 𝑥 ★, contradicting 𝑝 ∈ 𝑄 ★. Hence, no two correct replicas can commit conflicting proposals. □

A.2

Liveness

Definition 1 (Timeout-Sufficient Replica). Fix a stabilized synchronous interval whose actual message delay bound is Δ. A correct replica 𝑝𝑖 is timeout-sufficient during that interval if its local timeout baseline satisfies 𝛿𝑖 ≥ Δ. Lemma 6 (Eventual Timeout Sufficiency). During any sufficiently long stabilized synchronous interval in which at least 2𝑓 +1 correct replicas are mutually connected, every correct replica eventually becomes timeout-sufficient. Proof. Fix such a stabilized synchronous interval with actual delay bound Δ. Consider any correct replica 𝑝𝑖 . If 𝑝𝑖 cannot yet collect enough ⟨SYNC-READY, 𝜈⟩ messages to locally form a synchronization certificate, it keeps retransmitting its ⟨SYNC-READY, 𝜈⟩ message. Since at least 2𝑓 +1 correct replicas are mutually connected and all messages among them are delivered within Δ, eventually every correct replica receives 2𝑓 +1 valid SyncReady messages for some synchronization view and forms a local ⟨SYNC-CERT, 𝜈⟩.

Conference’17, July 2017, Washington, DC, USA

Shaokang Xie, Dakai Kang, Junchao Chen, Suyash Gupta, Daniel P. Hughes, and Mohammad Sadoghi

If replica 𝑝𝑖 locally forms a synchronization certificate but does not receive certificates from at least 𝑓 +1 distinct replicas within time 𝛿𝑖 , it doubles its 𝛿𝑖 and retries in a higher synchronization view. Hence, as long as 𝛿𝑖 < Δ, repeated failures cause 𝛿𝑖 to grow exponentially. Once 𝛿𝑖 ≥ Δ, after 𝑝𝑖 forms its local synchronization certificate, every correct replica that is already in the same synchronization view can form and broadcast its own synchronization certificate within at most Δ, and that certificate is delivered back to 𝑝𝑖 within at most another Δ. Therefore, replica 𝑝𝑖 receives remote synchronization certificates from at least 𝑓 +1 distinct replicas within time 𝛿𝑖 , so the calibration attempt succeeds. Thus, after finitely many retries, every correct replica reaches a timeout baseline 𝛿𝑖 ≥ Δ and remains timeout-sufficient throughout the stabilized interval. □

Proof. Fix a good round 𝑟 . By Definition 2, by the end of the proposal-exchange window (𝐼 1 ∪ 𝐼 2 ), every correct replica has received every proposal broadcast by a correct replica in round 𝑟 . We assume that each replica accepts at most one proposal per author per round, ignoring additional proposals from the same author as equivocations. Hence, the number of candidate proposals considered in round 𝑟 is at most 𝑛. Let M𝑟 denote the set of proposals with maximum log strength under S(·) among the proposals received by a correct replica in round 𝑟 . If |M𝑟 | = 1, all correct replicas select the same strongest proposal and vote for it. Otherwise, ties are broken using the common coin C𝑟 for round 𝑟 . Since C𝑟 is obtained by threshold aggregation of 𝑓 +1 signature shares from 𝑓 +1 distinct replicas, all correct replicas compute the same C𝑟 . For each proposal P ∈ M𝑟 , replicas compute Score(P) = 𝐻 (C𝑟 ∥ P.proposer_id)

Definition 2 (Good round). A round 𝑟 is good if there exists a stabilized synchronous interval of length ≥ 3Δ, partitioned into three consecutive subintervals 𝐼 1 , 𝐼 2 , and 𝐼 3 each of length ≥ Δ, such that: (i) by the end of 𝐼 1 , all correct replicas have entered round 𝑟 and are timeout-sufficient; (ii) during 𝐼 1 ∪ 𝐼 2 , every proposal broadcast by a correct replica in round 𝑟 is delivered to every correct replica; and (iii) during 𝐼 3 , all correct replicas remain in round 𝑟 , and every vote broadcast by a correct replica in round 𝑟 is delivered to every correct replica. Lemma 7 (Good round exists). During any sufficiently long stabilized synchronous period, the pacemaker ensures that all correct replicas eventually synchronize their round counters and enter good rounds. Proof. Consider a stabilized synchronous period in which messages between correct replicas are delivered within Δ. By Lemma 6, after finitely many retries, every correct replica becomes timeoutsufficient. If any correct replica enters a higher round using a valid PoR or RC, it broadcasts that certificate. If a lagging correct replica has not yet seen the standalone certificate, it will still receive a valid higher-round proposal carrying the same certificate as its enterCert. In either case, within at most one message delay, every correct replica receives round-entry evidence for that higher round and can catch up. Moreover, when a lagging replica catches up to an already active round, it joins that round using only the remaining local waiting needed before entering the election phase, rather than restarting a full fresh round. Thus, during a sufficiently long stabilized synchronous period, the skew among correct replicas is continuously reduced, and there exists a round 𝑟 in which all correct replicas enter early enough to complete the proposal-exchange window (> 2Δ) and the election window (> Δ) together. Hence, round 𝑟 is good by Definition 2. As the stabilized synchronous period continues, the same argument applies repeatedly, so good rounds recur. □ Lemma 8 (PoR in a good round (probabilistic)). In any good round 𝑟 , honest replicas form a valid PoR for a single proposal with 2𝑓 +1 probability at least 𝑛 .

and select the proposal with the highest score. Consider the event that the highest score among the tied proposers corresponds to an honest proposer. Since proposer identities are fixed and C𝑟 is unpredictable to the adversary before round 𝑟 , the top-scoring proposer is uniformly distributed over the 𝑛 pro2𝑓 +1 posers, and is honest with probability 𝑛 . Conditioned on this event, all correct replicas select the same honest proposal. During the election window 𝐼 3 , all correct replicas broadcast their Votes, and by Definition 2, those votes are delivered to every correct replica within one message delay. Therefore, the selected proposal receives at least 2𝑓 +1 votes, allowing correct replicas to assemble a valid PoR in round 𝑟 . □ Theorem 2 (Liveness (with probability 1)). During any sufficiently long stabilized synchronous period, correct replicas commit new proposals continuously; over an unbounded sequence of such stabilized periods, commits occur infinitely often with probability 1. Proof of Theorem 2. Consider a sufficiently long stabilized synchronous period. By Lemma 6, sufficiently long stabilized synchronous periods first make all correct replicas timeout-sufficient; then, by Lemma 7, good rounds recur. In each good round, Lemma 8 implies that a PoR is formed with non-zero probability. Assuming fresh common-coin outputs across rounds, these perround success events occur with a fixed non-zero probability, so over an unbounded sequence of good rounds, PoRs occur infinitely often with probability 1. Whenever two consecutive rounds produce PoRs for proposals that extend one another, the Two-PoR commit rule commits the earlier proposal in the two-chain. Hence, during any sufficiently long stabilized synchronous period, correct replicas commit new proposals continuously; over an unbounded sequence of such stabilized periods, commits occur infinitely often with probability 1. □

A.3

Partial Liveness

Cassandra distinguishes between commitment (which requires strong quorums and PoRs) and partial progress (which preserves useful work and availability evidence during partitions). Lemma 9 (Weak Quorum Progress). In any connected component that contains at least 𝑄 weak = 𝑓 +1 honest replicas, whose

Cassandra : Consensus with Partial Progress via Robust Partitionable View Synchronization

internal message delays are bounded by Δ, and in which all participating correct replicas are timeout-sufficient (i.e., they have local timeout baselines satisfying 𝛿𝑖 ≥ Δ), the component can form at least one PoA in a round. Proof. Let C be a connected component containing 𝑘 ≥ 𝑓 +1 honest and timeout-sufficient replicas. Within C, all honest replicas receive each other’s proposals within the proposal-exchange window (> 2Δ). By applying the deterministic Priority Rule, these replicas converge on the same strongest candidate and broadcast votes for it during the subsequent election window (> Δ). Since |C| ≥ 𝑄 weak = 𝑓 +1, replicas are guaranteed to aggregate the required weak quorum of votes. Consequently, replicas in C can locally assemble a valid PoA. □ Lemma 10 (RC Progress in a Weak Component). In any connected component that contains at least 𝑄 weak = 𝑓 +1 honest replicas , the component can form a valid RC for round 𝑟 + 1. Proof. If no PoR is formed in round 𝑟 , then every correct replica in the component eventually reaches the election timeout for round 𝑟 and broadcasts a WishNewRound (𝑟 ) message. Since the component contains at least 𝑓 +1 honest replicas and those messages are eventually delivered (without strict timing guarantees), replicas in the component can collect at least 𝑓 +1 such messages. By the protocol rule for round synchronization, these messages form a valid RC for round 𝑟 + 1. □ Lemma 11 (Data Availability). If a proposal is certified by a PoA or a PoR, its data is available at at least one correct replica. Hence, any correct replica can lazily retrieve it via the catch-up mechanism when connectivity permits. Proof. A PoA or a PoR requires at least 𝑓 +1 votes, which guarantees that at least one correct replica has verified and stored the proposal. Hence, this certificate ensures that the proposal remains retrievable in the system. □ Theorem 3 (Partial Liveness). Cassandra satisfies the Partial Liveness property. Specifically, during network partitions, any connected component that contains at least 𝑓 +1 correct replicas and whose internal message delays are bounded by Δ, and whose correct replicas use local timeout baselines satisfying 𝛿𝑖 ≥ Δ, continues to advance rounds locally and produce PoA-certified partial progress. After network recovery, this accumulated partial progress remains recoverable and can be incorporated into subsequent PoR-backed commitment. Proof of Theorem 3. Let C be a connected component containing at least 𝑓 +1 correct and timeout-sufficient replicas and timely internal communication. By Lemma 9, in each local round, replicas in C can form a PoA for the strongest locally visible proposal, thereby preserving certified partial progress. If the component cannot form a strong certificate in that round, then by Lemma 10, the same replicas can still form an RC for the next round and continue advancing locally. Thus, even without a global strong quorum, C continues both to make round progress and to accumulate recoverable PoA-certified work. A PoA does not imply commitment, but by Lemma 11, it guarantees that the certified proposal remains available at some correct replica. Once global connectivity is restored and a strong quorum

Conference’17, July 2017, Washington, DC, USA

𝑄 = 2𝑓 +1 becomes reachable again, replicas exchange their local histories, compare the available branches via the deterministic priority rule, and resume forming PoRs on the strongest recoverable branch. The catch-up and back-fill mechanisms then retrieve and extend previously accumulated PoA-backed proposals on that branch, allowing the system to reincorporate partition-time partial progress into subsequent PoR-backed commitment. Therefore, Cassandra satisfies Partial Liveness. □

Record · ID 343450 · SHA-256 dda555ef4f90f842
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.