Orca: Flexible Quorums Meet Dynamic Quorums

Abstract

Large-scale data management systems rely on fault-tolerant protocols to ensure availability and consistency in the presence of node failures. However, standard protocols require majority quorums in every phase, making them impractical in environments with frequent failures, such as IoT networks. This paper presents Orca, a crash-fault-tolerant consensus protocol that integrates Raft-style log replication with Flexible Paxos quorum construction to maintain small replication quorums. Orca exploits the observation that node failures are often independent and temporally separated: by assuming that at most k nodes fail within a window too short for the system to detect the first failure, Orca fixes the replication quorum at k +1 nodes. As failures are detected, faulty nodes are temporarily excluded from the voting set and the election quorum is reduced accordingly, allowing the system to continue making progress as failures accumulate. Our evaluation across diverse workloads and fault scenarios demonstrates that Orca tolerates more failures than Raft and FlexiRaft while incurring negligible overhead.