Data replication for mobile computers

ABSTRACT

Users of mobile computers will soon have online access to a large number of databases via wireless networks. Because of limited bandwidth, wireless communication is more expensive than wire communication. In this paper we present and analyze various static and dynamic data allocation methods. The objective is to optimize the communication cost between a mobile computer and the stationary computer that stores the online database. Analysis is performed in two cost models. One is connection (or time) based, as in cellular telephones, where the user is charged per minute of connection. The other is message based, as in packet radio networks, where the user is charged per message. Our analysis addresses both, the average case and the worst case for determining the best allocation method.

REFERENCES

• 1: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• 2: A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, Proceedings of the 15th Annual International Symposium on Computer architecture, p.280-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 3: Mustaque Ahamad , Mostafa H. Ammar , Shun Yan Cheung, Multidimensional voting, ACM Transactions on Computer Systems (TOCS), v.9 n.4, p.399-431, Nov. 1991 [doi>10.1145/118544.118552]
• 4: R. Alonso and S. Ganguly, "Query Optimization for Energy Efficiency in Mobile Enviroments', Proc. of the 1993 Inl'l Workshop on Foundalzons of Models and Languages for Data and Objects, Aigen, Austria
• 5: D. Agrawal , A. El Abbadi, The tree quorum protocol: an efficient approach for managing replicated data, Proceedings of the sixteenth international conference on Very large databases, p.243-254, September 1990, Brisbane, Australia
• 6: John K. Bennett , John B. Carter , Willy Zwaenepoel, Adaptive software cache management for distributed shared memory architectures, Proceedings of the 17th annual international symposium on Computer Architecture, p.125-134, May 28-31, 1990, Seattle, Washington, United States
• 7: J. K. Bennett , J. B. Carter , W. Zwaenepoel, Munin: distributed shared memory based on type-specific memory coherence, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.168-176, March 14-16, 1990, Seattle, Washington, United States
• 8: Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.39-50, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129717]
• 9: B. R. Badrinath and T. Imielinski, "Replication and Mobility", Proc. of the 2nd Workshop on the Management of Rephcated Data (WMRD-II), pp. 9-12, Monterey, CA.
• 10: Shun Yan Cheung , Mostafa H. Ammar , Mustaque Ahamad, The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data, Proceedings of the Sixth International Conference on Data Engineering, p.438-445, February 05-09, 1990
• 11: Michael J. Carey , Michael J. Franklin , Miron Livny , Eugene J. Shekita, Data caching tradeoffs in client-server DBMS architectures, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.357-366, May 29-31, 1991, Denver, Colorado, United States
• 12: Michael J. Carey , Miron Livny, Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication, Proceedings of the 14th International Conference on Very Large Data Bases, p.13-25, August 29-September 01, 1988
• 13: 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]
• 14: S. J. Eggers , R. H. Katz, A characterization of sharing in parallel programs and its application to coherency protocol evaluation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.373-382, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 15: S. J. Eggers , R. H. Katz, Evaluating the performance of four snooping cache coherency protocols, Proceedings of the 16th annual international symposium on Computer architecture, p.2-15, April 1989, Jerusalem, Israel
• 16: Derek L. Eager , Kenneth C. Sevcik, Achieving robustness in distributed database systems, ACM Transactions on Database Systems (TODS), v.8 n.3, p.354-381, Sept. 1983 [doi>10.1145/319989.319992]
• 17: Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
• 18: S. Ganguly and 1%. Alonso, "Query Optimization in Mobile Enviroments", Technical Report, December 1993
• 19: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 20: Yixiu Huang , Ouri Wolfson, A Competitive Dynamic Data Replication Algorithm, Proceedings of the Ninth International Conference on Data Engineering, p.310-317, April 19-23, 1993
• 21: Yixiu Huang , Ouri Wolfson, Object Allocation in Distributed Databases and Mobile Computers, Proceedings of the Tenth International Conference on Data Engineering, p.20-29, February 14-18, 1994
• 22: Tomasz Imielinski , B. R. Badrinath, Querying in Highly Mobile Distributed Environments, Proceedings of the 18th International Conference on Very Large Data Bases, p.41-52, August 23-27, 1992
• 23: Kai Li, Shared virtual memory on loosely coupled multiprocessors, 1986
• 24: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• 25: Joonwon Lee , Umakishore Ramachandran, Synchronization with multiprocessor caches, Proceedings of the 17th annual international symposium on Computer Architecture, p.27-37, May 28-31, 1990, Seattle, Washington, United States
• 26: A.R'. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator, "Competitive Snoopy Caching", Algorithmica (1988) 3:79-119
• 27: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 28: D.3. Makaroff and D.L. Eager, "Disk Cache Performance for Distributed Systems" Proc. of the 10- th Int'l Conf. on Dist. Computing Systems, Pages 212-219, May 1990
• 29: Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62243]
• 30: Mahadev Satyanarayanan , James J. Kistler , Puneet Kumar , Maria E. Okasaki , Ellen H. Siegel , David C. Steere, Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transactions on Computers, v.39 n.4, p.447-459, April 1990 [doi>10.1109/12.54838]
• 31: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 32: Ouri Wolfson , Sushil Jajodia, Distributed algorithms for dynamic replication of data, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.149-163, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137858]
• 33: Ouri Wolfson and Sushil J ajodia, "An Algorithm for Dynamic Data Distribution", Proc. of the 2nd Workshop on Management of Replicated Data (WMRD-II), 1992, pp. 62-65
• 34: 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]
• 35: Yongdong Wang , Lawrence A. Rowe, Cache consistency and concurrency control in a client/server DBMS architecture, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.367-376, May 29-31, 1991, Denver, Colorado, United States

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

General Terms:
Algorithms, Design, Performance, Theory