Verifying PRAM Consistency over Read/Write Traces of Data Replicas

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 ar