Time and Space Lower Bounds for Implementations Using k-CAS

This paper presents lower bounds on the time- and space-complexity of implementations that use the

k

compare-and-swap (

k

-CAS) synchronization primitives. We prove that the use of

k

-CAS primitives cannot improve neither the time- nor the space-complexity of implementations of widely-used concurrent objects, such as counter, stack, queue, and collect. Surprisingly, the use of

k

-CAS may even

increase

the space complexity required by such implementations.

We prove that the worst-case

average

number of steps performed by processes for any

n

-process implementation of a counter, stack or queue object is Ω(log

k

 + 1

n

), even if the implementation can use

j

-CAS for

j

≤

k

. This bound holds even if a

k

-CAS operation is allowed to

read

the

k

values of the objects it accesses and return these values to the calling process. This bound is tight.

We also consider more realistic

non-readingk

-CAS primitives. An operation of a non-reading

k

-CAS primitive is only allowed to return a success/failure indication. For implementations of the

collect

object that use such primitives, we prove that the worst-case average number of steps performed by processes is Ω(log

2

n

), regardless of the value of

k

. This implies a

round complexity

lower bound of Ω(log

2

n

) for such implementations. As there is an

O

(log

2

n

) round complexity implementation of collect that uses only reads and writes, these results establish that non-reading

k

-CAS is no stronger than read and write for collect implementation round complexity.

We also prove that

k

-CAS does not improve the space complexity of implementing many objects (including counter, stack, queue, and single-writer snapshot). An implementation has to use at least

n

base objects even if

k

-CAS is allowed, and if all operations (other than read) swap exactly

k

base objects, then the space complexity must be at least

k

·

n

.