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

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

authors

• Lee, Hyunyoung
• Welch, Jennifer

published proceedings

• 2014 IEEE 28TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM

author list (cited authors)

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

citation count

• 12

complete list of authors

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

publication date

• May 2014

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• Proceedings of the International Parallel and Distributed Processing Symposium, IPDPS  Journal

keywords

• Abstract Data Types
• Distributed Computing
• Linearizability
• Time Bounds

Digital Object Identifier (DOI)

• 10.1109/IPDPS.2014.77

International Standard Book Number (ISBN) 13

• 9780769552071

start page

• 691

end page

• 701

URL

• http%3A%2F%2Fdx.doi.org%2F10.1109%2Fipdps.2014.77