Brent ByungHoon Kang

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1351
October 2004

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1351.pdf

High data availability and scalability beyond a single shared server require data to be replicated and exchanged in a decentralized way. Optimistic replication is the primary technique to achieve these goals; however, current approaches to optimistic replication have fundamental limitations. Version vector based approaches entail complicated management in site addition/deletion and have limited scalability in terms of the number of replica sites. Moreover, version vectors entail significant overhead in maintaining revision histories that are essentially required to deter various attacks on decentralized ordering correctness. Because of the cooperative nature of decentralized dependency tracking mechanisms, a malicious site can easily falsify ordering information, which may cause the shared state to diverge without being detected.

This thesis presents S2D2, a framework that provides optimistic replication based on a novel decentralized ordering mechanism, called Summary Hash History (SHH). Being based on a causal history approach with secure summary hashes as version identifiers, SHH supports simple management of site membership changes, scales regardless of the number of sites, and guarantees the correctness of decentralized ordering in a scalable way. SHH uses "two-step reconciliation" to overcome the inherent limitation of the causal history approach, and thus, consumes orders of magnitude lower bandwidth than reconciliation based on version vectors. Interestingly, SHH provides faster convergence than version vector based approaches by recognizing "coincidental equalities," cases when identical versions are produced independently at different sites. This is of significant value in that SHH can enable distributed replica to converge even in the network partitions or disconnections that mobile computing and wide-area distributed computing have to cope with fundamentally.

S2D2 employs an elegant "hash typing" mechanism to enforce correctness in the error-prone usage of hashes and uses an "adaptor architecture" to support the application-specific consistency requirements. Prototype implementations of adaptors, for a peer-to-peer CVS (a concurrent version control system) and a replicated-shared folder, demonstrate that the S2D2 framework is highly suitable for supporting secure optimistic replication among global-scale and pervasive applications.

Advisor: Robert Wilensky

BibTeX citation:

@phdthesis{Kang:CSD-04-1351,
    Author = {Kang, Brent ByungHoon},
    Title = {S2D2: A Framework for Scalable and Secure Optimistic Replication},
    School = {EECS Department, University of California, Berkeley},
    Year = {2004},
    Month = {Oct},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5917.html},
    Number = {UCB/CSD-04-1351},
    Abstract = {High data availability and scalability beyond a single shared server require data to be replicated and exchanged in a decentralized way. Optimistic replication is the primary technique to achieve these goals; however, current approaches to optimistic replication have fundamental limitations. Version vector based approaches entail complicated management in site addition/deletion and have limited scalability in terms of the number of replica sites. Moreover, version vectors entail significant overhead in maintaining revision histories that are essentially required to deter various attacks on decentralized ordering correctness. Because of the cooperative nature of decentralized dependency tracking mechanisms, a malicious site can easily falsify ordering information, which may cause the shared state to diverge without being detected. <p>This thesis presents S2D2, a framework that provides optimistic replication based on a novel decentralized ordering mechanism, called Summary Hash History (SHH). Being based on a causal history approach with secure summary hashes as version identifiers, SHH supports simple management of site membership changes, scales regardless of the number of sites, and guarantees the correctness of decentralized ordering in a scalable way. SHH uses "two-step reconciliation" to overcome the inherent limitation of the causal history approach, and thus, consumes orders of magnitude lower bandwidth than reconciliation based on version vectors. Interestingly, SHH provides faster convergence than version vector based approaches by recognizing "coincidental equalities," cases when identical versions are produced independently at different sites. This is of significant value in that SHH can enable distributed replica to converge even in the network partitions or disconnections that mobile computing and wide-area distributed computing have to cope with fundamentally. <p>S2D2 employs an elegant "hash typing" mechanism to enforce correctness in the error-prone usage of hashes and uses an "adaptor architecture" to support the application-specific consistency requirements. Prototype implementations of adaptors, for a peer-to-peer CVS (a concurrent version control system) and a replicated-shared folder, demonstrate that the S2D2 framework is highly suitable for supporting secure optimistic replication among global-scale and pervasive applications.}
}

EndNote citation:

%0 Thesis
%A Kang, Brent ByungHoon
%T S2D2: A Framework for Scalable and Secure Optimistic Replication
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1351
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5917.html
%F Kang:CSD-04-1351