Technical Report CS0672

Authors: H. Attiya
PDFNot Available
Abstract: The cost of implementing FIFO queues and stacks is studied under two consistency conditions for shared memory multiprocessors, {\em sequential consistency} and {\em 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 \leq u \leq d$. If processes have perfectly synchronized clocks or if every message has delay exactly $d$, then the response time of a dequeue operation is at least $d$, for any sequentially consistent implementation of FIFO queues. This matches exactly an upper bound in which an enqueue operation is performed instantaneously and the response time of a dequeue operation is $d$; this upper bound implements linearizability. If clocks are not perfectly synchronized and if message delays are variable, i.e., $u > 0$, then for any linearizable implementation of a queue, the response time of an enqueue operation is at least $\Omega(u)$. In contrast, we present sequentially consistent implementation for this weaker timing model in which an enqueue operation is performed instantaneously, and the worst-case response time of a dequeue operation is $2d$. (This algorithm is completely asynchronous and does not rely on any timing information). Similar results are proved for implementing stacks, with the pop operation playing the role of the dequeue operation, and the push operation playing the role of the enqueue operation.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion