Towards a complexity hierarchy of wait-free concurrent objects
S.K. Chaudhuri · 2002
The author studies the time complexity of wait-free implementations of a generalized version of consensus, the set-consensus problem, in synchronous message-passing systems. The time complexity of such characteristic problems as consensus and strong renaming have been studied earlier. These two problems seem to exist at two ends of the spectrum, one taking O(n) time, while the other has an O(logn) time complexity. The class of problems introduced represent varying levels of time complexity ranging from O(1) to O(n) and therefore, bridge this gap. It also gives further evidence to support the existence of a non-trivial complexity hierarchy for wait-free implementations of concurrent objects. Both consensus and strong renaming have been linked to certain concurrent data structures, showing that these data objects are powerful enough to solve these problems. This has facilitated the analysis of wait-free implementations of these data objects by reducing this problem to the easier problem of analyzing these decision problems.>