Anomalies and Similarities Among Consensus Numbers of Variously-Relaxed Queues Conference Paper uri icon

abstract

  • Springer International Publishing AG 2017. 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, P eek), 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.

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Talmage, E., & Welch, J. L.

citation count

  • 2

complete list of authors

  • Talmage, Edward||Welch, Jennifer L

publication date

  • January 2017