Implementing FIFO Queues and
Hagit Attiya · 1991
The cost of implementing FIFO queues and stacks is studied under two consistency conditions for shared memory multiprocessors, sequential consistency and linearizability. The cost measure is the worst-case response time in distributed implementations of virtual shared memory supporting one of the two conditions. The worst-case response time is very sensitive to the assumptions that are made about the timing information available to the system. All the results in this paper assume that processes have clocks that run at the same rate as real time and that all message delays are in the range [d - u, d] for some known constants u and d, 0 < u < d. If processes have perfectly synchronized clocks or if every message has delay exactly