A Caltech Library Service

The maintenance of common data in a distributed system

Awerbuch, Baruch and Schulman, Leonard J. (1991) The maintenance of common data in a distributed system. In: Foundations of Computer Science, 32nd Annual Symposium. 1-4 Oct. 1991. IEEE , Piscataway, NJ, pp. 505-514. ISBN 0-8186-2445-0.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


A basic task in distributed computation is the maintenance at each processor of the network, of a current and accurate copy of a common database. A primary example is the maintenance, for routing and other purposes, of a record of the current topology of the system. Such a database must be updated in the wake of locally generated changes to its contents. Due to previous disconnections of parts of the network, a maintenance protocol may need to update processors holding widely varying versions of the database. We provide a deterministic protocol for this problem, which has only polylogarithmic overhead in its time and communication complexities. Previous deterministic solutions required polynomial overhead in at least one of these measures.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© Copyright 1991 IEEE. Reprinted with permission. Publication Date: 1-4 Oct. 1991. Supported by Air Force Contract TNDGAFOSR-86-0078, ARO contract DAAL03-86-K0171, NSF contract CCR8611442, and a special grant from IBM. Supported by an ONR Graduate Fellowship.
Funding AgencyGrant Number
Air Force Office of Scientific ResearchTNDGAFOSR-86-0078
Army Research OfficeDAAL03-86-K-0171
National Science FoundationCCR8611442
Office of Naval ResearchUNSPECIFIED
Subject Keywords:computational complexity; computer networks; database theory; distributed databases; protocols; software maintenance; common data maintenance; common database; communication complexity; deterministic protocol; distributed computation; distributed system; locally generated changes; maintenance protocol; polylogarithmic overhead; time complexity
Record Number:CaltechAUTHORS:AWEfocs91
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11499
Deposited On:26 Aug 2008 23:49
Last Modified:08 Nov 2021 22:00

Repository Staff Only: item control page