Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/61293
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
Pipelined-RAM
Verification
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.
URI: http://hdl.handle.net/10397/61293
ISSN: 1045-9219
EISSN: 1558-2183
DOI: 10.1109/TPDS.2015.2453985
Appears in Collections:Journal/Magazine Article

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

Page view(s)

33
Last Week
1
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



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