Replication: Optimistic Approaches

Saito, Yasushi ; Shapiro, Marc

HP Development Company

关键词: optimistic;    replication;    survey;   

RP-ID  :  HPL-2002-33

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Replication is a key enabling technology in distributed data sharing systems for improving both availability and performance. This paper surveys optimistic replication algorithms, which allow replica contents to diverge in the short term, in order to support concurrent work and to tolerate failures in low-quality communication links. The importance of such techniques is increasing as collaboration through wide-area and mobile networks is becoming more popular. Optimistic replication algorithms employ techniques vastly different from those for traditional pessimistic algorithms. Whereas a pessimistic algorithm relies on synchronous replica coordination, an optimistic algorithm propagates its updates in the background, discovers conflicts after they happen, and reaches an agreement on the final object contents incrementally. This paper identifies the key challenges that optimistic replication systems face -- - achieving uniformity, guaranteeing quality of replica contents, and scaling --- and presents a comprehensive survey of techniques developed for addressing these challenges. 40 Pages