Journal of the ACM Bibliography

Baruch Awerbuch and Leonard J. Schulman. The maintenance of common data in a distributed system. Journal of the ACM, 44(1):86-103, January 1997. [BibTeX entry]

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, with only polylogarithmic overhead in both time and communication complexities. Previous deterministic solutions required polynomial overhead in at least one of these measures.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: C.2.1 [Computer-Communication Networks]: Network Architecture and Design; C.2.2 [Computer-Communication Networks]: Network Protocols; C.2.4 [Computer-Communication Networks]: Distributed Systems; D.4.3 [Operating Systems]: File Systems Management; H.2.4 [Database Management]: Systems

General Terms: Algorithms, Databases

Additional Key Words and Phrases: Distributed computing, distributed databases, network management, network topology update, routing

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database