PROJECT TITLE :

Verifying Pipelined-RAM Consistency over Read/Write Traces of Data Replicas

ABSTRACT:

Information replication technologies in distributed storage systems introduce the problem of information consistency. For high performance, data replication systems typically settle for weak consistency models, like Pipelined-RAM consistency. To verify whether or not a information replication system provides Pipelined-RAM consistency, we have a tendency to study the matter of verifying Pipelined-RAM consistency over browse/write traces (VPC, for short). Four variants of VPC (labeled VPC-SU, VPC-MU, VPC-SD, and VPC-MD) are identified according to whether or not there are Multiple shared variables (or one Single variable) and whether write operations will assign Duplicate values (or solely Distinctive values) to every shared variable. We prove that VPC-SD is -complete (so is VPC-MD) by reducing the strongly -complete drawback 3-Partition to it. For VPC-MU, we tend to present the Browse-Centric algorithm with time complexity , where is the amount of operations. The algorithm constructs an operation graph by iteratively applying a rule that guarantees that no overwritten values will be browse later. It incrementally processes all the scan operations one after the other, and exploits the full order between the dictating writes on the same variable to avoid redundant applications of the rule. The expe- iments have demonstrated its practical potency and scalability.