• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Reading many variables in one atomic operation: solutions with linear or sublinear complexity
【24h】

Reading many variables in one atomic operation: solutions with linear or sublinear complexity

机译：在一个原子操作中读取许多变量：具有线性或亚线性复杂性的解决方案

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

摘要

We address the problem of reading several variables (components) X/sub 1/,...,X/sub c/, all in one atomic operation, by only one process, called the reader, while each of these variables are being written by a set of writers. All operations (i.e., both reads and writes) are assumed to be totally asynchronous and wait-free. For this problem, only algorithms that require at best quadratic time and space complexity can be derived from the existing literature. (The time complexity of a construction is the number of suboperations of a high-level operation and its space complexity is the number of atomic shared variables it needs) In this paper, we provide a deterministic protocol that has linear (in the number of processes) space complexity, linear time complexity for a read operation, and constant time complexity for a write. Our solution does not make use of time-stamps. Rather, it is the memory location where a write writes that differentiates it from the other writes. Also, introducing randomness in the location where the reader gets the value that it returns, we get a conceptually very simple probabilistic algorithm. This algorithm has an overwhelmingly small, controllable probability of error. Its space complexity, and also the time complexity of a read operation, are sublinear. The time complexity of a write is constant. On the other hand, under the Archimedean time assumption, we get a protocol whose time and space complexity do not depend on the number of writers, but are linear in the number of components only. (The time complexity of a write operation is still constant.).
机译：我们解决了仅通过一个称为读取器的过程在一个原子操作中读取多个变量（组件）X / sub 1 /，...，X / sub c /的问题，而每个变量都在编写时由一组作家。所有操作（即读和写）均假定为完全异步且无需等待。对于此问题，只能从现有文献中得出最高需要二次时间和空间复杂度的算法。 （构造的时间复杂度是高级操作的子操作数，其空间复杂度是它需要的原子共享变量的数目）在本文中，我们提供了具有线性（在过程数中）的确定性协议）空间复杂度，读取操作的线性时间复杂度和写入操作的恒定时间复杂度。我们的解决方案不使用时间戳。相反，是写操作将其与其他写操作区分开的存储位置。同样，在读者获得返回值的位置引入随机性，我们得到了概念上非常简单的概率算法。该算法具有极小的可控错误概率。它的空间复杂度以及读取操作的时间复杂度是次线性的。写入的时间复杂度是恒定的。另一方面，在阿基米德时间假设下，我们得到了一个协议，该协议的时间和空间复杂度不依赖于编写者的数量，而是仅线性于组件数。 （写操作的时间复杂度仍然恒定。）

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号