Efficient Adaptive Collect using Randomization



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 $\mathrm{O}(k)$ step complexity and polynomial memory overhead only. In addition we present a new deterministic collect algorithm which beats the best step complexity for previous polynomial-memory algorithms.