Serializability theory for replicated databases (Q1083230)

In a one-copy distributed database, each data item is stored at exactly one site of a distributed system. In a replicated database, some data items are stored at multiple sites. The main motivation for replicated data is improved reliability: by storing important data at multiple sites, the system can tolerate failures more gracefully. This paper presents a theory for proving the correctness of algorithms that manage replicated data. The theory is an extension of serializability theory. We use the theory to give simple correctness proofs for two replicated data algorithms: Gifford's ''quorum consensus'' algorithm, and Eager and Sevcik's ''missing writes'' algorithm.