Linear lower bounds on real-world implementations of concurrent objects Conference Paper uri icon


  • Abstract: This paper proves/spl Omega/(n) lower bounds on the time to perform a single instance of an operation in any implementation of a large class of data structures shared by n processes. For standard data structures such as counters, stacks, and queues, the bound is tight. The implementations considered may apply any deterministic primitives to a base object. No bounds are assumed on either the number of base objects or their size. Time is measured as the number of steps a process performs on base objects and the number of …

publication date

  • October 23, 2005