Adaptive and efficient algorithms for lattice agreement and renaming

摘要

In a shared-memory system, n independent asynchronous processes, with distinct names in the range {0,..., N-1}, communicate by reading and writing to shared registers. An algorithm is wait-free if a process completes its execution regardless of the behavior of other processes. This paper considers wait-free algorithms whose complexity adjusts to the level of contention in the system: A algorithm is adaptive (to total contention) if its step complexity depends only on the actual umber of active processes, k; this umber is unknown in advance and may change in different executions of the algorithm. Adaptive algorithms are presented for two important decision problems, lattice agreement and (6k-1)-renaming; the step complexity of both algorithms is O (k log k). An interesting component of the (6k-1)-renaming algorithm is an O(N) algorithm for (2k-1)-renaming; this improves on the best previously known (2k-1)-renaming algorithm, which has O ( Nnk) step complexity. The efficient renaming algorithm can be modified into an O (N) implementation of atomic snapshots using dynamic single-writer multi-reader registers. The best known implementations of atomic snapshots have step complexity O (N log N) using static single-writer multi-reader registers, and O (N) using multi-writer multi-reader registers. [References: 27]