Ouri Wolfson
Sushil Jajodia
Skip Abstract Section
Abstract
This article addresses the performance of distributed database systems. Specifically, we present an algorithm for dynamic replication of an object in distributed systems. The algorithm is adaptive in the sence that it changes the replication scheme of the object i.e., the set of processors at which the object inreplicated) as changes occur in the read-write patern of the object (i.e., the number of reads and writes issued by each processor). The algorithm continuously moves the replication scheme towards an optimal one. We show that the algorithm can be combined with the concurrency control and recovery mechanisms of ta distributed database management system. The performance of the algorithm is analyzed theoretically and experimentally. On the way we provide a lower bound on the performance of any dynamic replication algorith.
- AHAMAD, M., AND AMMAR, M.H. 1991. Multidimensional voting. ACM Trans. Comput. Syst. 9, 4, 399-431. Google Scholar
Digital Library
- AGRAWAL, D. AND BERNSTEIN, A. g. 1991. A nonblocking quorum consensus protocol for replicated data. IEEE Trans. Parallel Distrib. Syst. 2, 2 (April), 171-179. Google ScholarDigital Library
- AWERBUCH, B., BARTAL, Y., AND FIAT, A. 1993. Optimally-competitive distributed file allocation. In Proceedings of the 25th Annual ACM STOC (Victoria, B.C., Canada, May) ACM, New York, 164-173. Google ScholarDigital Library
- ALONSO, R., BARBARA, D., AND GARCIA-MOLINA, H. 1988. Quasi-copies: Efficient data sharing for information retrieval systems. In Proceedings of EDBT '88, LNCS 303, Springer-Verlag, New York. Google ScholarDigital Library
- ALONSO, R., BARBARA, D., AND GARCIA-MOLINA, H. 1990. Data caching issues in an information retrieval system. ACM Trans. Database Syst. 15, 3. Google ScholarDigital Library
- AGRAWAL, D. AND EL-ABBADI, A. 1990. The tree quorum protocol: An efficient approach for managing replicated data. In Proceedings of 16th VLDB (Aug.). Google ScholarDigital Library
- ADAM, N. R. AND TEWARI, R. 1993. Regeneration with virtual copies for distributed computing systems. IEEE Trans. Softw. Eng. 19, 6 (June), 594-602. Google ScholarDigital Library
- BARTAL, Y., FIAT, A., AND RABANI, Y. 1992. Competitive algorithms for distributed data management. In Proceedings of the 24th Annual ACM STOC, (Victoria, B.C., Canada, May), ACM, New York. Google ScholarDigital Library
- BARBARA, D. AND GARCIA-MOLINA, H. 1993. Replicated data management in mobile environmeAts: Anything new under the sun? Manuscript, Oct.Google Scholar
- BARBARA, D. AND GARCIA-MOLINA, H. 1990. The case for controlled inconsistency in replicated data. In Proceedings of the IEEE Workshop on Replicated Data.Google ScholarCross Ref
- BERNSTEIN, P., HADZILACOS, V., AND GOODMAN, N. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley, Reading, MA. Google ScholarDigital Library
- BADRINATH, B. R. AND IMIELINSKI, T. 1992. Replication and mobility. In Proceedings of the 2nd Workshop on the Management of Replicated Data (Monterey, CA), 9-12.Google ScholarCross Ref
- BADRINATH, B. R., IMIELINSKI, T., AND VIRMANI, A. 1992. Locating strategies for personal communication networks. In Proceedings of the Workshop on Networking of Personal Communication Applications (Dec.).Google Scholar
- CERI, S. AND PELAGATTI, G. 1984. Distributed Database Principles and Systems. McGraw- Hill, New York. Google ScholarDigital Library
- DOWDY, L. W. AND FOSTER, D.V. 1982. Comparative models of the file assignment problem. ACM Comput. Sur. 14, 2. Google ScholarDigital Library
- DuPuY, A., SENGUPTA, S., WOLFSON, O., AND YEMINI, Y. 1991a. Design of the Netmate network management system. Integrated network management II. In Proceedings of the Second International Symposium on Integrated Network Management (Washington D.C., Apr.).Google Scholar
- DuPuY, A., SENGUPTA, S., WOLFSON, O., AND YEMINI, Y. 1991b. NETMATE: A network management environment. (Invited article), IEEE Netw. (Mar.).Google Scholar
- FISCHER, M. AND MICHAEL, A. 1992. Sacrificing serializability to attain high availability of data in an unreliable network. In ACM-PODS '92 ACM, New York, 70-75. Google ScholarDigital Library
- GARCIA-MOLINA, H. AND BARBARA, D. 1985. How to assign votes in a distributed system. J. ACM 32, 4, 841-860. Google ScholarDigital Library
- GIFFORD, D. 1979. Weighted voting for replicated data. In Proceedings of the 7th ACM Symposium on Operation System Principles, 150-162. Google ScholarDigital Library
- GOODMAN, D. 1991. Trends in cellular and cordless communications. IEEE Commun. Mag. (June) 31-40.Google ScholarDigital Library
- GRUDIN, J. (ED.). 1991. Special section on computer supported cooperative work. Commun. ACM 34, 12. Google ScholarDigital Library
- GAVISH, B. AND SHENG, O. 1990. Dynamic file migration in distributed computer systems. Commun. ACM 33, 2. Google ScholarDigital Library
- HERLIHY, M. 1987. Dynamic quorum adjustments for partitioned data. ACM Trans. Database Syst. 12, 2. Google ScholarDigital Library
- HUMENIK, K., MATTHEWS, P., STEPHENS, A., AND YESHA, Y. 1992. Minimizing message complexity in partially replicated databases on hypercube networks. TR CS-92-09 Dept. of Computer Science, Univ. of Maryland, Baltimore, July.Google Scholar
- HUANG, Y. AND WOLFSON, O. 1993. A competitive dynamic data replication algorithm. In IEEE Proceedings of the 9th International Conference on Data Engineering, 310-317. Google ScholarDigital Library
- HUANG, Y. AND WOLFSON, O. 1994. Dynamic allocation in distributed system and mobile computers. In IEEE Proceedings of the l Oth International Conference on Data Engineering. 20 -29. Google ScholarDigital Library
- IMIELINSKI, T. AND BADRINATH, B.R. 1992. Querying in highly mobile distributed environments. In Proceedings of the 18th International Conference on VLDB. 41-52. Google ScholarDigital Library
- JAJODIA, S. AND MUTCHLER, D. 1990. Dynamic voting algorithms for maintaining the consistency of a replicated database. ACM Trans. Database Syst. 15, 2 (June), 230-280. Google ScholarDigital Library
- KRISHNAKUMAR, N. AND BERNSTEIN, A. 1991. Bounded ignorance in replicated systems. In Proceedings of ACM-PODS '91. ACM, New York. Google ScholarDigital Library
- KISTLER, J. J. AND SATYANARAYANAN, M. 1992. Disconnected operation in the coda file system. ACM Trans. Comput. Syst. 10, 1 (Feb.), 3-25. Google ScholarDigital Library
- KUMAR, A. 1991. Hierarchical quorum consensus: A new algorithm for managing replicated data. IEEE Trans. Comput. 40, 9 (Sept.), 996-1004. Google ScholarDigital Library
- LADIN, R., LISKOV, B. AND SHRIRA, L. 1988. A technique for constructing highly available distributed services. Algorithmica 3. Google ScholarDigital Library
- LADIN, R., LISKOV, B., SHRIRA, L., AND GHEMAWAT, S. 1992. Providing high availability using lazy replication. ACM Trans. Comput. Syst. 10, 4 (Nov.). Google ScholarDigital Library
- LADIN, R., LISKOV, B., AND SHRIRA, L. 1990. Lazy replication: Exploiting the semantics of distributed services. In Proceedings of the Workshop on Management of Replicated Data. (Nov.), 31-34. Google ScholarDigital Library
- MINOURA, T. AND WIEDERHOLD, G. 1982. Resilient extented true-copy token scheme for a distributed database systems. IEEE Trans. Softw. Eng. SE-8, 3 (May), 173-189.Google ScholarDigital Library
- Ozsu, M. T. AND VALDURIEZ, P. 1991. Principles of Distributed Database Systems. Prentice- Hall, Englewood Cliffs, NJ. Google ScholarDigital Library
- PARIS, J. 1986. Voting with a variable number of copies. In Fault-Tolerant Computing Symposium, (June), 50-55.Google Scholar
- SPASOJEVIC, M. AND BERMAN, P. 1994. Voting as the optimal static pessimistic scheme for managing replicated data. IEEE Trans. Parallel Distrib. Syst. 5, 1 (Jan.), 64-73. Google ScholarDigital Library
- SENGUPTA, S., DuPuY, A., SCHWARTZ, J., WOLFSON, O., AND YEMINI, Y. 1990. The Netmate model for network management. IEEE 1990 Network Operations and Management Symposium (NOMS), (San Diego, CA, Feb.), 11-14.Google Scholar
- SATYANARAYANAN, M., KISTLER, J. J., KUMAR, P., OKASAKI, M. E., SIEGEL, E. H., AND STEERE, D. C. 1990. Coda: A highly available file system for a distributed workstation environment. IEEE Trans. Comput. 39, 4 (April), 447-459. Google ScholarDigital Library
- THOMAS, R. H. 1979. A majority consensus approach to concurrency control for multiple copy database. ACM Trans. Database Syst. 4, 2 (June), 180-209. Google ScholarDigital Library
- TRIANTAFILLOU, P. AND TAYLOR, D. g. 1991. Using multiple replica classes to improve performance in distributed systems. In Proceedings of the 11th IEEE International Conference on Distributed Computing Systems. (April), 34-41.Google ScholarCross Ref
- WOLFSON, O. AND JAJODIA, S. 1992. Distributed algorithms for adaptive replication of data. ACM PODS '92 (San-Diego, CA, June), ACM, New York, 146-163. Google ScholarDigital Library
- WOLFSON, O. AND MILO, A. 1991. The multicast policy and its relationship to replicated data placement. ACM Trans. Database Syst. 16, 1. Google ScholarDigital Library
- WOLFSON, O., SENGUPTA, S., AND YEMINI, Y. 1991. Managing communication networks by monitoring databases. IEEE Trans. Softw. Eng. 17, 9 (Sept.), 944-953. Google ScholarDigital Library
Index Terms
- An adaptive data replication algorithm
Recommendations
Weighted voting for replicated data
SOSP '79: Proceedings of the seventh ACM symposium on Operating systems principlesIn a new algorithm for maintaining replicated data, every copy of a replicated file is assigned some number of votes. Every transaction collects a read quorum of rvotes to read a file, and a write quorum of wvotes to write a file, such that r+w is ...
A Fault-Tolerant Algorithm for Replicated Data Management
In this paper, we examine the tradeoff between message overhead and data availability that arises in the design of fault-tolerant algorithms for replicated data management in distributed systems. We propose a property called asymptotically high ...
Protocol refinement for maintaining replicated data in distributed systems
SPDP '93: Proceedings of the 1993 5th IEEE Symposium on Parallel and Distributed ProcessingData can be replicated to improve availability and performance in distributed systems. To ensure one copy serializability, many protocols have been proposed. Most of these protocols are based on the quorum set approach.However, some of them are ...
Comments