CS Paper Radar

Eliminating Servers in State Machine Replication

Dohyun Park, Wenjie Hu, Xiangyao Yu, Mahesh Balakrishnan, Yongjoo Park

cs.DB cs.DC ·submitted 2026-11-01 00:01 UTC · v1

Abstract

State Machine Replication (SMR) underpins many stateful systems, including distributed databases, coordination services, and metadata stores. Fundamentally, SMR requires state to be materialized from a durable total order of commands. Existing SMR systems rely on servers to materialize, locally store, and serve snapshots of state; while the durable total order either resides on the same servers, or on an external, disaggregated shared log. Unfortunately, servers act as brittle, expensive choke-points in such systems, causing service unavailability when they fail; incurring provisioning latency on cold starts; and red-lining when exposed to bad clients. In this paper, we propose Serverless SMR (S^2MR), where both the materialized state and the durable total order are stored on disaggregated storage; clients concurrently maintain a single copy of materialized state on external storage. Our key technical insight is that the shared log abstraction is useful not just for consistently ordering commands in SMR, but also for enabling distributed materialization, thus becoming the only interface for ac hieving SMR. We demonstrate S^2MR by developing AirDB, a transactional key-value store. In our evaluation, AirD B over S^2MR achieves higher availability than existing SMR-based systems like etcd over Raft: it is oblivious to server failures and bad client activity; and spins up 10x-45x faster from a cold start.

Comment
14 pages including references, 9 figures, 2 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Pangolin: Efficient DAG-based BFT State-Machine Replication with TEE-Accelerated Commitment

cs.DC ·2026-10-19 ·Paul Franke-Bergmann, Maya Kuhlmann, Alexander Heß, Marc Leinweber, Rüdiger Kapitza +3 more
similarity 0.63
Abstract · 28 pages

Currently many Byzantine fault-tolerant (BFT) protocols use directed acyclic graphs (DAGs) to let replicas propose blocks of requests in parallel for improved throughput. Yet, the existing DAG-based designs mainly consider the atomic-broadcast layer: They typically do not describe an efficient client interaction layer, their garbage collection is either unspecified or relies on trusted external storage, and the lowest-latency designs rely on timing assumptions that may be violated in geo-distributed deployments. In this paper, we propose the Pangolin protocol: It introduces a novel low-latency DAG-based atomic broadcast layer and completes it into an efficient state-machine replication (SMR) framework. To preserve system throughput, clients issue requests to a single replica and verify replies efficiently via compact execution proofs. Furthermore, Pangolin introduces a new garbage-collection scheme for DAGs which bounds memory usage even under full asynchrony. Pangolin leverages trusted execution environments to tolerate f Byzantine faults with only n >= 2f + 1 replicas and accelerates vertex commitments significantly: Broadcasting certified vertices requires only a single communication step, and commit rules are refined to commit both frequently and early without revealing the coin-elected anchor. This way, Pangolin overtakes the fastest partially synchronous DAG protocols while being live under asynchrony: In our evaluation, Pangolin achieves an average 1.27x (up to 1.52x) latency speedup over Mysticeti.

0.23

SnapShare: Isolation-Preserving Deduplication for Serverless Snapshots

cs.DC ·2026-10-09 ·Leonid Kondrashov, Likun Zhang, André Filipe do Pilar de Jesus, Hans Pistor, Marco Cali +3 more
similarity 0.62
Abstract

