Journal of the Association for Computing Machinery, Vol. 44, No. 1, January 1997, pp. 86–103.

The Maintenance of Common Data in a Distributed System

BARUCH AWERBUCH

AND

LEONARD J. SCHULMAN

Abstract. 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.

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

Copyright 1997 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.