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

Hengfeng Wei, Marzio De Biasi, Yu Huang, Jiannong Cao, Jian Lu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

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.
Original languageEnglish
Article number7152941
Pages (from-to)1511-1523
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Volume27
Issue number5
DOIs
Publication statusPublished - 1 May 2016

Keywords

  • consistency model
  • Pipelined-RAM
  • verification

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this