definition of wait-free (referring to parallel programming)

Question

In Maurice Herlihy paper "Wait-free synchronization" he defines wait-free:

"A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless the execution speeds on the other processes." www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf

Let's take one operation op from the universe.

(1) Does the definition mean: "Every process completes a certain operation op in the same finite number n of steps."?

(2) Or does it mean: "Every process completes a certain operation op in any finite number of steps. So that a process can complete op in k steps another process in j steps, where k != j."?

Just by reading the definition i would understand meaning (2). However this makes no sense to me, since a process executing op in k steps and another time in k + m steps meets the definition, but m steps could be a waiting loop. If meaning (2) is right, can anybody explain to me, why this describes wait-free?

In contrast to (2), meaning (1) would guarantee that op is executed in the same number of steps k. So there can't be any additional steps m that are necessary e.g. in a waiting loop.

Which meaning is right and why?

Thanks a lot, sebastian

Answer 1

The answer means definition (2). Consider that the waiting loop may potentially never terminate, if the process that is waited for runs indefinitely: “regardless the execution speeds on the other processes”.

So the infinite waiting loop effectively means that a given process may not be able to complete an operation in a finite number of steps.

Answer 2

When an author of a theoretical paper like this writes "a finite number of steps", it means that there exists some constant k (you do not necessarily know k), so that the number of steps is smaller than k (i.e. your waiting time surely won't be infinite).

I'm not sure what 'op' means in this context, but generally, when you have a multithreaded program, threads might wait for one another to do something.

Example: a thread has a lock, and other threads wait for this lock to be freed until they can operate.

This example is not wait free, since if the thread holding the lock does not get a chance to do any ops (this is bad, since the requirement here is that other threads will continue regardless of any other thread), other threads are doomed, and will never ever make any progress.

Other Example: there are several threads each trying to CAS on the same address

This example is wait free, because although all threads but one will fail in such an operation, there will always be progress no matter which threads are chosen to run.

Answer 3

Wait-free essentially means that it needs no synchronization to be used in a multi-processing environment. The 'finite number of steps' refers to not having to wait on a synchronization device (e.g. a mutex) for an unknown -- and potentially infinite (deadlock) -- length of time while another process executes a critical section.

Answer 4

It sounds like you're concerned that definition 2 would allow for an infinite wait loop, but such a loop -- being infinite -- would not satisfy the requirement for completion within a finite number of steps.

I take "wait-free" to mean that making progress does not require any participant to wait for another participant to finish. If such waiting was necessary, if one participant hangs or operates slowly, other participants suffer similarly.

By contrast, with a wait-free approach, each participant tries its operation and accommodates competitive interaction with other participants. For instance, each thread may try to advance some state, and if two try "at the same" time, only one should succeed, but there's no need for any participants that "failed" to retry. They merely recognize that someone else already got the job done, and they move on.

Rather than focusing on "waiting my turn to act", a wait-free approach encourages "trying to help", acknowledging that others may also be trying to help at the same time. Each participant has to know how to detect success, when to retry, and when to give up, confident that trying only failed because someone else got in there first. As long as the job gets done, it doesn't matter which thread got it done.