Summary.
In a shared-memory distributed system, n independent asynchronous processes communicate by reading and writing to shared variables. An algorithm is adaptive (to total contention) if its step complexity depends only on the actual number, k, of active processes in the execution; this number is unknown in advance and may change in different executions of the algorithm. Adaptive algorithms are inherently wait-free, providing fault-tolerance in the presence of an arbitrary number of crash failures and different processes' speed.
A wait-free adaptive collect algorithm with O(k) step complexity is presented, together with its applications in wait-free adaptive alg orithms for atomic snapshots, immediate snapshots and renaming.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: August 1999 / Accepted: August 2001
Rights and permissions
About this article
Cite this article
Attiya, H., Fouren, A. & Gafni, E. An adaptive collect algorithm with applications. Distrib Comput 15, 87–96 (2002). https://doi.org/10.1007/s004460100067
Issue Date:
DOI: https://doi.org/10.1007/s004460100067