An algorithm for concurrency control and recovery in replicated distributed databases

TLDR

In a distributed database, each data item is stored at one site, but replication stores items at multiple sites to improve reliability by allowing operation even when some sites fail. The paper proposes an algorithm that lets users operate on replicated data as long as at least one copy is available. A copy is considered available if its site is up and it is not stale due to a prior crash. The algorithm successfully handles clean, detectable site failures but does not address Byzantine failures or network partitions.

Abstract

In a one-copy distributed database, each data item is stored at exactly one site. In a replicated database, some data items may be stored at multiple sites. The main motivation is improved reliability: by storing important data at multiple sites, the DBS can operate even though some sites have failed. This paper describes an algorithm for handling replicated data, which allows users to operate on data so long as one copy is “available.” A copy is “available” when (i) its site is up, and (ii) the copy is not out-of-date because of an earlier crash. The algorithm handles clean, detectable site failures, but not Byzantine failures or network partitions.