The maintenance of common data in a distributed system

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.

REFERENCES

• 1: Baruch Awerbuch , Israel Cidon , Inder Gopal , Marc Kaplan , Shay Kutten, Distributed control for PARIS, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.145-159, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93412]
• 2: AWERBUCH, B., CIDON, I., AND KUTTEN, S. 1990b. Optimal maintenance of replicated information. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. IEEE, New York. pp. 472-502.
• 3: Baruch Awerbuch , Israel Cidon , Shay Kutten , Yishay Mansour , David Peleg, Broadcast with partial knowledge (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.153-163, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112614]
• 4: BARATZ, A. E., GRAY, J. P., GREEN JR., P. E., JAFFE, J. M., AND POZEFSKI, D. P. 1985. SNA networks of small systems. IEEE Sel. Areas Commun. SAC-3, 3 (May), 416-426.
• 5: CIDON, I., AND GOPAL, I.S. 1988. PARIS: An approach to integrated high-speed private networks. Int. J. Digital Anal. Cabled Syst. 1, 2 (April-June), 77-86.
• 6: KOLMOGOROV, A. N., AND TIHOMIROV, V.M. 1959/1961. Epsilon-entropy and epsilon-capacity of sets in functional spaces. Usp. Matemat. Nauk (N. S.) 14 (1959), 3-86. (Translated in Am. Math. Soc. Translations (Series 2) 17, (1961), 277-364.)
• 7: MANDELBROT, B. 1982. The Fractal Geometry of Nature. W. H. Freeman and Company, San Francisco, Calif.
• 8: McQUILLAN, J., RICHER, I., AND ROSEN, E. 1980. The new routing algorithm for the arpanet. IEEE Trans. Commun. 28, 5 (May), 711-719.
• 9: PONTRJAGIN, L., AND SCHNIRELMAN, L. 1932. Sur une propri6t6 m6trique de la dimension. Ann. Math. 33, 156-162.
• 10: WECKER, S. 1980. DNA: the digital network architecture. IEEE Trans. Commun. COM-28, (Apr.) 510-526.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Theory

Keywords:
distributed databases, distriubuted computing, network management, network topology update, routing