Wait-Free is not enough

The current classification of Progress Conditions for algorithms and data structures is not enough to differentiate between the different capabilities and performance/latency of each one.
We propose a new kind of "Big O" notation for Wait-Free algorithms and data structures. Here's how it works:
An algorithm or function is said to be "Wait-Free O(x)" if it takes at most O(x) operations to complete.

Some examples:

• a) An algorithm that scans the states of each active thread will be "Wait-Free O(NThreads)".
• b) An algorithm that needs to insert itself into a sorted list of active threads (using bisection method), will be "Wait-Free O(ln NThreads)".
• c) An algorithm that scans each state of the active threads quadratically will be "Wait-Free O(NThreads^2)".
• d) An algorithm that does 3 operations, regardless of the number of active threads or any other variable, will be "Wait-Free O(1)".
• e) An algorithm that gets a certain number N, like the number of elements "currently" in a list, and does O(N) operations, is said to be "Wait-Free O(N)"
• f) An algorithm that gets a certain number N, and does O(N^2) operations, is said to be "Wait-Free O(N^2)".

According to the current notation, cases a), b), and c) are all "Wait-Free Bounded", but clearly case b) is much better than c) or a).
According to the current notation, cases d), e), and f) are all "Wait-Free Population Oblivious", yet case d) is clearly much better than cases e) or f).

Perhaps more interesting, case b) may be much better than case f) , particularly if N > NThreads, even though b) is "Bounded" and f) is "Population Oblivious", which just serves to show that "Wait-Free Population Oblivious" is not necessarily better than "Wait-Free Bounded".

How about Lock-Free?
Well, in this new notation, Lock-Free could be written as "Wait-Free O(infinity)", but notice that although all Lock-Free algorithms have a worst-case O(infinity), most of them have an expected number of operations of O(1) or O(N), and don't depend on the number of threads.

One more example:
- A Linked-List that is Wait-Free for contains() will never be better than "Wait-Free O(N_elements)" where N_elements is the number of elements in the list at some point in time during the contains() operation.


Matching between old and new classification:

• Wait-Free Bounded: O(ln NThreads), O(NThreads), O(NThreads^2),  ...
• Wait-Free Population Oblivious: O(1), O(ln N), O(N), O(N^2), ...

On our own data structures, we are trying to follow this convention and indicate in for each function what is the order of the Progress Condition.
http://sourceforge.net/projects/ccfreaks/files/