Improved Time Bounds for Linearizable Implementations of Abstract Data Types Conference Paper uri icon

abstract

  • Linearizability is a well-known consistency condition for shared objects in concurrent systems. We focus on the problem of implementing linearizable objects of arbitrary data types in message-passing systems with bounded, but uncertain, message delay and bounded, but non-zero, clock skew. We present an algorithm that exploits axiomatic properties of different operations to reduce the running time of each operation below that obtainable with previously known algorithms. We also prove lower bounds on the time complexity of various kinds of operations, specified by the axioms they satisfy, resulting in reduced gaps in some cases and tight bounds in others. 2014 IEEE.

name of conference

  • 2014 IEEE 28th International Parallel and Distributed Processing Symposium

published proceedings

  • 2014 IEEE 28TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM

author list (cited authors)

  • Wang, J., Talmage, E., Lee, H., & Welch, J. L.

complete list of authors

  • Wang, Jiaqi||Talmage, Edward||Lee, Hyunyoung||Welch, Jennifer L

publication date

  • January 1, 2014 11:11 AM