We explore efficient implementations of shared data structures in an asynchronous message-passing system. Considering the Queue data type, we know that Dequeue is inherently expensive. We consider ways to circumvent this performance limitation. Though we cannot improve the worst-case time per operation instance, we show that relaxation, weakening the ordering guarantees of the Queue data type, allows most Dequeue instances to return after only local computation, giving a low amortized cost per instance. Adjusting the degree of relaxation gives a customizable tradeoff between the ordering of data and the speed of access.