Long-lived adaptive collect with applications

Abstract

A distributed algorithm is adaptive if the worst case step complexity of its operations is bounded by a function of the number of processes that are concurrently active during the operation (rather than a function of N, the total number of processes, which is usually much larger). We present long-lived and adaptive algorithms for collect in the read/write shared-memory model. Replacing the reads and writes in long-lived shared memory algorithms with our adaptive collect results in many cases in a corresponding long-lived algorithm which is adaptive. Examples of such applications, which are discussed are atomic-snapshots, and l-exclusion. Following the long-lived and adaptive collect we present a more pragmatic version of collect, called active set. This algorithm is slightly weaker than the collect but has several advantages. We employ this algorithm to transform algorithms, such as the Bakery algorithm, into their corresponding adaptive long-lived version, which is more efficient than the version that was obtained with the collect. Previously, long-lived and adaptive algorithms in this model were presented only for the renaming problem.