On Optimal Concurrency Control for Optimistic Replication

Concurrency control is a core component in optimistic replication systems. To detect concurrent updates, the system associates each replicated object with metadata, such as, version vectors or causal graphs exchanged on synchronization opportunities. However, the size of such metadata increases at least linearly with the number of active sites. With trends in cloud computing, multi-regional collaboration, and mobile networks, the number of sites within a single replication system becomes very large. This imposes substantial overhead in communication and computation on every site. In this paper, we first present three version vector implementations that significantly reduce the cost of vector exchange by incrementally transferring vector elements. Basic rotating vectors (BRV) support systems providing no conflict reconciliation, whereas conflict rotating vectors (CRV) extend BRV to overcome this limitation. Skip rotating vectors (SRV) based on CRV further reduce data transmission. We show that both BRV and SRV are optimal implementations of version vectors, which, in turn, have minimal storage complexity among all known concurrency control schemes for state-transfer systems. We then present a causal graph exchange algorithm for operation-transfer systems with optimal communication overhead. All these algorithms adopt network pipelining to reduce running time.