A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
复制标题
无等待计算的简单算法推理表征（扩展摘要）
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
E. Gafni
中科院分区：
文献类型：
--
作者：
E. Borowsky;E. Gafni
本文介绍了两个新的新的工具，用于分布式计算的研究，并显示其效用，使用它们来展示一个简单的推导Herlihy和Strift表征的无等待共享内存计算。第一个工具是给定模型的迭代版本的概念。我们表明，对应于迭代模型的拓扑结构具有良好的递归结构，并且原子快照内存的迭代版本解决了非迭代模型可解决的任何任务。第二个工具是迭代显式简单收敛算法。在博士学位。这些工具被用来描述比读写共享存储器更复杂的模型。
This paper introduces two new novel tools for the study of distributed computing and shows their utility by using them to exhibit a simple derivation of the Herlihy and Shavit characterization of wait-free shared-memory computation. The first tool is the notion of the iterated version of a given model. We show that the topological structure that corresponds to an iterated model has a nice recursive structure, and that the iterated version of the atomic snapshot memory solves any task solvable by the non-iterated model. The second tool is an iterated explicit simple convergence algorithm. In the Ph.D. Thesis oft he first author these tool were used to characterize models more complex than read-write shared-memory.