Definition of lifeless (referring to parallel programming)

Question

In an article by Maurice Herlich, "Lifeless Synchronization," he defines without expectation:

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

Take one op operation from the universe.

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

(2) Or does this mean: “Each process completes a certain op operation in any finite number of steps. Thus, a process can complete op in k steps, another process in j steps, where k! = J.”?

Just by reading the definition, I would understand the meaning (2). However, this does not make any sense to me, since the process executing op in k steps and another time in steps k + m matches the definition, but m steps can be a wait loop. If the meaning of (2) is right, can someone explain to me why this describes without waiting?

Unlike (2), a value of (1) would guarantee that op is executed in the same number of steps k. Thus, there can be no additional steps m that are necessary, for example. in a wait loop.

What is the right meaning and why?

Many thanks,

sema

Answer 1

The answer means definition (2). Consider that the wait cycle could not potentially end if the process waiting to be executed is indefinitely: "regardless of the speed of the other processes."

Thus, an infinite wait loop means that the process may not complete the operation in a finite number of steps.

Answer 2

When the author of such a theoretical article writes “a finite number of steps”, this means that there is some constant k (you do not necessarily know k ), so the number of steps is less than k (that is, your waiting time will certainly not be infinite).

I'm not sure what “op” means in this context, but usually when you have a multi-threaded program, threads can wait for each other to do something.

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

This example is not free, because if the thread containing the lock is not able to do any operations (this is bad, since the requirement here is that other threads continue to run independently of any other thread), other threads are doomed and never no progress has been made.

Another example: there are several threads, each of which tries to CAS at the same address

This example is free because, although all threads except one will not work in such an operation, there will always be progress no matter which threads are selected to run.

Answer 3

You seem to be worried that Definition 2 allows an infinite wait loop, but such an infinite number of loops will not satisfy the requirement of completion within a finite number of steps.

I take "without waiting" to mean that to achieve progress it is not required that any participant wait for the end of another participant. If such an expectation was necessary, if one participant is hanging or working slowly, other participants suffer in a similar way.

In contrast, with a perpetual approach, each participant tries their work and maintains competitive interaction with other participants. For example, each thread may try to promote a state, and if they try twice at the same time, only one should succeed, but there is no need for participants who “fail” to try again. They simply admit that someone else has already completed their work, and they are moving forward.

Instead of focusing on “waiting for my turn to act,” a no-wait approach encourages “trying to help,” recognizing that others can also try to help at the same time. Each participant must know how to detect success, when to retry, and when to refuse, I am sure that the attempt only failed, because someone else got there first. As long as the work is completed, it does not matter which thread does this.

Answer 4

Anxiety essentially means that a multiprocessor environment does not require synchronization. A “finite number of steps” means no need to wait on a synchronization device (for example, a mutex) for an unknown - and potentially infinite (deadlock) - time, while another process is performing a critical section.