Tight bounds for anonymous adopt-commit objects
James Aspnes, Faith Ellen · 2011
We give matching upper and lower bounds of Θ(min(log m/log log m, n)) for the space and individual step complexity of a wait-free m-valued adopt-commit object implemented using multi-writer registers for n anonymous processes. While the upper bound is deterministic, the lower bound holds for randomized adopt-commit objects as well. Our results are based on showing that adopt-commit objects are equivalent up to small additive constants, to a simpler class of objects that we call weak conflict detectors.