Strongly linearizable implementations: possibilities and impossibilities
Strongly linearizable implementations: possibilities and impossibilities
复制标题
强线性化实现：可能性和不可能性
DOI：
10.1145/2332432.2332508
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Philipp Woelfel
中科院分区：
文献类型：
--
作者：
Maryam Helmi;Lisa Higham;Philipp Woelfel
Herlihy 和 Wing [11] 确定，当原子对象被可线性化的实现替换时，共享内存分布式算法的可能结果集保持不变。从那时起，线性化就成为分布式算法设计者选择的正确性条件。然而，2011 年，Golab、Higham 和 Woelfel [9] 表明，如果算法采用随机化，那么原子版本和实现版本之间可能结果集的概率分布可能会有所不同。他们还证明，当随机算法处于自适应对手的控制下时，称为强线性化的更强条件对于保证这两种情况具有相同的概率分布是必要且充分的。因此，我们有动力尽可能构建常见分布式对象的强线性化实现。在本文中我们证明
• 对于包括多写入器寄存器、最大寄存器、快照和计数器在内的多个对象，多读取器/单写入器原子寄存器没有强线性化、非阻塞实现，尽管这些对象中的每一个都有满足更强的无等待进度要求的线性化实现。
• 对于来自多读取器/单写入器原子寄存器的任何对象，存在通用的强线性化、无阻塞实现。
• 存在来自多读取器/多写入器原子寄存器的有界最大寄存器的强线性化无等待实现。
Herlihy and Wing [11] established that the set of possible outcomes of a shared memory distributed algorithm remains unchanged when atomic objects are replaced by their linearizable implementations. Since then, linearizability has been the correctness condition of choice for distributed algorithm designers. In 2011, however, Golab, Higham and Woelfel [9] showed that, if an algorithm employs randomization, then the probability distribution over the set of possible outcomes can differ between the atomic and implemented versions. They also proved that a stronger condition, called strong linearizability, is necessary and sufficient to guarantee the same probability distributions for these two cases when the randomized algorithm is under the control of an adaptive adversary. Therefore, we are motivated to construct strongly linearizable implementations of common distributed objects whenever possible. In this paper we prove
• for several objects including multi-writer registers, max-registers, snapshots, and counters there is no strongly linearizable, non-blocking implementation from multi-reader/single-writer atomic registers, even though each of these objects has a linearizable implementation meeting the stronger wait-free progress requirement.
• There is a universal strongly linearizable obstruction-free implementation of any object from multi-reader/single-writer atomic registers.
• There is a strongly linearizable wait-free implementation of bounded max-registers from multi-reader/multi-writer atomic registers.