论文标题
关于线性性和随机算法的终止
On Linearizability and the Termination of Randomized Algorithms
论文作者
论文摘要
我们研究了当算法用可线化（实现）寄存器使用的原子寄存器时，是否保留了随机算法的“终止概率1”属性的问题。我们表明，通常情况并非如此：粗略地说，每个随机算法A具有相应的算法A'，如果使用原子或强可连接的寄存器，则可以解决相同的问题，但如果这些寄存器仅由“仅是”线性化的寄存器替换，则不会终止。加上[15]中显示的先前结果，这意味着人们不能使用众所周知的ABD在消息通讯系统中的寄存器实现来自动将在共享记忆系统中起作用的任何随机算法转换为在消息传播系统中起作用的随机算法：具有强大的对手的逆向算法可能无法终止。
We study the question of whether the "termination with probability 1" property of a randomized algorithm is preserved when one replaces the atomic registers that the algorithm uses with linearizable (implementations of) registers. We show that in general this is not so: roughly speaking, every randomized algorithm A has a corresponding algorithm A' that solves the same problem if the registers that it uses are atomic or strongly-linearizable, but does not terminate if these registers are replaced with "merely" linearizable ones. Together with a previous result shown in [15], this implies that one cannot use the well-known ABD implementation of registers in message-passing systems to automatically transform any randomized algorithm that works in shared-memory systems into a randomized algorithm that works in message-passing systems: with a strong adversary the resulting algorithm may not terminate.
