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 http://resolver.caltech.edu/CaltechAUTHORS:AWEfocs91
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:AWEfocs91
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|
|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.|
|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|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Kristin Buxton|
|Deposited On:||26 Aug 2008 23:49|
|Last Modified:||26 Dec 2012 10:15|
Repository Staff Only: item control page