Improving Average Performance by Relaxing Distributed Data Structures

Springer-Verlag Berlin Heidelberg 2014. Linearizability is a powerful consistency condition but can be expensive to implement. Recently, reserarchers have suggested gaining performance by relaxing the sequential specification of objects data types. We consider, for the first time, linearizable message-passing implementations of relaxed Queues and prove upper and lower bounds on the elapsed time for Dequeue operations both in the worst case and on average.Our results imply that worst-case time complexity does not indicate benefit from relaxation. In contrast, we present implementations of relaxed Queues for which the average time complexity of Dequeue is significantly smaller than both the worst-case lower bound for unrelaxed Queues and a newly-proved lower bound on the average time for unrelaxed Queues. We also prove lower bounds on the average time complexity of Dequeue for relaxed Queues that show our algorithms are asymptotically optimal and that there is an inherent complexity gap between different levels of relaxation.

Improving Average Performance by Relaxing Distributed Data Structures Conference Paper