Adaptive wait-free algorithms for lattice agreement and renaming (extended abstract)
Hagit Attiya, Arie Fouren · 1998
) Hagit Attiya and Arie Fouren Department of Computer Science The Technion, Haifa 32000, Israel Abstract This paper considers wait-free algorithms whose complexity is constant in the absence of contention, and grows gradually as the number of active processes increases. An algorithm is fast if its complexity depends on the maximal number of active processes, K, and not on the total number of processes in the system, n. An algorithm is adaptive if its complexity depends only on the actual number of active processes, k, which is unknown in advance and may change in different executions of the algorithm. It is shown that two important decision problems, lattice agreement and renaming with linear name space, have adaptive solutions using only read and write operations. An O(k log k) adaptive algorithm for lattice agreement and an O(k log k) adaptive algorithm for (6k \\Gamma 1)-renaming are presented. These algorithms are constructed from several subalgorithms, which are interesting in t...