Immediate atomic snapshots and fast renaming
Immediate atomic snapshots and fast renaming
复制标题
立即原子快照和快速重命名
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
E. Gafni
中科院分区：
文献类型：
--
作者：
E. Borowsky;E. Gafni
本文研究了一种新的共享存储模型--即时原子快照存储器。它是原子快照内存的一个扩展，其中写操作除了~vriting之外，还返回内存的原子快照。与常规原子快照不同，立即快照保证紧跟写操作。该模型以前用于获得不可能性结果。在这里，我们调查其效用的算法设计。我们首先在读写模型中实现一次性版本。然后，我们使用该模型来设计一个新的重命名算法。我们得到的重命名算法是简单的，最坏的情况下需要n个周期的一次立即快照。由于我们实现的oneshot立即快照需要0（nz）原语读写操作，我们得到一个0（n3）重命名算法。目前最好的重命名算法是指数，我们的即时快照的实现依赖于由NSF总统青年研究者奖资助DC R84-5 1396下的 * 工作的先验知识。允许免费复制本材料的全部或部分，前提是复制品不是为了直接的商业利益而制作或分发的，ACM版权声明和出版物的标题及其日期出现，并通知计算机协会允许复制。以其他方式复制或重新发布需要付费和/或特定许可。第12届ACM研讨会！分布式计算原理，IthacaNY@1993ACM0 -89791-613- 1/93/0008/0041。. ..$ 1.50要拍摄的快照数。我们无法免除这个条件，因此无法获得长寿对象的实现。
This paper investigates a new shared-memory model called immediate atomic snapshot memor~. It is an extension of atomic snapshot memory in which a write operation in addition to ~vriting, also returns an atomic snapshot of the memory. Unlike regular atomic snapshot, immediate snapshot is guaranteed to closely follow the write operation. This model was previously used to obtain an inlpossibility result. Here we investigate its utility for the design of algorithms. We first implement the one-shot version in the read-write model. We then use the model to design a new renaming algorithm. The renaming algorithm we obtain is simple and requires at worst n cycles of one-shot immediate snapshots. Since our implementation of the oneshot immediate snapshot requires 0( nz) primitive read-write operations, we obtain an 0(n3) renanling algorithm. Currently the best renaming algorithm is exponential, Our implementation of the immediate snapshot relies on a priori knowledge of the bound on the *Work supported by NSF Presidential Young Investigator Award under grant DC R84-5 1396. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and Its date appear, and notice is given thet copying ie by permissi~n of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 12th ACM Sympos!um on Principles on Distributed Computing, Ithaca NY @ 1993 ACM o-89791-613-l/93/0008/0041 . . ..$ 1.50 number of snapshots to be taken. We were not able to dispense with this condition and thus were unable to obtain an implementation of the longlived object.