Abstract
The obstruction-free progress condition is weaker than previous nonblocking progress conditions such as lock-freedom and wait-freedom, and admits simpler implementations that are faster in the uncontended case. Pragmatic contention management techniques appear to be effective at facilitating progress in practice, but, as far as we know, none guarantees progress.
We present a transformation that converts any obstruction-free algorithm into one that is wait-free when analyzed in the unknown-bound semisynchronous model. Because all practical systems satisfy the assumptions of the unknown-bound model, our result implies that, for all practical purposes, obstruction-free implementations can provide progress guarantees equivalent to wait-freedom. Our transformation preserves the advantages of any pragmatic contention manager, while guaranteeing progress.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, A., Cherian, M.: Adaptive backoff synchronization techniques. In: Proceedings of the 16th International Symposium on Computer Architecture, May 1989, pp. 396–406 (1989)
Alur, R., Attiya, H., Taubenfeld, G.: Time-adaptive algorithms for synchronization. SIAM J. Comput. 26(2), 539–556 (1997)
Arora, N.S., Blumofe, R.D., Plaxton, C.G.: Thread scheduling for multiprogrammed multiprocessors. Theory of Computing Systems 34(2), 115–144 (2001)
Aspnes, J., Herlihy, M., Shavit, N.: Counting networks. Journal of the ACM 41(5), 1020–1048 (1994)
Attiya, H., Mavronicolas, M.: Efficiency of semisynchronous versus asynchronous networks. Math. Syst. Theory 27(6), 547–571 (1994)
Burns, J.E., Lynch, N.A.: Bounds on shared memory for mutual exclusion. Information and Computation 107(2), 171–184 (1993)
Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225–267 (1996)
Chase, D., Lev, Y.: Dynamic circular work-stealing deque. In: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 21–28. ACM Press, New York (2005)
Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)
Fischer, M.: Personal communication with Leslie Lamport (June 1985)
Fischer, M., Lynch, N., Paterson, M.: Impossibility of distributed consensus with one faulty process. Journal of the ACM, 374–382 (1985)
Gafni, E., Lamport, L.: Disk Paxos. In: Herlihy, M.P. (ed.) DISC 2000. LNCS, vol. 1914, pp. 330–344. Springer, Heidelberg (2000)
Gafni, E., Mitzenmacher, M.: Analysis of timing-based mutual exclusion with random times. In: PODC 1999: Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing, pp. 13–21. ACM Press, New York (1999)
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, pp. 258–264. ACM Press, New York (2005)
Herlihy, M.: Wait-free synchronization. ACM Transactions on Programming Languages and Systems 13(1), 124–149 (1991)
Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: Proc. 23rd International Conference on Distributed Computing Systems (2003)
Herlihy, M., Luchangco, V., Moir, M.: Space- and time-adaptive nonblocking algorithms. In: Proceedings of Computing: The Australasian Theory Symposium, CATS (2003)
Herlihy, M., Luchangco, V., Moir, M., Scherer III, W.N.: Software transactional memory for supporting dynamic-sized data structures. In: Proc. 22nd Annual ACM Symposium on Principles of Distributed Computing, pp. 92–101 (2003)
Lo, W.-K., Hadzilacos, V.: Using failure detectors to solve consensus in asynchronous shared-memory systems (extended abstract). In: Tel, G., Vitányi, P.M.B. (eds.) WDAG 1994. LNCS, vol. 857, pp. 280–295. Springer, Heidelberg (1994)
Loui, M.C., Abu-Amara, H.H.: Memory requirements for agreement among unreliable asynchronous processes. In: Preparata, F.P. (ed.) Advances in Computing Research, vol. 4, pp. 163–183. JAI Press, Greenwich (1987)
Luchangco, V., Moir, M., Shavit, N.: Nonblocking k-compare-single-swap. In: SPAA 2003: Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 314–323. ACM Press, New York (2003)
Lynch, N., Shavit, N., Shvartsman, A., Touitou, D.: Timing conditions for linearizability in uniform counting networks. Theor. Comput. Sci. 220(1), 67–91 (1999)
Lynch, N.A., Shavit, N.: Timing-based mutual exclusion. In: IEEE Real-Time Systems Symposium, pp. 2–11. IEEE Press, Los Alamitos (1992)
Mavronicolas, M., Papatriantafilou, M., Tsigas, P.: The impact of timing on linearizability in counting networks. In: IPPS 1997: Proceedings of the 11th International Symposium on Parallel Processing, pp. 684–688. IEEE Computer Society, Los Alamitos (1997)
Michael, M., Scott, M.: Nonblocking algorithms and preemption-safe locking on multiprogrammed shared-memory multiprocessors. Journal of Parallel and Distributed Computing 51(1), 1–26 (1998)
Scherer III, W.N., Scott, M.L.: Contention management in dynamic software transactional memory. In: Moir, M., Shavit, N. (eds.) Proceedings of Workshop on Concurrency and Sycnhronization in Java Programs (July 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, pp. 240–248. ACM Press, New York (2005)
Treiber, R.K.: Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center (April 1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fich, F.E., Luchangco, V., Moir, M., Shavit, N. (2005). Obstruction-Free Algorithms Can Be Practically Wait-Free. In: Fraigniaud, P. (eds) Distributed Computing. DISC 2005. Lecture Notes in Computer Science, vol 3724. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11561927_8
Download citation
DOI: https://doi.org/10.1007/11561927_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29163-3
Online ISBN: 978-3-540-32075-3
eBook Packages: Computer ScienceComputer Science (R0)