Efficient Adaptive Collect using Randomization \Lambda

Abstract An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractivefor 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 com-plexity 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