Volume 1999
Article 9
Published by MIT Press. Copyright 1999 Massachusetts Institute of
Technology.
Your institution may already be a
subscriber to CJTCS. If not,
please subscribe.
Time Bounds for Strong and Hybrid Consistency for Arbitrary
Abstract Data Types
Martha J. Kosa (Tennessee Technological University)
6 August 1999
Abstract
We compare the costs of three well-known consistency guarantees (seque
ntial
consistency, linearizability, and hybrid consistency) for shared memor
y objects
of arbitrary data types, generalizing previous work on specifi
c
types. We
evaluate the impact of the desired consistency guarantee, the amount
of synchrony among the users of the objects, and algebraic properties
of a type on the worst-case time complexity of
operations of the type. These algebraic properties are sufficient for
proving
many lower bounds and some upper bounds (even 0,
meaning only local computation is required) on the worst-case times.
Under
certain reasonable assumptions, sequential consistency and linearizabi
lity are
equally costly in perfectly synchronized systems, linearizable operati
ons are
more expensive in approximately synchronized systems than in perfectly
synchronized systems, sequentially consistent operations are cheaper t
han
linearizable operations in approximately synchronized systems, and hyb
rid
consistency is not necessarily cheaper than sequential consistency or
linearizability.
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Article 8
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
Article 10
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 1999
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif){kind=logo}