Linearizable Relaxations of Stacks and their Generalizations to Ordered Data Structures

Relaxation of semantics is a technique for improving the amortized distributed time complexity of data structures. We exhibit the first known algorithms implementing linearizable relaxed stacks in a partially synchronous, message-passing system, and proceed to show that relaxed priority queues reduce to relaxed stacks, meaning that their implementations are equally as fast in terms of amortized performance. Furthermore, restricting these new algorithms to relaxed queues improves on the previously best known upper bounds.Undergraduat