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/

## No comments:

## Post a Comment