The efficiency of serverless computing fundamentally depends on rapid function startup, a challenge increasingly addressed by restoring from virtual machine snapshots. However, because content deduplication techniques can open timing-channel attacks that leak sensitive tenant data, production platforms like AWS Lambda instead enforce strict, zero-sharing isolation between snapshots of different tenants. While secure, this isolation precludes the deduplication of common infrastructure components, wasting per-worker cache capacity and exacerbating cold-start latency through inefficient remote fetching. Our characterization reveals that non-sensitive, shareable infrastructure accounts for roughly 70% of a typical snapshot's contents and, on average, about 50% of its working set. We present SnapShare, a cluster-wide snapshot management system that co-designs storage and caching to exploit this commonality without compromising sensitive data isolation. SnapShare classifies a snapshot page as shareable only when its full content matches that of a page from a provider-approved source; any non-matching content is treated as isolated private content. Common infrastructure components are selectively deduplicated and pinned across the cluster's worker nodes, while private data remains strictly isolated and is eagerly fetched as part of the tracked working set, falling back to on-demand retrieval only for pages that fall outside it. Implemented as an extension to Knative, SnapShare reduces end-to-end tail request slowdowns by 10-29% compared to traditional working-set and chunk-based platforms. It also reduces remote storage requirements by 39% and local cache footprints by 38%, reducing network retrieval payloads and bounding worst-case fetch delays by 10x.

0.21

Generalizing and accelerating consistency checking for non-transactional distributed storage systems

cs.DC ·2026-08-18 ·Kotikala Raghav, Aman Hassan, Brian Sajeev Kattikat, Patel Jay, RSRS Santhosh +1 more
similarity 0.61
Abstract

Linearizability checkers check if an operation history, observed by concurrent clients, is linearizable. They are used in testing distributed storage systems, and use the classic Wing-Gong (WG) linearizability checking algorithm. In this paper, we generalize the WG algorithm to make linearizability checkers more versatile: we can check other non-transactional consistency guarantees, like ordered sequential consistency provided by Zookeeper. Equipped with this generalization, we can also check for system-specific consistency guarantees that introduce additional ordering constraints over operations in a history, as per the system's specification. Our experiments with 8 distributed storage systems show that checking for system-specific consistency guarantees is easy to realize, reduces false negatives in testing, helps debug consistency violations, can be up to 370x faster, and can scale to more concurrent clients within the same checking time budget. We report 6 new consistency violation bugs, out of which 5 could not be found with existing consistency checkers.

0.38

Ermes: a Stateful Serverless Platform for the Edge-to-Cloud Continuum

cs.DC ·2026-09-16 ·Matteo Cenzato, Dario d'Abate, Arianna Dragoni, Giacomo Orsenigo, Luca Tosetti +2 more
similarity 0.61
Abstract · Under revision at Future Generation Computer Systems (FGCS)

Function-as-a-Service (FaaS) is a widely adopted paradigm to simplify application deployment across the edge-to-cloud continuum. However, its stateless nature forces functions to retrieve their state from external, typically cloud-centric, data stores, reintroducing the very latency that edge computing aims to eliminate. This issue is further exacerbated by location-agnostic schedulers and rigid, one-size-fits-all consistency models that fail to capture the diverse requirements of edge applications. In this paper, we propose Ermes, a distributed platform that natively integrates state management into the FaaS paradigm, enabling the joint distribution of computational workloads and application state across the edge-to-cloud continuum. Ermes organizes application state into logical units, termed collections, and employs a distributed coordination algorithm that jointly maps collections and functions onto the available nodes seeking to minimize the latency perceived by the clients. In addition, it supports fine-grained replication and per-collection consistency levels, ranging from sequential to eventual consistency, leaving developers the choice of how to resolve the trade-off between consistency and performance. The experimental evaluation shows that Ermes quickly turns remote state accesses into local ones and sustains low latency as the workload grows, and as clients move across the edge.

0.14

Optimality and Trade-offs in Fast BFT SMR (Extended Version)

cs.DC ·2026-08-20 ·Neil Giridharan, Minh Tung Nguyen, Ittai Abraham, Allen Clement, Natacha Crooks +1 more
similarity 0.60
Abstract

