Efficient adaptive collect using randomization
Efficient adaptive collect using randomization
复制标题
使用随机化的高效自适应收集
DOI：
10.1007/s00446-005-0143-6
复制
发表时间：
2004
影响因子：
1.3
通讯作者：
Roger Wattenhofer
中科院分区：
文献类型：
--
作者：
H. Attiya;F. Kuhn;C. Plaxton;Mirjam Wattenhofer;Roger Wattenhofer
自适应算法，其步骤的复杂性调整的活动进程的数量，是有吸引力的分布式系统具有高度可变的进程数。许多自适应算法的基石是从所有参与进程收集最新信息的自适应机制。迄今为止，所有已知的收集算法要么具有非线性的步复杂度，要么由于不切实际的存储开销而不实用，本文提出了新的具有渐近最优O（k）步复杂度和线性存储开销的随机收集算法。此外，我们提出了一个新的确定性收集算法，击败了以前的多项式记忆算法的最佳步骤复杂度。
An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractive for distributed systems with a highly-variable number of processes. The cornerstone of many adaptive algorithms is an adaptive mechanism to collect up-to-date information from all participating processes. To date, all known collect algorithms either have non-linear step complexity or they are impractical because of unrealistic memory overhead.This paper presents new randomized collect algorithms with asymptotically optimal O(k) step complexity and linear memory overhead only. In addition we present a new deterministic collect algorithm that beats the best step complexity for previous polynomial-memory algorithms.