SODA

CATS: linearizability and partition tolerance in scalable and self-organizing key-value stores

Arad, Cosmin and Shafaat, Tallat M. and Haridi, Seif (2012) CATS: linearizability and partition tolerance in scalable and self-organizing key-value stores. [SICS Report]

[img]
Preview
PDF
489Kb

Abstract

Distributed key-value stores provide scalable, fault-tolerant, and self-organizing storage services, but fall short of guaranteeing linearizable consistency in partially synchronous, lossy, partitionable, and dynamic networks, when data is distributed and replicated automatically by the principle of consistent hashing. This paper introduces consistent quorums as a solution for achieving atomic consistency. We present the design and implementation of CATS, a distributed key-value store which uses consistent quorums to guarantee linearizability and partition tolerance in such adverse and dynamic network conditions. CATS is scalable, elastic, and self-organizing; key properties for modern cloud storage middleware. Our system shows that consistency can be achieved with practical performance and modest throughput overhead (5%) for read-intensive workloads.

Item Type:SICS Report
Uncontrolled Keywords:atomic consistency, partition tolerance, scalability, self-organization,elasticity, fault tolerance, dynamic reconfiguration, distributed key-value stores
ID Code:5260
Deposited By:Vicki Carleson
Deposited On:28 May 2012 15:18
Last Modified:28 May 2012 15:18

Repository Staff Only: item control page