Abstract
Data replication is a key technology in distributed systems that enables higher availability and performance. This article surveys optimistic replication algorithms. They allow replica contents to diverge in the short term to support concurrent work practices and tolerate failures in low-quality communication links. The importance of such techniques is increasing as collaboration through wide-area and mobile networks becomes popular.Optimistic replication deploys algorithms not seen in traditional “pessimistic” systems. Instead of synchronous replica coordination, an optimistic algorithm propagates changes in the background, discovers conflicts after they happen, and reaches agreement on the final contents incrementally.We explore the solution space for optimistic replication algorithms. This article identifies key challenges facing optimistic replication systems---ordering operations, detecting and resolving conflicts, propagating changes efficiently, and bounding replica divergence---and provides a comprehensive survey of techniques developed for addressing these challenges.
- Adly, N. 1995. Management of replicated data in large scale systems. Ph.D. thesis, Corpus Cristi College, University of Cambridge.]]Google Scholar
- Adya, A. and Liskov, B. 1997. Lazy consistency using loosely synchronized clocks. In 16th Symposium on Principles of Distributed Computing (PODC). Santa Barbara, CA. 73--82.]] Google ScholarDigital Library
- Agrawal, D., Abbadi, A. E., and Steike, R. C. 1997. Epidemic algorithms in replicated databases. In 16th Symposium on Principles of Database Systems (PODS). Tucson, AZ. 161--172.]] Google ScholarDigital Library
- Albitz, P. and Liu, C. 2001. DNS and BIND, 4th Ed. O'Reilly & Associates. Sebastopol, CA. ISBN 0-596-00158-4.]] Google ScholarDigital Library
- Almeida, P. S., Baquero, C., and Fonte, V. 2000. Panasync: Dependency tracking among file copies. In 9th ACM SIGOPS European Workshop, P. Guedes, Ed. Kolding, Denmark. 7--12.]] Google ScholarDigital Library
- Almeida, P. S., Baquero, C., and Fonte, V. 2002. Version stamps---decentralized version vectors. In 22nd International Conference on Distributed Computing Systems (ICDCS). Vienna, Austria. 544--551.]] Google ScholarDigital Library
- Alonso, R., Barbara, D., and Garcia-Molina, H. 1990. Data caching issues in an information retrieval system. ACM Trans. Datab. Syst. 15, 3 (Sept.), 359--384.]] Google ScholarDigital Library
- Baker, M., Hartman, J. H., Kupfer, M. D., Shirriff, K., and Ousterhout, J. K. 1991. Measurements of a distributed file system. In 13th Symposium on Operating Systems Principles (SOSP). Pacific Grove, CA. 198--212.]] Google ScholarDigital Library
- Balasubramaniam, S. and Pierce, B. C. 1998. What is a file synchronizer? In 4th International Conference on Mobile Computing and Networking (MOBICOM). ACM/IEEE. Dellas, TX.]] Google ScholarDigital Library
- Bernstein, P. A. and Goodman, N. 1983. The failure and recovery problem for replicated databases. In 2nd Symposium on Principles of Distributed Computing (PODC). Montréal, QC, Canada. 114--122.]] Google ScholarDigital Library
- Bernstein, P. A., Hadzilacos, V., and Goodman, N. 1987. Concurrency Control and Recovery in Database Systems. Addison Wesley, Boston, MA. Available at http://research.microsoft.com/pubs/ccontrol/.]] Google ScholarDigital Library
- Birman, K. P., Hayden, M., Ozkasap, O., Xiao, Z., Budiu, M., and Minsky, Y. 1999. Bimodal multicast. ACM Trans. Comp. Syst. 17, 2, 41--88.]] Google ScholarDigital Library
- Birman, K. P. and Joseph, T. A. 1987. Reliable communication in the presence of failures. ACM Trans. Comp. Syst. 5, 1 (Feb.), 272--314.]] Google ScholarDigital Library
- Birrell, A. D., Levin, R., Needham, R. M., and Schroeder, M. D. 1982. Grapevine: An exercise in distributed computing. Comm. ACM 25, 4 (Feb.), 260--274.]] Google ScholarDigital Library
- Bolinger, D. and Bronson, T. 1995. Applying RCS and SCCS. O'Reilly & Associates, Sebastopol, CA.]] Google ScholarDigital Library
- Carter, J., Ranganathan, A., and Susarla, S. 1998. Khazana: An infrastructure for building distributed services. In 18th International Conference on Distributed Computer Systems (ICDCS). Amsterdam, The Netherlands. 562--571.]] Google ScholarDigital Library
- Cederqvist, P., Pesch, R., et al. 2001. Version management with CVS. Available at http://www.cvshome.org/docs/manual.]]Google Scholar
- Chandra, B., Dahlin, M., Gao, L., and Nayate, A. 2001. End-to-end WAN service availability. In 3rd USENIX Symposium on Internet Technology and Systems (USITS). San Francisco, CA.]] Google ScholarDigital Library
- Chandra, T. D. and Toueg, S. 1996. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2 (Mar.), 225--267.]] Google ScholarDigital Library
- Chankhunthod, A., Danzig, P. B., Neerdaels, C., Schwartz, M. F., and Worrell, K. J. 1996. A hierarchical internet object cache. In USENIX Winter Technical Conference. San Diego, CA. 153--164.]] Google ScholarDigital Library
- Charron-Bost, B. 1991. Concerning the size of logical clocks in distributed systems. Information Processing Letters 39, 1 (July), 11--16.]] Google ScholarDigital Library
- Chen, Y., Edler, J., Goldberg, A., Gottlieb, A., Sobti, S., and Yianilos, P. N. 1999. A prototype implementation of archival intermemory. In Fourth ACM Conference on Digital Libraries (DL'99). ACM, Berkeley CA. 28--37.]] Google ScholarDigital Library
- Cho, J. and Garcia-Molina, H. 2000. Synchronizing a database to improve freshness. In International Conference on Management of Data (SIGMOD). Dallas, TX. 117--128.]] Google ScholarDigital Library
- Cormack, G. V. 1995. A calculus for concurrent update. Tech. Rep. CS-95-06, University of Waterloo.]]Google Scholar
- Cox, L. P. and Noble, B. D. 2001. Fast reconciliations in fluid replication. In 21st International Conference on Distributed Computer Systems (ICDCS). Phoenix, AZ.]] Google ScholarDigital Library
- de Torres-Rojas, F. and Ahamad, M. 1996. Plausible clocks: Constant size logical clocks for distributed systems. In 10th International Workshop on Distributed Algorithms (WDAG). Bologna, Italy.]] Google ScholarDigital Library
- Deering, S. E. 1991. Multicast routing in a datagram internetwork. Ph.D. thesis, Stanford University.]] Google ScholarDigital Library
- Demers, A. J., Greene, D. H., Hauser, C., Irish, W., and Larson, J. 1987. Epidemic algorithms for replicated database maintenance. In 6th Symposium on Princeples of Distributed Computing (PODC). Vancouver, BC, Canada. 1--12.]] Google ScholarDigital Library
- Dietterich, D. J. 1994. DEC data distributor: For data replication and data warehousing. In International Conference on Management of Data (SIGMOD). ACM, Minneapolis, MN. 468.]] Google ScholarDigital Library
- Ellis, C. A. and Gibbs, S. J. 1989. Concurrency control in groupware systems. In International Conference on Management of Data (SIGMOD). Portland, OR.]] Google ScholarDigital Library
- Elmagarmid, A. K., Ed. 1992. Database Transaction Models for Advanced Applications. Morgan Kaufmann, San Francisco, CA.]] Google ScholarDigital Library
- Elson, J., Girod, L., and Estrin, D. 2002. Fine-grained network time synchronization using reference broadcasts. In 5th Symposium on Operating Systems Design and Implementation (OSDI). Boston, MA.]] Google ScholarDigital Library
- Fekete, A., Gupta, D., Luchangco, V., Lynch, N., and Shvartsman, A. 1999. Eventually serializable data services. Theor. Comput. Sci. 220: Special issue on Distributed Algorithms, 113--156.]] Google ScholarDigital Library
- Fekete, A., Lynch, N., and Shvartsman, A. 1997. Specifying and using a partitionable group communication service. In 16th Symposium on Principles of Distributed Computing (PODC). Santa Barbara, CA. 53--62.]] Google ScholarDigital Library
- Fidge, C. J. 1988. Timestamps in message-passing systems that preserve the partial ordering. In 11th Australian Computer Science Conference. University of Queensland, Australia. 55--66.]]Google Scholar
- Fielding, R., Gettys, J., Mogul, J., Frystyk, H., Masinter, L., Leach, P., and Berners-Lee, T. 1999. RFC2616: Hypertext transfer protocol---HTTP/1.1. Available at http://www.faqs.org/rfcs/rfc2616.html.]] Google ScholarDigital Library
- Fischer, M. J., Lynch, N. A., and Paterson, M. S. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2, 374--382.]] Google ScholarDigital Library
- Fischer, M. J. and Michael, A. 1982. Sacrificing serializability to attain availability of data in an unreliable network. In 1st Symposium on Principles of Database Systems (PODS). Los Angeles, CA. 70--75.]] Google ScholarDigital Library
- Floyd, S., Jacobsen, V., Liu, C.-G., McCanne, S., and Zhang, L. 1997. A reliable multicast framework for light-weight sessions and application level framing. IEEE/ACM J. Netw. 5, 6 (Dec.), 784--803.]] Google ScholarDigital Library
- Fox, A. and Brewer, E. A. 1999. Harvest, yield, and scalable tolerant systems. In 6th Workshop on Hot Topics in Operating Systems (HOTOS-VI). Rio Rico, AZ. 174--178.]] Google ScholarDigital Library
- Gifford, D. K. 1979. Weighted voting for replicated data. In 7th Symposium on Operating Systems Principles (SOSP). Pacific Grove, CA. 150--162.]] Google ScholarDigital Library
- Golding, R. A. 1992. Weak-consistency group communication and membership. Ph.D. thesis. Tech. Report no. UCSC-CRL-92-52. University of California Santa Cruz, CA.]] Google ScholarDigital Library
- Gray, J., Helland, P., O'Neil, P., and Shasha, D. 1996. Dangers of replication and a solution. In International Conference on Management of Data (SIGMOD). Montréal, Canada. 173--182.]] Google ScholarDigital Library
- Gray, J. and Reuter, A. 1993. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, San Francisco, CA.]] Google ScholarDigital Library
- Guy, R. G., Popek, G. J., and Page, T. W., Jr. 1993. Consistency algorithms for optimistic replication. In Proceedings to 1st IEEE International Conference on Network Protocols. San Francisco, CA.]]Google Scholar
- Hedetniemi, S., Hedetniemi, S., and Liestman, O. 1988. A survey of gossiping and broadcasting in communication networks. Networks 18, 319--349.]]Google ScholarCross Ref
- Herlihy, M. P. and Wing, J. M. 1990. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12, 3, 463--492.]] Google ScholarDigital Library
- Jagadish, H. V., Mumick, I. S., and Rabinovich, M. 1997. Scalable versioning in distributed databases with commuting updates. In 13th International Conference on Data Engineering (ICDE). Birmingham, U.K. 520--531.]] Google ScholarDigital Library
- Johnson, P. R. and Thomas, R. H. 1976. RFC677: The maintenance of duplicate databases. Available at http://www.faqs.org/rfcs/rfc677.html.]] Google ScholarDigital Library
- Johnson, T. and Jeong, K. 1996. Hierarchical matrix timestamps for scalable update propagation. Tech. Rep. (June). TR96-017, University of Florida.]]Google Scholar
- Kang, B. B., Wilensky, R., and Kubiatowicz, J. 2003. The hash history approach for reconciling mutual inconsistency. In 23rd International Conference on Distributed Computer Systems (ICDCS). Providence, RI.]] Google ScholarDigital Library
- Kantor, B. and Rapsey, P. 1986. RFC977: Network news transfer protocol. Available at http://www.faqs.org/rfcs/rfc977.html.]] Google ScholarDigital Library
- Kawell, L., Jr., Beckhart, S., Halvorsen, T., Ozzie, R., and Greif, I. 1988. Replicated document management in a group communication system. In Conference on Computer Supported Cooperative Work (CSCW). Chapel Hill, NC.]] Google ScholarDigital Library
- Keleher, P. J. 1999. Decentralized replicated-object protocols. In 18th Symposium on Principles of Database Computing (PODC). Atlanta, GA. 143--151.]] Google ScholarDigital Library
- Kempe, D., Kleinberg, J., and Demers, A. 2001. Spatial gossip and resource location protocols. In 33rd Symposium on Theory of Computing (STOC). Crete, Greece.]] Google ScholarDigital Library
- Kermarrec, A.-M., Rowstron, A., Shapiro, M., and Druschel, P. 2001. The IceCube approach to the reconciliation of diverging replicas. In 20th Symposium on Principles of Distributed Computing (PODC). Newport, RI.]] Google ScholarDigital Library
- Kim, M., Cox, L. P., and Noble, B. D. 2002. Safety, visibility, and performance in a wide-area file system. In USENIX Conference on File and Storage Technologies (FAST). Monterey, CA.]] Google ScholarDigital Library
- Kistler, J. J. and Satyanarayanan, M. 1992. Disconnected operation in the Coda file system. ACM Trans. Comput. Syst. 10, 5 (Feb.), 3--25.]] Google ScholarDigital Library
- Krasel, C. 2000. Leafnode: An NNTP server for small sites. Available at http://www.leafnode.org.]]Google Scholar
- Krishnakumar, N. and Bernstein, A. 1994. Bounded ignorance: A technique for increasing concurrency in replicated systems. ACM Trans Datab. Syst. 19, 4 (Dec.), 685--722.]] Google ScholarDigital Library
- Kumar, A. and Stonebraker, M. 1988. Semantic based transaction management techniques for replicated data. In International Conference on Management of Data (SIGMOD). Chicago, Il. 117--125.]] Google ScholarDigital Library
- Kumar, A. and Stonebraker, M. 1990. An analysis of borrowing policies for escrow transactions in a replicated environment. In 6th International Conference on Data Engineering (ICDE). Los Angeles, CA. 446--454.]] Google ScholarDigital Library
- Kumar, P. and Satyanarayanan, M. 1993. Log-based directory resolution in the coda file system. In 2nd International Confernce on Parallel and Distributed Information Systems (PDIS). San Diego, CA. 202--213.]] Google ScholarDigital Library
- Kumar, P. and Satyanarayanan, M. 1995. Flexible and safe resolution of file conflicts. In USENIX Winter Technical Conference. New Orleans, LA. 95--106.]] Google ScholarDigital Library
- Ladin, R., Liskov, B., Shrira, L., and Ghemawat, S. 1990. Lazy replication: Exploiting the semantics of distributed services. Tech. Rep. TR-484 (July). MIT LCS.]] 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, 360--391.]] Google ScholarDigital Library
- Lamport, L. 1978. Time, clocks, and the ordering of events in a distributed system. Comm. ACM 21, 7 (July), 558--565.]] Google ScholarDigital Library
- Lawrence, N. D., Rowstron, A. I. T., Bishop, C. M., and Taylor, M. J. 2002. Optimising synchronisation times for mobile devices. In Advances in Neural Information Processing Systems, T. G. Dietterich, S. Becker, and Z. Ghahramani, Eds. Vol. 14. MIT Press, Cambridge, MA. 1401--1408.]]Google Scholar
- Lee, Y.-W., Leung, K.-S., and Satyanarayanan, M. 2002. Operation shipping for mobile file systems. IEEE Trans. Comput. 51, 1410--1422.]] Google ScholarDigital Library
- Lidl, K., Osborne, J., and Malcolm, J. 1994. Drinking from the firehose: Multicast USENET news. In USENIX Winter Technical Conference. San Francisco, CA. 33--45.]] Google ScholarDigital Library
- Lin, M. J. and Marzullo, K. 1999. Directional gossip: Gossip in a wide-area network. In Third European Dependable Computing Conference. Prague, Czechoslovakia. 364--379.]] Google ScholarDigital Library
- Lu, Q. and Satyanarayanan, M. 1995. Improving data consistency in mobile computing using isolation-only transactions. In 4th Workshop on Hot Topics in Operating Systems (HOTOS-IV). Orcas Island, WA.]] Google ScholarDigital Library
- Matheson, C. 2003. Personal communication.]]Google Scholar
- Mattern, F. 1989. Virtual time and global states of distributed systems. In International Workshop on Parallel and Distributed Algorithms. Elsevier Science Publishers B.V. (North-Holland). 216--226.]]Google Scholar
- Mazières, D. and Shasha, D. 2002. Building secure file systems out of Byzantine storage. In 21st Symposium on Principles of Distribted Computing (PODC). Monterey, CA.]] Google ScholarDigital Library
- Microsoft. 2000. Windows 2000 Server: Distributed systems guide. Microsoft Press, Redmond, WA. Chapter 6, 299--340.]]Google Scholar
- Mills, D. L. 1994. Improved algorithms for synchronizing computer network clocks. In ACM SIGCOMM. London, UK. 317--327.]] Google ScholarDigital Library
- Minsky, Y. 2002. Spread rumors cheaply, quickly and reliably. Ph.D. thesis, Cornell University.]] Google ScholarDigital Library
- Minsky, Y., Trachtenberg, A., and Zippel, R. 2001. Set reconciliation with nearly optimal communication complexity. In International Symposium on Information Theory. IEEE. Washington, DC.]]Google Scholar
- Mishra, S., Peterson, L., and Schlichting, R. 1989. Implementing fault-tolerant replicated objects using Psync. In 8th Symposium on Reliable Distributed Systems (SRDS). Seattle, WA. 42--53.]]Google Scholar
- Mockapetris, P. V. 1987. RFC1035: Domain names---implementation and specification. Available at http://www.faqs.org/rfcs/rfc1035.html.]] Google ScholarDigital Library
- Mockapetris, P. V. and Dunlap, K. 1988. Development of the domain name system. In ACM SIGCOMM. Stanford, CA. 123--133.]] Google ScholarDigital Library
- Molli, P., Oster, G., Skaf-Molli, H., and Imine, A. 2003. Safe generic data synchronizer. Rapport de recherche A03-R-062 (May). LORIA.]]Google Scholar
- Moore, K. 1995. The lotus notes storage system. In International Conference on Management of Data (SIGMOD). San Jose, CA. 427.]] Google ScholarDigital Library
- Mummert, L. B., Ebling, M. R., and Satyanarayanan, M. 1995. Exploiting weak connectivity for mobile file access. In 15th Symposium on Operating Systems Principles (SOSP). Copper Mountain, CO. 143--155.]] Google ScholarDigital Library
- Muthitacharoen, A., Chen, B., and Mazières, D. 2001. A low-bandwidth network file system. In 18th Symposium on Operating Systems Principles (SOSP). Lake Louise, AB, Canada. 174--187.]] Google ScholarDigital Library
- Nakagawa, I. 1996. FTPmirror---mirroring directory hierarchy with FTP. Available at http://noc.intec.co.jp/ftpmirror.html.]]Google Scholar
- O'Neil, P. E. 1986. The escrow transactional method. ACM Trans. Datab. Syst. 11, 4, 405--430.]] Google ScholarDigital Library
- Oracle. 1996. Oracle7 Server Distributed Systems Manual, Vol. 2. Oracle.]]Google Scholar
- Ousterhout, J. K., da Costa, H., Harrison, D., Kunze, J. A., Kupfer, M. D., and Thompson, J. G. 1985. A trace-driven analysis of the Unix 4.2 BSD file system. In 10th Symposium on Operating Systems Principles (SOSP). Orcas Island, WA. 15--24.]] Google ScholarDigital Library
- Palmer, C. and Cormack, G. 1998. Operation transforms for a distributed shared spreadsheet. In Conference on Computer Supported Cooperative Work (CSCW). Seattle, WA. 69--78.]] Google ScholarDigital Library
- PalmSource, I. 2002. Introduction to conduit development. Available at http://www.palmos.com/dev/support/docs/.]]Google Scholar
- Parker, D. S., Popek, G., Rudisin, G., Stoughton, A., Walker, B., Walton, E., Chow, J., Edwards, D., Kiser, S., and Kline, C. 1983. Detection of mutual inconsistency in distributed systems. IEEE Trans. Softw. Eng. SE-9, 3, 240--247.]]Google ScholarDigital Library
- Paul, S., Sabnani, K. K., Lin, J. C., and Bhattacharyya, S. 1997. Reliable multicast transport protocol (RMTP). IEEE J. Select. Areas Comm. 15, 3 (Apr.), 407--421.]] Google ScholarDigital Library
- Pedone, F. 2001. Boosting system performance with optimistic distributed protocols. IEEE Computer 34, 7 (Dec.), 80--86.]] Google ScholarDigital Library
- Petersen, K., Spreitzer, M. J., Terry, D. B., Theimer, M. M., and Demers, A. J. 1997. Flexible update propagation for weakly consistent replication. In 16th Symposium on Operating Systems Principles (SOSP). St. Malo, France. 288--301.]] Google ScholarDigital Library
- Preguiça, N., Shapiro, M., and Matheson, C. 2003. Semantics-based reconciliation for collaborative and environments. In Proceedings of 10th International Conference on Cooperative Information Systems (CoopIS). Catania, Sicily, Italy.]]Google Scholar
- Pu, C., Hseush, W., Kaiser, G. E., Wu, K.-L., and Yu, P. S. 1995. Divergence control for distributed database systems. Dist. Parall. Datab. 3, 1 (Jan.), 85--109.]] Google ScholarDigital Library
- Pu, C., Hseush, W., Kaiser, G. E., Wu, K.-L., and Yu, P. S. 1995. Divergence control for distributed database systems. Dist. Parall. Datab. 3, 1 (Jan.), 85--109.]] Google ScholarDigital Library
- Pu, C. and Leff, A. 1991. Replica control in distributed systems: An asynchronous approach. In International Conference on Management of Data (SIGMOD). Denver, CO. 377--386.]] Google ScholarDigital Library
- Rabin, M. O. 1981. Fingerprinting by random polynomials. Tech. Rep. TR-15-81, Harvard University.]]Google Scholar
- Rabinovich, M., Gehani, N. H., and Kononov, A. 1996. Efficient update propagation in epidemic replicated databases. In International Conference on Extending Database Technology (EDBT). Avignon, France. 207--222.]] Google ScholarDigital Library
- Ramamritham, K. and Chrysanthis, P. K. 1996. Executive Briefing: Advances in Concurrency Control and Transaction Processing. IEEE Computer Society. Los Alamitos, CA. ISBN 0818674059.]] Google ScholarDigital Library
- Ramamritham, K. and Pu, C. 1995. A formal characterization of epsilon serializability. IEEE Trans. Knowl. Data Eng. 7, 6 (Dec.), 997--1007.]] Google ScholarDigital Library
- Ramsey, N. and Csirmaz, E. 2001. An algebraic approach to file synchronization. In 9th International Symposium on the Foundations of Software Engineering (FSE). Austria.]] Google ScholarDigital Library
- Ratner, D., Reiher, P., and Popek, G. 1997. Dynamic version vector maintenance. Tech. Rep. CSD-970022, UCLA (June).]]Google Scholar
- Ratner, D. H. 1998. Roam: A scalable replication system for mobile and distributed computing. Ph.D. thesis, Tech. Report. no. UCLA-CSD-970044. University of California, Los Angeles, CA.]] Google ScholarDigital Library
- Ravin, E., O'Reilly, T., Dougherty, D., and Todino, G. 1996. Using and Managing UUCP. O'Reilly & Associates, Sebastopol, CA.]] Google ScholarDigital Library
- Reiher, P., Heidemann, J. S., Ratner, D., Skinner, G., and Popek, G. J. 1994. Resolving file conflicts in the ficus file system. In USENIX Summer Technical Conference. Boston, MA. 183--195.]] Google ScholarDigital Library
- Rhodes, N. and McKeehan, J. 1998. Palm Programming: The Developer's Guide. O'Reilly & Associates, Sebastopol, CA.]] Google ScholarDigital Library
- Saito, Y. and Levy, H. M. 2000. Optimistic replication for Internet data services. In 14th International Conference on Distributed Computing (DISC). Toledo, Spain. 297--314.]] Google ScholarDigital Library
- Saito, Y., Mogul, J., and Verghese, B. 1998. A Usenet performance study. Available at http://www.hpl.hp.com/personal/Yasushi_Saito/pubs/newsbench.ps.]]Google Scholar
- Spencer, H. and Lawrence, D. 1998. Managing Usenet. O'Reilly & Associates, Sebastopol, CA. ISBN 1-56592-198-4.]] Google ScholarDigital Library
- Spreitzer, M. J., Theimer, M. M., Petersen, K., Demers, A. J., and Terry, D. B. 1997. Dealing with server corruption in weakly consistent, replicated data systems. In 3rd International Conference on Mobile Computing and Networking (MOBICOM). Budapest, Hungary.]] Google ScholarDigital Library
- Spring, N. T. and Wetherall, D. 2000. A protocol-independent technique for eliminating redundant network traffic. In ACM SIGCOMM Stockholm, Sweden.]] Google ScholarDigital Library
- Stern, H., Eisley, M., and Labiaga, R. 2001. Managing NFS and NIS, 2nd Ed. O'Reilly & Associates, Sebastopol, CA. ISBN 1-56592-510-6.]] Google ScholarDigital Library
- Sun, C. and Ellis, C. 1998. Operational transformation in real-time group editors: Issues, algorithms, and achievements. In Conference on Computer Supported Cooperative Work (CSCW). Seattle, WA. 59--68.]] Google ScholarDigital Library
- Sun, C., Jia, X., Zhang, Y., Yang, Y., and Chen, D. 1998. Achieving convergence, causality-preservation, and intention-preservation in real-time cooperative editing systems. ACM Trans. Comput.-Hum. Interact. 5, 1 (Mar.), 63--108.]] Google ScholarDigital Library
- Sun, C., Yang, Y., Zhang, Y., and Chen, D. 1996. A consistency model and supporting schemes for real-time cooperative editing systems. In 19th Australian Computer Science Conference. Melbourne, Australia. 582--591.]]Google Scholar
- Sun, Q. 2000. Reliable multicast for publish/subscribe systems. M.S. thesis, MIT.]]Google Scholar
- Sun Microsystems. 1998. Sun directory services 3.1 administration guide.]]Google Scholar
- Terry, D. B., Demers, A. J., Petersen, K., Spreitzer, M. J., Theimer, M. M., and Welch, B. B. 1994. Session guarantees for weakly consistent replicated data. In 3rd International Conference on Parallel and Distributed Information Systems (PDIS). Austin, TX. 140--149.]] Google ScholarDigital Library
- Terry, D. B., Theimer, M., Petersen, K., and Spreitzer, M. 2000. An examination of conflicts in a weakly-consistent, replicated application. Personal communication.]]Google Scholar
- Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., Spreitzer, M. J., and Hauser, C. H. 1995. Managing update conflicts in Bayou, a weakly connected replicated storage system. In 15th Symposium on Operating Systems Principles (SOSP). Copper Mountain, CO. 172--183.]] Google ScholarDigital Library
- Thomas, R. H. 1979. A majority consensus approach to concurrency control for multiple copy databases. ACM Trans. Datab. Syst. 4, 2 (June), 180--209.]] Google ScholarDigital Library
- Tridgell, A. 2000. Efficient algorithms for sorting and synchronization. Ph.D. thesis, Australian National University.]]Google Scholar
- Valot, C. 1993. Characterizing the accuracy of distributed timestamps. In Workshop on Parallel and Distributed Debugging. 43--52.]] Google ScholarDigital Library
- Vesperman, J. 2003. Essential CVS. O'Reilly & Associates, Sebastopol, CA.]] Google ScholarDigital Library
- Vidot, N., Cart, M., Ferri'e, J., and Suleiman, M. 2000. Copies convergence in a distributed real-time collaborative environment. In Conference on Computer Supported Cooperative Work (CSCW). Philadelphia, PA. 171--180.]] Google ScholarDigital Library
- Vogels, W. 1999. File system usage in Windows NT 4.0. In 17th Symposium on Operating Systems Principles (SOSP). Kiawah Island, SC, USA, 93--109.]] Google ScholarDigital Library
- Walker, B., Popek, G., English, R., Kline, C., and Thiel, G. 1983. The LOCUS distributed operating system. In 9th Symposium on Operating Systems Principles (SOSP). Bretton Woods, NH. 49--70.]] Google ScholarDigital Library
- Wang, A.-I. A., Reiher, P. L., and Bagrodia, R. 2001. Understanding the conflict rate metric for peer optimistically replicated filing environments. Submitted for publication.]]Google Scholar
- Wessels, D. and Claffy, K. 1997. RFC2186: Internet Cache Protocol. Available at http://www.faqs.org/rfcs/rfc2186.html.]] Google ScholarDigital Library
- Wuu, G. T. J. and Bernstein, A. J. 1984. Efficient solutions to the replicated log and dictionary problems. In 3rd Symposium on Principles of Distributed Computing (PODC). Vancouver, BC, Canada. 233--242.]] Google ScholarDigital Library
- XTP. 2003. The xpress transport protocol. Available at http://www.ca.sandia.gov/xtp/.]]Google Scholar
- Yin, J., Alvisi, L., Dahlin, M., and Lin, C. 1999. Hierarchical cache consistency in a WAN. In 2nd USENIX Symposium on Internet Technology and Systems (USITS). Boulder, CO. 13--24.]] Google ScholarDigital Library
- Yu, H. and Vahdat, A. 2000. Design and evaluation of a continuous consistency model for replicated services. In 4th Symposium on Operating Systems Design and Implementation (OSDI). San Diego, CA. 305--318.]] Google ScholarDigital Library
- Yu, H. and Vahdat, A. 2001. The costs and limits of availability for replicated services. In 18th Symposium on Operating Systems Principles (SOSP). Lake Louise, AB, Canada. 29--42.]] Google ScholarDigital Library
- Yu, H. and Vahdat, A. 2002. Minimal replication cost for availability. In 21st Symposium on Principles of Distributed Computing (PODC). Monterey, CA. 98--107.]] Google ScholarDigital Library
- Zhang, Y., Paxon, V., and Shenkar, S. 2000. The stationarity of Internet path properties: Routing, loss and throughput. Tech. rep. (May), ACIRI.]]Google Scholar
Index Terms
- Optimistic replication
Recommendations
Optimistic transactional active replication
ICUIMC '08: Proceedings of the 2nd international conference on Ubiquitous information management and communicationCritical database applications require 2-safe replication between at least two sites for disaster-tolerant services. At the same time, they must provide consistent and low-latency results to their clients in normal cases. In this paper, we propose ...
Branch replication scheme: A new model for data replication in large scale data grids
Data replication is a practical and effective method to achieve efficient and fault-tolerant data access in grids. Traditionally, data replication schemes maintain an entire replica in each site where a file is replicated, providing a read-only model. ...
Tutorial on geo-replication in data center applications
SIGMETRICS '13: Proceedings of the ACM SIGMETRICS/international conference on Measurement and modeling of computer systemsData center applications increasingly require a *geo-replicated* storage system, that is, a storage system replicated across many geographic locations. Geo-replication can reduce access latency, improve availability, and provide disaster tolerance. It ...
Comments