Extend the R and W quorum to > 1. Say choose R and W random subset of preferred list of N.
Coordinator waits until operation is (1) executed locally with local vector clock, and (2) replicated to the quorum verbatim, i.e. with coordinator vector clock.
Async Replication
Eventually each object gets replicated to N nodes (which N depends on the object), regardless of R or W.
Coordinator does not have to wait for async replication to return success.
Async rep can be done periodically in background, in batch.
Merkle tree helps to quickly figure out which replicas for what key ranges and keys are out of sync (i.e. missing some should-have-been-replicated object versions)
Example: N = (S_1, S_2, S_3). S_1 coordinates D_1([S_1,1]) and sync-replicates to S_2. Meanwhile, S_3 coordinates D_2([S_3,1]) and sync-replicates to S_2. S_1, S_2 and S_3 need to decide what's missing on each other's data. Using Merkle tree, they quickly find out it's only object D that's different across. Then they sync on D by passing around D_1 and D_2. Say S_1 gets D_2 from S_3, and adds it to its store; S_2 gets D_1 from S_1 and D_2 from S_3 but doesn't need to update its store; S_3 gets (D_1,D_2) from S_2 and only adds D_1 to its store.
We do not consider failures just yet. But we can hopefully already see the effect of replication on reducing version divergence.
Sync Replication
Async Replication
We do not consider failures just yet. But we can hopefully already see the effect of replication on reducing version divergence.