Eventually-serializable data services

Data replication is used in distributed systems to improve availability, in crease throughput and eliminate single points of failures. The cost of repl ication is that significant care and communication is required to maintain consistency among replicas. Tn some settings, such as distributed directory services, it is acceptable to have transient inconsistencies, in exhange f or better performance, as long as a consistent view of the data is eventual ly established. For such services to be usable, it is important that the co nsistency guarantees are specified clearly. We present a new specification for distributed data services that trades of f immediate consistency guarantees for improved system availability and eff iciency, while ensuring the long-term consistency of the data. An eventuall y-serializable data service maintains the requested operations in a partial order that gravitates over time towards a total order. It provides clear a nd unambiguous guarantees about the immediate and long-term behavior of the system. We also present an algorithm, based on the lazy, replication strategy of La din, Liskov, Shrira, and Ghemawat (1992), that implements this specificatio n. Our algorithm provides the external interface of the eventually-serializ able data service specification, and generalizes their algorithm by allowin g arbitrary operations and greater flexibility in specifying consistency re quirements. In addition to correctness, we prove performance and fault-tole rance properties of this algorithm. (C) 1999 Elsevier Science B.V. All righ ts reserved.