Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 1991 | Published
Book Section - Chapter Open

The maintenance of common data in a distributed system


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.

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.

Attached Files

Published - AWEfocs91.pdf


Files (781.0 kB)
Name Size Download all
781.0 kB Preview Download

Additional details

August 22, 2023
October 17, 2023