Experience with many applications (e.g., web caching, P2P sharing, and
grid and cloud computing) shows that data replication is a fundamental
feature of large systems. Replication improves performance,
availability and dependability.
Replication algorithms based on state machine replication are attractive
because they maintain a simple sequential semantics. However, we
believe they will not scale to massive cloud and peer-to-peer systems.
To be successful, future algorithms must: (1) support multi-object
transactions across distant data centres, (2) leverage the semantics of
data accesses, and (3) support partial replication.
In the first part of this talk, we describe two variants of Generalized
Paxos, a solution to consensus that leverages the commutativity
semantics. Our algorithms reduce message delay when a collision occurs
between non-commuting operations. In the second part, we present a new
approach to partial replication of database systems at large scale.
Previous protocols either reexecute transactions entirely and/or compute
a total order of transactions. In contrast, ours applies update values,
and generate a partial order between mutually conflicting transactions
only.