Distributed algorithms for dynamic replication of data

ABSTRACT

We present two distributed algorithms for dynamic replication of a data-item in communication networks. The algorithms are adaptive in the sense that they change the replication scheme of the item (i.e. the set of processors at which the data-item is replicated), as the read-write pattern of the processors in the network changes. Each algorithm continuously moves the replication scheme towards an optimal one, where optimality is defined with respect to different objective functions. One algorithm optimizes the communication cost objective function, and the other optimizes the communication time. We also provide a lower bound on the performance of any dynamic replication algorithm.

REFERENCES

• AE1: D. Agrawal , A. El Abbadi, Storage Efficient Replicated Databases, IEEE Transactions on Knowledge and Data Engineering, v.2 n.3, p.342-352, September 1990 [doi>10.1109/69.60797]
• AE2: D. Agrawal and A. E1 Abbadi, "Efficient Techniques for Replicated Data Management", Proc. of the Workshop on Management of Replicated Data, IEEE CS Press, 1990.
• ABG1: Rafael Alonso , Daniel Barbará , Hector Garcia-Molina , Soraya Abad, Quasi-Copies: Efficient Data Sharing for Information Retrieval Systems, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.443-468, March 14-18, 1988
• ABG2: Rafael Alonso , Daniel Barbara , Hector Garcia-Molina, Data caching issues in an information retrieval system, ACM Transactions on Database Systems (TODS), v.15 n.3, p.359-384, Sept. 1990 [doi>10.1145/88636.87848]
• B: L. Belady, "A Study of Page Replacement Algorithms for a Virtual Storage Computer", IBM Systems Journal, 5(2), 1966.
• BG: D. Barbara, H. Garcia Mohna, "The case for controlled inconsistency in replicated data," Proc. of the IEEE workshop on replicated data, 1990.
• BHG: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• BLS: A. Borodin , N. Linial , M. Saks, An optimal online algorithm for metrical task systems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.373-382, January 1987, New York, New York, United States [doi>10.1145/28395.28435]
• BS: D.L. Black and D. D. Sleator "Competitive Algorithms for Replication and Migration Problems", manuscript, 1989.
• CP: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• CL: M. Chrobak and L. L. Larmore "An Optimal Online Algorithm for k Servers on Trees", manuscript, 1990.
• DGS: Susan B. Davidson , Hector Garcia-Molina , Dale Skeen, Consistency in a partitioned network: a survey, ACM Computing Surveys (CSUR), v.17 n.3, p.341-370, Sept. 1985 [doi>10.1145/5505.5508]
• DF: Lawrence W. Dowdy , Derrell V. Foster, Comparative Models of the File Assignment Problem, ACM Computing Surveys (CSUR), v.14 n.2, p.287-313, June 1982 [doi>10.1145/356876.356883]
• E: A. E1 Abbadi, "Adaptive Protocols for Managing Replicated Distributed Databases", to appear in the Symposium on Parallel and Distributed Processing, 1991.
• GB: Hector Garcia-Molina , Daniel Barbara, How to assign votes in a distributed system, Journal of the ACM (JACM), v.32 n.4, p.841-860, Oct. 1985 [doi>10.1145/4221.4223]
• GS: Bezalel Gavish , Olivia R. Liu Sheng, Dynamic file migration in distributed computer systems, Communications of the ACM, v.33 n.2, p.177-189, Feb. 1990 [doi>10.1145/75577.75583]
• GZ: O. Gerstel and S. Zaks, "A New Characterization of Tree Medians with Applications to Distributed Algorithms", submitted to Networks.
• H: Maurice Herlihy, Dynamic quorum adjustment for partitioned data, ACM Transactions on Database Systems (TODS), v.12 n.2, p.170-194, June 1987 [doi>10.1145/22952.22953]
• KMRS: A. Karlin, M. Manasse, L. Rudolph, D. Sleator, "Competitive Snoopy Caching", Algorithmica, 3:1, 1988.
• KB: Narayanan Krishnakumar , Arthur J. Bernstein, Bounded ignorance in replicated systems, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.63-74, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113419]
• LLS: Rivka Ladin , Barbara Liskov , Liuba Shrira, A technique for constructing highly available services, Algorithmica, v.3 n.3, p.393-420, 1988
• J: C. Jordan, "Sur les assembblages des lignes", J. Reine Angew. Math., 70 1869.
• OV: M. Tamer Ozsu , P. Valduriez, Principles of distributed database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• ST: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• WM: Ouri Wolfson , Amir Milo, The multicast policy and its relationship to replicated data placement, ACM Transactions on Database Systems (TODS), v.16 n.1, p.181-205, March 1991 [doi>10.1145/103140.103146]
• Z: B. Zelinka, "Medians and Periphenans on Trees", Arch. Math. (Bmo), 1968.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Performance, Theory