Description
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.