Efficient support for partial write operations in replicated databases

We present a new replica control technique targeted at replicated systems in which write operations update a portion of the information in the data item rather than replacing it entirely. The existing protocols capable of supporting partial writes must either perform the writes on all accessible replicas of the data item, or always apply the writes to the same group (quorum set) of replicas. In the former case, the system incurs high message overhead. In the latter case, if any of the replicas in this group fail, additional replicas must be synchronously brought up-to-date during the write operation causing delay to the operation. Also, in both cases, the system loses the advantage of load sharing provided by replication. Our protocol avoids performing the write on all nodes while preserving load sharing and reducing greatly the risk of having to propagate updates synchronously. We describe the protocol, prove it correct, and present a comparative performance study of our protocol and the existing alternatives