Leveraging sharding in the design of scalable replication protocols - Abu-Libdeh, Hussam; Renesse, Robbert van; Vigfusson, Ymir (SOCC '13: Proceedings of the 4th annual Symposium on Cloud Computing, 2013)
Most if not all datacenter services use sharding and replication for scalability and reliability. Shards are more-or-less independent of one another and individually replicated. In this paper, we challenge this design philosophy and present a replication protocol where the shards interact with one another: A protocol running within shards ensures linearizable consistency, while the shards interact in order to improve availability. We provide a specification for the protocol, prove its safety, analyze its liveness and availability properties, and evaluate a working implementation.