Time and space lower bounds for non-blocking implementations (preliminary version)
Prasad Jayanti, King Tan, Sam Toueg · 1996
We show the following time and space complexity lower bounds.Let Z be any randomized nonbk, ;ng n-process implementation of any object in 1 from any combination of objects in set 1?, where A = {increment, store-conditional bit, compare@swap, bounded-counter, single-writer atomic snapshot, fetch~add}, and B = { resettable consensus, register, swap register}.The space complexity of ~is at least n -1.Moreover, if ~is deterministic, both its time and space complexit y are at least n -1.These lower bounds hold even if objects used in the implementation are of unbounded size.This improves on some of the C?(@) space com-plexit~lower bounds of Fich, Herlihy & Shavit [FHS93].It also shows the near optimality of Dome known wait-free implementations in terms of space complexity.