Fast state-machine replication (SMR) protocols in the crash-fault setting have attracted significant interest in both academia and industry. This interest stems from their advantages over leader-based protocols, including low execution latency for non-conflicting commands, high throughput, improved availability, and increased fairness. While Fast SMR is well studied in the crash-fault setting, the Byzantine fault-tolerant (BFT) setting remains much less understood, with only a small number of existing Fast BFT SMR protocols. In this paper, we present tight upper and lower bounds on the replication factor required for Fast BFT SMR. We also present a suboptimal protocol that illustrates a trade-off between replication factor and recovery efficiency.

0.30

Optimizing Geo-replicated Deterministic Databases

cs.DB ·2026-11-04 ·Yunhao Mao, Shiquan Zhang, Gengrui Zhang, Hans-Arno Jacobsen
similarity 0.60
Abstract

In transactional databases, achieving active-active replication among geo-distributed replicas is challenging due to the high coordination cost in ensuring the serializability of concurrent cross-node transactions. Deterministic concurrency control (DCC) has emerged as a promising alternative: it establishes a global order for a batch of transactions before execution and thereby amortizes this coordination cost across the batch. To better understand the performance characteristics of DCC, we conduct a theoretical analysis of traditional two-phase locking and optimistic concurrency control to account for geo-replication and introduce a model for DCC. We compare the three paradigms and identify the conditions under which DCC is advantageous. Guided by the insights from this analysis, we then present Quirinus, a DCC-based geo-replicated database that optimizes transaction execution through speculative execution, transaction reordering, integration of conflict-free replicated data types (CRDTs), and fast-path commit. Even without these optimizations, Quirinus achieves up to 6.2x the TPC-C throughput of Tiga under our configuration.

0.15

Scalable datacenter replication with mostly-synchronous consensus on hardware

cs.DC ·2026-08-25 ·Davide Rovelli, Philipp Berdesinski, Rodrigo Otoni, Patrick Eugster
similarity 0.60
Abstract

Consistent replication of data among distributed processes -- a task involving the well-known consensus problem -- is notoriously expensive and hard to scale, affecting especially datacenter services with stringent performance requirements. To mitigate this problem, we introduce scalable replication in-hardware ( scarHW ): a network card design that improves throughput and latency of consistent replication even when increasing the number of replicas, whereas current systems operate at a small scale or with relaxed consistency guarantees. At the heart of scarHW is our novel POPUC consensus algorithm, implemented in an FPGA smartNIC to take full advantage of the "mostly synchronous" behavior of programmable network devices in the datacenter. Unlike widely-adopted "mostly asynchronous" coordination protocols such as Paxos or leaderless alternatives, POPUC implements a generalized variant of consensus dubbed collaborative consensus which allows for several simultaneous decisions, achieving great scalability without compromising availability. POPUC preserves safety guarantees in the presence of process crash-stop and message send/receive omission failures (capturing incidental asynchrony) and has been formally specified and verified in TLA+. Our FPGA prototype improves throughput and latency of widely-used services Redis and Zookeeper by up to two orders of magnitude compared to the state of the art. scarHW-based services also achieve zero downtime upon failure of a minority of replicas, offering a highly-robust, wire-speed, scalable replication system.

0.10

A Deterministic Commitment Rule over Unstructured DAGs for Optimistic Replication

cs.DC ·2026-10-30 ·João Paulo Bezerra, Petr Kuznetsov, Léo Olivier, Sara Tucci-Piergiovanni
similarity 0.59
Abstract

In optimistic replication protocols, each replica uses the local state to execute requests from its clients in a wait-free manner, without synchronizing with other replicas. The outcomes may be revised later, making optimistic protocols only eventually consistent. To compensate for this consistency loss, an additional commitment mechanism can be employed: an underlying atomic broadcast protocol that allows replicas to periodically agree on the evolution of the object state. In this paper, we introduce a simple framework for optimistic replication based on a causality DAG: every replica represents the object state via a causally ordered set of client operations. The framework incorporates a deterministic commitment rule that incurs virtually zero message overhead beyond the basic dissemination of submitted operations.

0.22