Data Replicas in Distributed Information Services

Abstract

In an information distribution network in which records are repeatedly read, it is cost-effective to keep read-only copies in work locations. This paper presents a method of updating replicas that need not be immediately synchronized with the source data or with each other. The method allows an arbitrary mapping from source records to replica records. It is fail-safe, maximizes workstation autonomy, and is well suited to a network with slow, unreliable, and/or expensive communications links. The algorithm is a manipulation of queries, which are represented as short encodings. When a response is generated, we record which portion of the source database was used. Later, when the source data are updated, this information is used to identify obsolete replicas. For each workstation, the identity of obsolete replicas is saved until a workstation process asks for this information. This workstation process deletes each obsolete replica, and replaces it by an up-to-date version either promptly or the next time the application asks for this particular item. Throughout, queries are grouped so that the impact of each source update transaction takes effect atomically at each workstation. Optimizations of the basic algorithm are outlined. These overlap change dissemination with user service, allow the mechanism to be hidden within the data delivery subsystem, and permit very large networks. © 1989, ACM. All rights reserved.