Access Restriction

Author Awerbuch, Baruch ♦ Schulman, Leonard J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1997
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Distributed databases ♦ Distriubuted computing ♦ Network management ♦ Network topology update ♦ Routing
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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1997-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 44
Issue Number 1
Page Count 18
Starting Page 86
Ending Page 103

Open content in new tab

   Open content in new tab
Source: ACM Digital Library