In the modern Internet, scalable and reliable storage mechanisms have become a requirement. Distributed Hash Tables provide scalable management of storage, but don?t support consistency of replicated mutable data. In this paper, we argue that replication is an intrinsic building block of computer-based systems and we present a formal model for specifying replication services that provide support for a range of consistency policies and take into account fault tolerance, liveness and application-specific data constraints. This unified model is general and expressive, permitting a better understanding of the space of possible consistency semantics and protocols, and facilitating the notion of a contract between a client and the service.

The model is applied to a multi-consistency replication system designed to be deployed on Distributed Hash Tables. We outline design choices in the replication layer, formally analyze the requirements for several consistency semantics, sketch the implementation and detail the application of the formal model to the eventual consistency protocol.