Large-scale distributed storage systems built over failureprone commodity components are increasingly popular. Failures are common in those large systems, and replication is often the solution to data reliability. A clear gap remains between the well-known consensus algorithms and the practical replication protocols in real systems: consensus algorithms such as Paxos [2] are used mostly to maintain global configuration information, not for the actual data replication.