Abstract
It is considered good practice in concurrent computing to devise shared object implementations that ensure a minimal obstruction-free progress property and delegate the task of boosting liveness to independent generic oracles called contention managers. This paper determines necessary and sufficient conditions to implement wait-free and non-blocking contention managers, i.e., contention managers that ensure wait-freedom (resp. non-blockingness) of any associated obstruction-free object implementation. The necessary conditions hold even when universal objects (like compare-and-swap) or random oracles are available in the implementation of the contention manager. On the other hand, the sufficient conditions assume only basic read/write objects, i.e., registers. We show that failure detector \(\lozenge{\fancyscript{P}}\) is the weakest to convert any obstruction-free algorithm into a wait-free one, and Ω *, a new failure detector which we introduce in this paper, and which is strictly weaker than \(\lozenge\fancyscript{P}\) but strictly stronger than Ω, is the weakest to convert any obstruction-free algorithm into a non-blocking one. We also address the issue of minimizing the overhead imposed by contention management in low contention scenarios. We propose two intermittent failure detectors \(I_{\Omega^*}\) and \(I_{\lozenge\fancyscript{P}}\) that are in a precise sense equivalent to, respectively, Ω * and \(\lozenge\fancyscript{P}\), but allow for reducing the cost of failure detection in eventually synchronous systems when there is little contention. We present two contention managers: a non-blocking one and a wait-free one, that use, respectively, \(I_{\Omega^*}\) and \(I_{\lozenge\fancyscript{P}}\). When there is no contention, the first induces very little overhead whereas the second induces some non-trivial overhead. We show that wait-free contention managers, unlike their non-blocking counterparts, impose an inherent non-trivial overhead even in contention-free executions.
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.: Stable leader election. In: Proceedings of the International Symposium on Distributed Computing (DISC) (2001)
Attiya, H., Guerraoui, R., Kouznetsov, P.: Computing with reads and writes in the absence of step contention. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC) (2005)
Attiya H. and Welch J.L. (2004). Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley, New York
Bershad, B.N.: Practical considerations for non-blocking concurrent objects. In: Proceedings of the 14th IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 264–273 (1993)
Boichat, R., Dutta, P., Frølund, S., Guerraoui, R.: Deconstructing Paxos. ACM SIGACT News Distributed Computing Column 34(1), 47–67 (2003). Revised version of EPFL Technical Report 200106, January 2001
Chandra T.D., Hadzilacos V. and Toueg S. (1996). The weakest failure detector for solving consensus. J. ACM 43(4): 685–722
Chandra T.D. and Toueg S. (1996). Unreliable failure detectors for reliable distributed systems. J. ACM 43(2): 225–267
Dwork C., Lynch N.A. and Stockmeyer L.J. (1988). Consensus in the presence of partial synchrony. J. ACM 35(2): 288–323
Fetzer, C., Raynal, M., Tronel, F.: An adaptive failure detection protocol. In: Proceedings of the 2001 Pacific Rim International Symposium on Dependable Computing (2001)
Fich, F., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free algorithms can be practically wait-free. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC) (2005)
Fischer M.J., Lynch N.A. and Paterson M.S. (1985). Impossibility of distributed consensus with one faulty process. J. ACM 32(3): 374–382
Gafni E. and Lamport L. (2003). Disk Paxos. Distrib. Comput. 1(16): 1–20
Guerraoui, R.: Indulgent algorithms. In: Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2000)
Guerraoui, R., Herlihy, M., Kapałka, M., Pochon, B.: Robust contention management in software transactional memory. In: Proceedings of the Workshop on Synchronization and Concurrency in Object-Oriented Languages (SCOOL); in conjunction with the ACM Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA) (2005)
Guerraoui, R., Herlihy, M., Pochon, B.: Polymorphic contention management. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC). LNCS, pp. 303–323. Springer, Heidelberg (2005)
Guerraoui, R., Herlihy, M., Pochon, B.: Toward a theory of transactional contention managers. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2005)
Guerraoui, R., Schiper, A.: “Γ-accurate” failure detectors. In: Proceedings of the 10th International Workshop on Distributed Algorithms (WDAG). Springer, Heidelberg (1996)
Herlihy M. (1991). Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1): 124–149
Herlihy, M., Luchangco, V., Moir, M., Scherer III, W.N.: Software transactional memory for dynamic-sized data structures. In: Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 92–101 (2003)
Herlihy, M., Luchango, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 522–529 (2003)
Herlihy M. and Wing J.M. (1990). Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3): 463–492
Jayanti P. (1997). Robust wait-free hierarchies. J. ACM 44(4): 592–614
LaMarca, A.: A performance evaluation of lock-free synchronization protocols. In: Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 130–140 (1994)
Lamport L. (1998). The part-time parliament. ACM Trans. Comput. Syst. 16(2): 133–169
Larrea M., Fernández A. and Arévalo S. (2004). On the implementation of unreliable failure detectors in partially synchronous systems. IEEE Trans. Comput. 53(7): 815–828
Moir, M., Anderson, J.H.: Wait-free algorithms for fast, long-lived renaming. Sci. Comput. Program. 25 (1995)
Scherer III, W.N., Scott, M.L.: Contention management in dynamic software transactional memory. In: Proceedings of the Workshop on Concurrency and Synchronization in Java Programs; in conjunction with the 23th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2004)
Scherer III, W.N., Scott, M.L.: Advanced contention management for dynamic software transactional memory. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is a revised and extended version of a paper with the same title in the Proceedings of the 20th International Symposium on Distributed Computing (DISC’06).
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License ( https://creativecommons.org/licenses/by-nc/2.0 ), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Guerraoui, R., Kapałka, M. & Kouznetsov, P. The weakest failure detectors to boost obstruction-freedom. Distrib. Comput. 20, 415–433 (2008). https://doi.org/10.1007/s00446-007-0046-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-007-0046-9