  In this paper, we first propose a new liveness requirement for shared objects
and data structures, we then give a shared queue algorithm that satisfies this
requirement and we prove its correctness. We also implement this algorithm and
compare it to a well-known shared queue algorithm that is used in practice. In
addition to having a stronger worst-case progress guarantee, our experimental
results suggest that, at the cost of a marginal decrease in throughput, our
algorithm is significantly fairer, by a natural definition of fairness that we
introduce here.
