Brief Announcement: How Fast Reads Affect Multi-Valued Register Simulations
Brief Announcement: How Fast Reads Affect Multi-Valued Register Simulations
复制标题
简短公告：读取速度如何影响多值寄存器模拟
DOI：
10.1145/3293611.3331580
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Welch, Jennifer L.
中科院分区：
文献类型：
--
作者：
Chaudhuri, Soma;Frank, Reginald;Welch, Jennifer L.
我们考虑的问题，模拟一个k值寄存器在一个无等待的方式使用二进制寄存器作为积木，其中k 2。我们表明，对于任何模拟使用原子二进制基址寄存器来模拟一个安全的k值寄存器，其中读取算法采取的最佳步骤数（log2k），写入算法必须采取至少log2k步骤在最坏的情况下。更不用说，当模拟寄存器应该是规则的时，同样的下限适用。以前已知的算法表明，这两个下界是紧的。我们还表明，为了模拟一个原子的k值寄存器的两个读者，读算法的最佳步骤数必须严格大于log2k。
We consider the problem of simulating a k-valued register in a wait-free manner using binary registers as building blocks, where k 2. We show that for any simulation using atomic binary base registers to simulate a safe k-valued register in which the read algorithm takes the optimal number of steps (log2k), the write algorithm must take at least log2k steps in the worst case. A fortiori, the same lower bound applies when the simulated register should be regular. Previously known algorithms show that both these lower bounds are tight. We also show that in order to simulate an atomic k-valued register for two readers, the optimal number of steps for the read algorithm must be strictly larger than log2k.