Nontrivial and universal helping for wait-free queues and stacks

Afek, 1993, Atomic snapshots of shared memory, J. ACM, 40, 873, 10.1145/153724.153741 Afek, 2007, Common2 extended to stacks and unbounded concurrency, Distrib. Comput., 20, 239, 10.1007/s00446-007-0023-3 Y. Afek, E. Weisberger, H. Weisman, A completeness theorem for a class of synchronization objects, in: 12th ACM Symposium on Principles of Distributed Computing, PODC, 1993, pp. 159–170. K. Censor-Hillel, E. Petrank, S. Timnat, Help! in: ACM Symposium on Principles of Distributed Computing, PODC, 2015, pp. 241–250. M. David, A single-enqueuer wait-free queue implementation, in: 18th International Conference on Distributed Computing, DISC, 2004, pp. 132–143. David, 2004 M. David, A. Brodsky, F.E. Fich, Restricted stack implementations, in: 19th International Conference on Distributed Computing, DISC, 2005, pp. 137–151. O. Denysyuk, P. Woelfel, Wait-freedom is harder than lock-freedom under strong linearizability, in: 29th International Conference on Distributed Computing, DISC, 2015, pp. 60–74. Eisenstat, 2008, A two-enqueuer queue, CoRR, abs/0805.0444 P. Fatourou, N.D. Kallimanis, The redblue adaptive universal constructions, in: 23rd International Conference on Distributed Computing, DISC, 2009, pp. 127–141. P. Fatourou, N.D. Kallimanis, A highly-efficient wait-free universal construction, in: 23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, 2011, pp. 325–334. W. Golab, L. Higham, P. Woelfel, Linearizable implementations do not suffice for randomized distributed computation, in: 43rd ACM Symposium on Theory of Computing, STOC, 2011, pp. 373–382. M. Helmi, L. Higham, P. Woelfel, Strongly linearizable implementations: Possibilities and impossibilities, in: ACM Symposium on Principles of Distributed Computing, PODC, 2012, pp. 385–394. D. Hendler, N. Shavit, Operation-valency and the cost of coordination, in: 22nd ACM Symposium on Principles of Distributed Computing, PODC, 2003, pp. 84–91. Herlihy, 1991, Wait-free synchronization, ACM Trans. Program. Lang. Syst., 13, 124, 10.1145/114005.102808 Herlihy, 2008 Herlihy, 1990, Linearizability: A correctness condition for concurrent objects, ACM Trans. Program. Lang. Syst., 12, 463, 10.1145/78969.78972 A. Kogan, E. Petrank, A methodology for creating fast wait-free data structures, in: 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, 2012, pp. 141–150. Li, 2001 S. Timnat, E. Petrank, A practical wait-free simulation for lock-free data structures, in: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, 1993, pp. 357–368.