Data replication technologies enable efficient and highly-available data access, thus gaining more and more interests in both the academia and the industry. However, it introduces the problem of data consistency. For high performance and availability, modern data replication systems often settle for weak consistency. Pipelined-RAM consistency is one of the wellknown weak consistency models. It does not require all the replicas to agree on the same global view of the order in which data operations occur. To determine whether a data replication system indeed provides Pipelined-RAM consistency, we study the problem of verifying Pipelined-RAM consistency over read/write traces (VPC, for short). We identify four variants of VPC according to a) whether write operations can assign Duplicate values (or only Unique values) for each shared variable, and b) whether there are Multiple shared variables (or one Single variable); the four variants are labeled VPC-SU, VPC-MU, VPC-SD, and VPC-MD.

For the VPC problem, all read operations are totally ordered on the same process p0. It turns out that the VPC problem is NP-complete if write operations can assign duplicate values for each shared variable. In contrast, it is polynomially tractable if only unique values are allowed. Specifically, we prove that VPC-SD is NP-complete (so is VPC-MD) by reducing the strongly NP-complete problem 3-PARTITION to it. On the other hand, we present a polynomial algorithm, called READCENTRIC, for the VPC-MU variant. The READ-CENTRIC algorithm constructs an operation graph by iteratively applying a rule which guarantees that no overwritten values are allowed to be read. It makes use of the total order between the dictating writes on the same variable to avoid redundant applications of the rule, achieving the time complexity of O(n4), where n is the number of operations in the trace. Moreover, the READ-CENTRIC algorithm is incremental in the way that it processes all the read operations on process p0 – ne by one. The experiments have demonstrated its practical efficiency and scalability.