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 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. Partially supported by NSF Grants CCR–0310970 and ANI–0326001. A preliminary version of this paper appeared in the Proceedings of the 18th Annual Conference on Distributed Computing (DISC) 2004 10].