An efficient long-lived adaptive collect algorithm

Adaptive algorithms, whose step complexity adjusts to the number of actually participating processors, are attractive in distributed systems where the number of processors is highly variable. Long-lived adaptive algorithms moreover enable processors to repeatedly execute operations "from scratch", allowing for stronger forms of adaptiveness. Shared memory collect can be implemented non adaptively with step and memory complexity O(N). To date, the best known long-lived and adaptive shared memory collect algorithm has worst case step complexity O(k³) and requires O(N³) shared memory registers where k is the interval contention of a collect operation and N the number of processors in the system. Hence, if the interval contention k rises above K such that K³≫N this algorithm becomes inefficient. In this paper, we present a new long-lived, efficient, adaptive collect algorithm. Namely, our algorithm adapts to K-contention - it has the property that if during an operation the interval contention k exceeds a predetermined constant K the step complexity is O(N). If it falls below K, the processors executions eventually have adaptive step complexity of O(k³). Moreover, for K such that K3≤N our algorithm requires only O(N²) shared memory registers.