Please use this identifier to cite or link to this item:
Title: Verifying pipelined-RAM consistency over read/write traces of data replicas
Authors: Wei, H
De Biasi, M
Huang, Y
Cao, J 
Lu, J
Keywords: Consistency model
Issue Date: 2016
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on parallel and distributed systems, 2016, v. 27, no. 5, 7152941, p. 1511-1523 How to cite?
Journal: IEEE transactions on parallel and distributed systems 
Abstract: Data replication technologies in distributed storage systems introduce the problem of data consistency. For high performance, data replication systems often settle for weak consistency models, such as Pipelined-RAM consistency. To determine whether a data replication system provides Pipelined-RAM consistency, we study the problem of verifying Pipelined-RAM consistency over read/write traces (VPC, for short). Four variants of VPC (labeled VPC-SU, VPC-MU, VPC-SD, and VPC-MD) are identified according to whether there are Multiple shared variables (or one Single variable) and whether write operations can assign Duplicate values (or only Unique values) to each shared variable. We prove that VPC-SD is NP-complete (so is VPC-MD) by reducing the strongly NP-complete problem 3-Partition to it. For VPC-MU, we present the Read-Centric algorithm with time complexity O(n4) , where n is the number of operations. The algorithm constructs an operation graph by iteratively applying a rule which guarantees that no overwritten values can be read later. It incrementally processes all the read operations one by one, and exploits the total order between the dictating writes on the same variable to avoid redundant applications of the rule. The experiments have demonstrated its practical efficiency and scalability.
ISSN: 1045-9219
EISSN: 1558-2183
DOI: 10.1109/TPDS.2015.2453985
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Last Week
Last month
Checked on Aug 20, 2017

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.