Abstract
We introduce a simple liveness property for shared object implementations that is gracefully degrading depending on the degree of synchrony in each run. This property, called adaptive progress, provides a gradual bridge between obstruction-freedom and wait-freedom in partially-synchronous systems. We show that adaptive progress can be achieved using very weak shared objects. More precisely, every object has an implementation that ensures adaptive progress and uses only abortable registers (which are weaker than safe registers). As part of this work, we present a new leader election abstraction that processes can use to dynamically compete for leadership such that if there is at least one timely process among the current candidates for leadership, then a timely leader is eventually elected among the candidates. We also show that this abstraction can be implemented using abortable registers.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: On implementing Omega in systems with weak reliability and synchrony assumptions. Distrib. Comput. 21(4), 239–314 (2008). A preliminary version of this work appeared in the Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing, pp. 306–314. ACM, New York (2003)
Aguilera, M.K., Frolund, S., Hadzilacos, V., Horn, S.L., Toueg, S.: Abortable and query-abortable objects and their efficient implementation. In: Proceedings of the 26th ACM Symposium on Principles of Distributed Computing, pp. 23–32. ACM, New York (2007)
Aguilera, M.K., Toueg, S.: Timeliness-based wait-freedom: a gracefully degrading progress condition. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, pp. 305–314. ACM, New York (2008)
Chandra T.D., Hadzilacos V., Toueg S.: The weakest failure detector for solving consensus. J. ACM 43(4), 685–722 (1996)
Chandra T.D., Toueg S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225–267 (1996)
Dwork C., Lynch N.A., Stockmeyer L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)
Fich, F.E., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free algorithms can be practically wait-free. In: Proceedings of the 19th International Symposium on Distributed Computing, vol. 3724 of LNCS, pp. 78–92. Springer, Heidelberg (2005)
Guerraoui, R., Herlihy, M., Pochon, B.: Toward a theory of transactional contention managers. In: Proceedings of the 24th ACM Symposium on Principles of Distributed Computing, pp. 258–264. ACM, New York (2005)
Guerraoui R., Kapalka M., Kouznetsov P.: The weakest failure detectors to boost obstruction-freedom. Distrib. Comput. 20(6), 415–433 (2008)
Herlihy M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)
Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems, pp. 522–529. IEEE Computer Society, New York (2003)
Herlihy M., Wing J.: Linearizability: a correctness condition for concurrent objects. Trans. Program. Lang. Syst. 12(3), 463–492 (1990)
Lamport L.: On interprocess communication; part I: basic formalism. Distrib. Comput. 1(2), 77–85 (1986)
Lamport L.: On interprocess communication; part II: algorithms. Distrib. Comput. 1(2), 86–101 (1986)
Taubenfeld, G.: Efficient transformations of obstruction-free algorithms into non-blocking algorithms. In: Proceedings of the 21st International Symposium on Distributed Computing, vol. 4731 of LNCS, pp. 450–464. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Additional information
Research supported in part by the National Science and Engineering Research Council of Canada.
Rights and permissions
About this article
Cite this article
Aguilera, M.K., Toueg, S. Adaptive progress: a gracefully-degrading liveness property. Distrib. Comput. 22, 303–334 (2010). https://doi.org/10.1007/s00446-010-0106-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-010-0106-4