Brief Announcement: Readers of Wait-Free Unbounded Registers Must Write
Brief Announcement: Readers of Wait-Free Unbounded Registers Must Write
复制标题
简短公告：无等待无界寄存器的读者必须写入
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
E. Ruppert
中科院分区：
文献类型：
--
作者：
E. Ruppert
从较弱的读/写寄存器实现更强的读/写寄存器是分布式计算理论中的一个经典问题。在一些这样的实现中，所实现的读操作具有不必写入实现中使用的基址寄存器的期望特性。在其他情况下，已经证明实现不能具有此属性。在这里，我们描述了后一种类型的新颖结果。尽管可以在读取而不是写入的情况下构建无界寄存器的无锁实现，但我们表明，在从有界寄存器实现无界寄存器的任何无等待实现中，所实现的读取操作必须写入共享内存。
Implementing stronger read/write registers from weaker ones is a classical problem in the theory of distributed computing. In some such implementations, implemented read operations have the desirable property of not having to write to the base registers used in the implementation. In other cases, it has been proved that implementations cannot have this property. Here, we describe a novel result of the latter type. Although a lock-free implementation of an unbounded register can be built where reads do not write, we show that in any wait-free implementation of unbounded registers from bounded registers, the implemented read operations must write to shared memory.