Lower bounds for wait-free computation in message-passing systems
Maurice P. Herlihy, Mark R. Tuttle · 1990
We explore the time complexity of waitfree implementations of concurrent objects in synchronous, message-passing systems.Our technique is to reduce the (difficult) problem of analyzing all possible wait-free implementations for a particular object to the (more tractable) problem of analyzing a related decision problem.The decision problem we consider is strong renaming, in which an arbitrary subset of m out of n processors choose unique names in the range 1 . ..m,where m is not known in advance.We prove tight log m bounds on the number of rounds of communication needed to solve this renaming problem.As a result, we derive corresponding lower bounds for wait-free implementations of a variety of objects such as stacks, queues, priority queues, and fetch&add registers, as well as for decision problems such as &assignment and order-preserving renaming.Conversely, we show how a particular strong renaming algorithm can be transformed into an O(rn+fc) implementation of an object called an increment register, a substantial improvement over conventional O(n) techniques.Our results suggest the existence of a nontrivial complexity hierarchy for wait-free implementations of concurrent objects.