• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Verifying Pipelined-RAM Consistency over Read/Write Traces of Data Replicas
【24h】

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

机译：在数据副本的读/写迹线上验证流水线式RAM一致性

获取原文
获取原文并翻译 | 示例
       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 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 -complete (so is VPC-MD) by reducing the strongly -complete problem to it. For VPC-MU, we present the algorithm with time complexity , where 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 expe- iments have demonstrated its practical efficiency and scalability.
机译：分布式存储系统中的数据复制技术引入了数据一致性问题。为了获得高性能，数据复制系统通常会适应弱一致性模型，例如流水线RAM一致性。为了确定数据复制系统是否提供Pipelined-RAM一致性，我们研究了读/写跟踪（简称VPC）过多的问题。根据是否存在多个共享变量（或一个单一变量）以及写入操作是否可以分配重复值（或仅）来识别VPC的四个变体（标记为VPC-SU，VPC-MU，VPC-SD和VPC-MD）每个共享变量的唯一值）。通过减少强完全问题，我们证明了VPC-SD是完全的（VPC-MD也是如此）。对于VPC-MU，我们提出的算法具有时间复杂度，其中表示操作数。该算法通过迭代应用规则来构造操作图，该规则保证以后不会读取任何覆盖的值。它逐个增量地处理所有读取操作，并利用同一变量的命令写入之间的总顺序来避免规则的重复应用。实验证明了其实用的效率和可扩展性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号