2017/10/26 by Seo Jin Park, Park, Seo Jin, John K. Ousterhout +1 · 2 citations
Computer Science · Engineering · #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Operating Systems (cs.OS) #Parallel #Parallel Computing and Optimization Techniques #Radiation Effects in Electronics #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1710.09921
openalex publication_date 2017/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Traditional approaches to replication require client requests to be ordered before making them durable by copying them to replicas. As a result, clients must wait for two round-trip times (RTTs) before updates complete. In this paper, we show that this entanglement of ordering and durability is unnecessary for strong consistency. Consistent Unordered Replication Protocol (CURP) allows clients to replicate requests that have not yet been ordered, as long as they are commutative. This strategy allows most operations to complete in 1 RTT (the same as an unreplicated system). We implemented CURP in the Redis and RAMCloud storage systems. In RAMCloud, CURP improved write latency by ~2x (13.8 us -> 7.3 us) and write throughput by 4x. Compared to unreplicated RAMCloud, CURP's latency overhead for 3-way replication is just 0.4 us (6.9 us vs 7.3 us). CURP transformed a non-durable Redis cache into a consistent and durable storage system with only a small performance overhead.