Abstract
We give matching upper and lower bounds of \(\varTheta(\min(\frac{\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 against an oblivious adversary.
For deterministic non-anonymous implementations of adopt-commit objects, we show a lower bound of \(\varOmega(\min(\frac{\log m}{\log \log m}, \frac{\sqrt{\log n}}{\log \log n}))\) and an upper bound of \(O(\min(\frac{\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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abrahamson, K.: On achieving consensus using a shared memory. In: Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 291–302 (1988)
Alistarh, D., Gilbert, S., Guerraoui, R., Travers, C.: Of choices, failures and asynchrony: the many faces of set agreement. In: Dong, Y., Du, D.Z., Ibarra, O.H. (eds.) ISAAC. Lecture Notes in Computer Science, vol. 5878, pp. 943–953. Springer, Berlin (2009)
Aspnes, J.: A modular approach to shared-memory consensus, with applications to the probabilistic-write model. In: Proceedings of the Twenty-Ninth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 460–467 (2010)
Aspnes, J., Censor, K.: Approximate shared-memory counting despite a strong adversary. In: Mathieu, C. (ed.) Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009, pp. 441–450. SIAM, Philadelphia (2009)
Aspnes, J., Fich, F.E., Ruppert, E.: Relationships between broadcast and shared memory in reliable anonymous distributed systems. Distrib. Comput. 18(3), 209–219 (2006)
Attiya, H., Censor, K.: Tight bounds for asynchronous randomized consensus. J. ACM 55(5), 20 (2008)
Attiya, H., Censor-Hillel, K.: Lower bounds for randomized consensus under a weak adversary. SIAM J. Comput. 39(8), 3885–3904 (2010)
Aumann, Y.: Efficient asynchronous consensus with the weak adversary scheduler. In: PODC’97: Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 209–218. ACM, New York (1997). doi:10.1145/259380.259441
Aumann, Y., Bender, M.A.: Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler. Distrib. Comput. 17(3), 191–207 (2005). doi:10.1007/s00446-004-0113-4
Chandra, T.D.: Polylog randomized wait-free consensus. In: Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, Pennsylvania, USA, pp. 166–175 (1996)
Cheung, L.: Randomized wait-free consensus using an atomicity assumption. In: Principles of Distributed Systems, 9th International Conference, OPODIS 2005, Pisa, Italy, December 12–14, 2005. Lecture Notes in Computer Science, vol. 3974, pp. 47–60. Springer, Berlin (2006). Revised Selected Papers
Chor, B., Israeli, A., Li, M.: Wait-free consensus using asynchronous hardware. SIAM J. Comput. 23(4), 701–712 (1994)
Fich, F., Herlihy, M., Shavit, N.: On the space complexity of randomized synchronization. J. ACM 45, 843–862 (1998). doi:10.1145/290179.290183
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985). doi:10.1145/3149.214121. http://portal.acm.org/citation.cfm?id=214121
Gafni, E.: Round-by-round fault detectors: unifying synchrony and asynchrony (extended abstract). In: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, pp. 143–152 (1998)
Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)
Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)
Loui, M.C., Abu-Amara, H.H.: Memory requirements for agreement among unreliable asynchronous processes. Adv. Comput. Res. 163–183 (1987)
Lubell, D.A.: A short proof of Sperner’s lemma. J. Comb. Theory, Ser. A 1(2), 402 (1966)
Moses, Y., Rajsbaum, S.: A layered analysis of consensus. SIAM J. Comput. 31(4), 989–1021 (2002)
Mostefaoui, A., Rajsbaum, S., Raynal, M., Travers, C.: The combined power of conditions and information on failures to solve asynchronous set agreement. SIAM J. Comput. 38(4), 1574–1601 (2008)
Peterson, G.L., Fischer, M.J.: Economical solutions for the critical section problem in a distributed system (extended abstract). In: Hopcroft, J.E., Friedman, E.P., Harrison, M.A. (eds.) Proceedings of the 9th Annual ACM Symposium on Theory of Computing, Boulder, Colorado, USA, May 4–6, 1977, pp. 91–97. ACM, New York (1977)
Acknowledgements
James Aspnes was supported in part by National Science Foundation grant CCF-0916389. Faith Ellen was supported in part by the Natural Science and Engineering Research Council of Canada.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Aspnes, J., Ellen, F. Tight Bounds for Adopt-Commit Objects. Theory Comput Syst 55, 451–474 (2014). https://doi.org/10.1007/s00224-013-9448-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-013-9448-1