Paper Info
Title
On Optimal Concurrency Control for Optimistic Replication
Abstract
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 recent 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.
Year
DOI
Venue
2009
10.1109/ICDCS.2009.71
ICDCS
Keywords
Field
DocType
concurrency control scheme,causal graph exchange algorithm,vector element,concurrency control,vector exchange,optimistic replication,metadata increase,causal graph,optimal concurrency control,conflict reconciliation,version vector,version vector implementation,collaboration,cloud computing,metadata,control systems,data mining,scalability,data transmission,probability density function,active site,mobile network,availability,meteorology,col,distributed computing,synchronization,meta data,mobile computing,graph theory
Graph theory,Optimistic replication,Pipeline (computing),Metadata,Synchronization,Concurrency control,Computer science,Computer network,Distributed computing,Version vector,Cloud computing
Conference
ISSN
Citations 
PageRank 
1063-6927
3
0.55
References 
Authors
20
2
Name
Order
Citations
PageRank
Weihan Wang1196.08
Cristiana Amza2106181.70