An adaptive collect algorithm with applications
An adaptive collect algorithm with applications
复制标题
一种自适应采集算法及其应用
DOI：
10.1007/s004460100067
复制
发表时间：
2002
影响因子：
1.3
通讯作者：
E. Gafni
中科院分区：
文献类型：
--
作者：
H. Attiya;Arie Fouren;E. Gafni
摘要在共享内存分布式系统中，n个独立的异步进程通过对共享变量进行阅读和写来进行通信。一个算法是自适应的（总竞争），如果它的步骤复杂度只取决于实际的数量，k，在执行中的活动进程;这个数字是未知的，并可能在不同的算法执行变化。自适应收集算法具有无等待特性，能够在任意数目的崩溃失败和不同进程速度的情况下提供容错能力.本文提出了一种O（k）步复杂度的无等待自适应收集算法，并给出了该算法在原子快照、立即快照和重命名等无等待自适应算法中的应用.
Summary. In a shared-memory distributed system, n independent asynchronous processes communicate by reading and writing to shared variables. An algorithm is adaptive (to total contention) if its step complexity depends only on the actual number, k, of active processes in the execution; this number is unknown in advance and may change in different executions of the algorithm. Adaptive algorithms are inherently wait-free, providing fault-tolerance in the presence of an arbitrary number of crash failures and different processes' speed.A wait-free adaptive collect algorithm with O(k) step complexity is presented, together with its applications in wait-free adaptive alg orithms for atomic snapshots, immediate snapshots and renaming.