Chicago Journal of Theoretical Computer Science

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

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.

DOI: 10.4086/cjtcs.1999.009
[] Article 8 [] Article 10
[back] Volume 1999 [back] Published articles
[CJCTS home]

Last modified: Sat Mar 20 09:32:31 CST 1999