James Aspnes and Faith Ellen. Tight bounds for adopt-commit objects. Theory of Computing Systems 55(3):451-474. (SPAA 2011 special issue). An earlier version appeared in 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, June 2011, pp. 317–324, under the title “Tight bounds for anonymous adopt-commit objects.”
We give matching upper and lower bounds of Θ(min(log m / log log m, n)) for the 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 conflict detectors.
Our anonymous lower bound also applies to the individual step complexity of m-valued wait-free anonymous consensus, even for randomized algorithms with global coins against an oblivious adversary. The upper bound can be used to slightly improve the cost of randomized consensus in an oblivious-adversary model.
For deterministic non-anonymous implementations of adopt-commit objects, we show a lower bound of Ω(min(log m / log log m, sqrt(log n) / log log n) and an upper bound of O(min(log m / log log m, log n) on the worst-case individual step complexity. For randomized non-anonymous implementations, we show that any execution contains at least one process whose steps exceed the deterministic lower bound.
@article{AspnesE2014,
year={2014},
issn={1432-4350},
journal={Theory of Computing Systems},
volume={55},
number={3},
doi={10.1007/s00224-013-9448-1},
title={Tight Bounds for Adopt-Commit Objects},
url={https://dx.doi.org/10.1007/s00224-013-9448-1},
publisher={Springer US},
keywords={Distributed computing; Shared memory; Anonymity; Lower bounds; Covering argument; Adopt-commit; Randomized consensus},
author={Aspnes, James and Ellen, Faith},
pages={451--474},
language={English}
}