Anomalies and Similarities Among Consensus Numbers of Variously-Relaxed Queues

摘要

Shared data structures are a basic building block in distributed computing, but can be expensive to implement. One way to circumvent the high implementation cost of linearizability is to relax the sequential specification of the data type. This gives up some guarantees, for instance on the ordering of data elements, as a tradeoff against performance. We want to explore the effects of this tradeoff on the computational power of the shared data structures. In this paper, we characterize the effects of three different types of relaxation, chosen from the literature, on the computational power of FIFO queues. By parametrically relaxing each of the three operations on a queue (Enqueue, Dequeue, Peek), we obtain an infinite 3-dimensional space for each type of relaxation. We find the consensus number, a standard measure of the computational power of shared data types, of each point in these spaces, completely describing the effect of these three types of relaxation on the computational power of queues.