Nontrivial and universal helping for wait-free queues and stacks

The other approach formalizes the helping mechanism employed by Herlihy's universal wait-free construction and is based on having an operation by one process restrict the possible linearizations of operations by other processes. We show that queue and stack implementations possessing such universal helping can be used to solve consensus. This result can be used to show that a strongly linearizable (Golab et al., 2011) implementation of a queue or a stack for n processes must use objects that allow to solve consensus among n or more processes.