Techniques are provided for managing replicated data items in a cluster of shared nothing nodes. The techniques include synchronously propagating changes to one or more replicas, while asynchronously propagating changes to the remaining replicas. Because the replicas to which the change is synchronously replicated may be a relatively small percentage of the total number of replicas, the overhead associated with performing an update is reduced. The process of selecting which nodes are involved in the synchronous update operation may take into account a variety of factors, including which replicas are available at the time the update operation is being performed.