THE MAINTENANCE OF COMMON DATA IN A DISTRIBUTED SYSTEM

A basic task in distributed computation is the maintenance at each pro cessor of the network, of a current and accurate copy of a common data base. A primary example is the maintenance, for routing and other purp oses, of a record of the current topology of the system. Such a databa se must be updated in the wake of locally generated changes to its con tents. Due to previous disconnections of parts of the network, a maint enance protocol may need to update processors holding widely varying v ersions of the database. We provide a deterministic protocol for this problem, with only polylogarithmic overhead in both time and communica tion complexities. Previous deterministic solutions required polynomia l overhead in at least one of these measures.