# Trading time for work; does this concurrency phenomenon have a name?

Recently, my girlfriend and I were trying to get out of the house, when I encountered a phenomenon which I thought might be analogous to a tradeoff in concurrent systems.

Here's the real world setup.

### Processes

• Process A: Girlfriend orders coffee on phone.
• Process B: Girlfriend gets ready at apartment, and ideally drives car to pick me up at coffee shop.
• Process C: I fetch coffee, and ideally get picked up by girlfriend at coffee shop.
• Process D: We commute together.

### Dependencies

• Process A must complete before Processes B and C.
• Process B and C must complete before Process D.

### Phenomenon

On the day:

• My girlfriend orders coffee (Process A) and begins getting ready (Process B).
• I leave the apartment to fetch coffee while my girlfriend is getting ready (Process C).
• However, my girlfriend takes longer than expected to get ready, so instead of getting picked up at the coffee shop shortly after dealing with payment, I wait.
• Then, we commute (Process D).

### What's suboptimal?

Resources, namely me walking, are not used minimally. In retrospect, we determine the optimal solution given the knowledge that my girlfriend will take longer to get ready is to simply wait. Once she finishes getting ready, we ought to drive to the coffee shop together to fetch the coffee and commute from there.

Processes are appropriately recognized as able to be parallelized. But, because of resource sharing, will only yield the desired improvements under ideal circumstances wherein girlfriend arrives by car at coffee shop shortly after coffee has been fetched. Unless this circumstance is realized, the time to complete Processes A - D becomes primarily determined by Process B and optimization of Process C is not concerning.

More generally, we determine a sequential solution makes better use of resources than the concurrent solution.

If processes are performed...

A -> B -> C -> D


we will most likely prefer that outcome to the original...

     -> B -
A - |      | -> D
-> C -


... (in part) because, even though time is slightly less optimized, work is better shared.

Does this phenomenon have a name? In what areas of computing might this tradeoff be more common or concerning? What are common software analysis strategies that may help?

Note: I can contrive examples with more significant effects, even ones that do not produce optimal runtime (though that may be another phenomenon). But, (a) this is partially a playful barb at my gf's planning and (b) I thought this might resonate with some folks.

• Not all things that can happen have a short name. What do you mean by "may help"? Can you formulate a more specific problem statement? It's unclear what decisions you want to make (e.g., what aspects you are able to change and what is fixed and not under your control).
– D.W.
Sep 14, 2022 at 1:28
• I guess the following might be a shorter way to describe the core phenomenon. For a set of processes with fixed dependencies and the ability to share resources, naively selecting the most concurrent solution may result in more work than is necessary. (Fixed: dependencies; controlled: level of concurrency and which resources are shared.) Sep 14, 2022 at 14:09
• If we give ourselves the ability to add to the dependency graph, this becomes a slightly different problem. This is also a way to achieve the optimal solution. Sep 14, 2022 at 14:23

Such considerations are known as Critical Path analysis. They allow to describe the temporal dependencies and find the fastest solution, as well as detect bottlenecks or near-bottlenecks.

https://en.wikipedia.org/wiki/Critical_path_method

• This may be good for another question. But, are you aware of cases wherein the weights on the graph are more complex? Include considerations other than time? Are multi-dimensional? Sep 15, 2022 at 22:50
• @lmonninger: this touches the universe of multicriteria optimization. I assume that you can generalize the concept.
– user16034
Sep 16, 2022 at 7:07

So your situation in computing terms: You have two task A and B that could be calculated in parallel. A produces a result X at no cost at the end of A. B requires X at the first step. B has the choice of waiting for A to finish, or calculating X itself.

It is not uncommon that trying to parallelise tasks involves duplicating some work. There is no particular name for this.

(A much worse case is the alpha-beta algorithm for chess. Each calculation makes the next calculation more efficient. But if you perform multiple calculations in parallel, you can’t take advantage of that).

• Don't know why this was downvoted. This is actually good info and given that the question is rather vague is reasonable as an answer. Sep 15, 2022 at 17:33

In the absence of a direct answer, here are some ideas.

I would say this is essentially a job scheduling problem with multiple optimization criteria:

• total completion time
• resource utilization

The mathematical discipline that studies such problems is scheduling theory, a subdiscipline of operations research; I'm not really familiar with the field, but if you're looking for standard terminology, I'd look there.

Many others have been working on scheduling problems, with their own approach, and no doubt some of them have their own terminology.

For instance, I used to work on a Petri net editor that can be used to draw your examples (as Petri nets), and, after assigning expected processing times to the individual tasks, simulations can be run to calculate average completion times and resource utilization for each resource. It is by no means the only software tool with such capabilities. Its designer, a professor in computer science (now retired), spent considerable effort on problems in logistics and job scheduling, and this was one of his efforts to provide practical tooling for modeling and optimizing such problems. This approach is different from the one taken in operations research, and it has its own merits and limitations.