46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) Linear Lower Bounds on Real-World Implementations of Concurrent Objects Pittsburgh, Pennsylvania, USA October 23-October 25 ISBN: 0-7695-2468-0
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.47
This paper proves \Omega (\pi ) 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 (\pi ) 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 stalls it incurs as a result of contention with other processes.
Citation:
Faith Ellen Fich, Danny Hendler, Nir Shavit, "Linear Lower Bounds on Real-World Implementations of Concurrent Objects," focs, pp.165-173, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb