Home » References » Verifying PRAM Consistency over Read/Write Traces of Data Replicas

Verifying PRAM Consistency over Read/Write Traces of Data Replicas

Wei, et.al., 2013, Arxiv.org, Verifying PRAM Consistency over Read/Write Traces of Data Replicas, here. PRAM Consistency in China, nice.

Abstract—Data replication technologies enable efficient and highly-available data access, thus gaining more and more in- terests in both the academia and the industry. However, data replication introduces the problem of data consistency. Modern commercial data replication systems often provide weak consis- tency for high availability under certain failure scenarios. An important weak consistency is Pipelined-RAM (PRAM) consis- tency. It allows different processes to hold different views of data. To determine whether a data replication system indeed provides PRAM consistency, we study the problem of Verifying PRAM Consistency over read/write traces (or VPC, for short).

We first identify four variants of VPC according to a) whether there are Multiple shared variables (or one Single variable), and b) whether write operations can assign Duplicate values (or only Unique values) for each shared variable; the four variants are labeled VPC-SU, VPC-MU, VPC-SD, and VPC-MD. Second, we present a simple VPC-MU algorithm, called RW-CLOSURE. It constructs an operation graph G by iteratively adding edges according to three rules. Its time complexity is O(n5), where n is the number of operations in the trace. Third, we present an improved VPC-MU algorithm, called READ-CENTRIC, with time complexity O(n4). Basically it attempts to construct the operation graph G in an incremental and efficient way. Its correctness is based on that of RW-CLOSURE. Finally, we prove that VPC-SD (so is VPC-MD) is NP-complete by reducing the strongly NP-complete problem 3-PARTITION to it.

Index Terms—Consistency, PRAM, Replication, Verification.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: