Serializability theory for replicated databases
type: Item
instance of: scholarly article
title: Serializability theory for replicated databases
zbMATH Open document ID: 0604.68108
DOI: 10.1016/0022-0000(85)90058-3
author: Philip A. Bernstein
author: Nathan Goodman
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P20
zbMATH DE Number: 3976394
zbMATH Keywords: distributed database
zbMATH Keywords: correctness proofs
zbMATH Keywords: replicated data algorithms
describes a project that uses: INGRES
MaRDI profile type: Publication
full work available at URL: 0022-0000(85)90058-3
OpenAlex ID: W1966089826
cites work: Multiversion concurrency control—theory and algorithms
cites work: Formal Aspects of Serializability in Database Concurrency Control
cites work: The Byzantine generals strike again
cites work: The notions of consistency and predicate locks in a database system
cites work: Q4198056
cites work: Time, clocks, and the ordering of events in a distributed system
cites work: The serializability of concurrent database updates
cites work: Reaching Agreement in the Presence of Faults
cites work: Concurrency Control and Consistency of Multiple Copies of Data in Distributed Ingres
cites work: Consistency in Hierarchical Database Systems
cites work: Transactions and consistency in distributed database systems
description: scientific article; zbMATH DE number 3976394