Describe the fork-join model of parallel computation: how does a unit of work split itself, and what does the 'join' step guarantee to the code that runs after it?

## The idea Many computations over a large input have the same shape: the answer for the whole input can be assembled from the answers for its parts. Summing an array, sorting it, counting matches, walking a tree, multiplying matrices - all split cleanly. If the parts do not depend on each other, they can be evaluated at the same time. Fork-join is the discipline that turns that observation into a repeatable parallel structure, and it is *recursive*: each part splits again, until the pieces are small enough to be worth doing directly. ## The two operations **fork(task)** makes a task available to run concurrently with the caller. It is a *submission* to a runtime, not the creation of an operating-system thread. This distinction is the whole reason the model is affordable: a parallel sort of a million elements may create hundreds of thousands of tasks, but the runtime executes them on a handful of worker threads, each holding a queue of pending tasks. Creating a thread per split would cost orders of magnitude more than the work being split. **join(task)** waits for that task to complete and yields its result. Logically it is a barrier between one child and its parent. Practically, a good runtime does not park the calling worker: if the child has not started, the joining worker often executes it directly, and otherwise it runs other pending work while it waits, so the thread is not wasted. ## The recursive skeleton ``` solve(input): if size(input) <= CUTOFF: return solveSequentially(input) (a, b) = split(input) left = fork(solve(a)) right = solve(b) // reuse the current worker return combine(join(left), right) ``` The recursion builds a *task tree*: the root is the whole problem, the leaves are the base cases, and results flow back up through the combine step. The tree's breadth gives parallelism; its depth gives the shortest possible finish time. ## What a join actually guarantees Two separate guarantees, and candidates usually name only the first. 1. **Completion ordering.** After `join(t)` returns, `t` has run to completion. Nothing that `t` still had to do can happen later. 2. **Visibility.** Writes performed by the child before it completed are observable by the parent after the join, without any additional lock or flag. Fork and join create ordering edges in the memory model: everything before the fork is visible to the child, and everything the child did is visible after the join. Together these are why a parallel sum needs no synchronization on the array. The parent hands each child a disjoint slice; children only touch their own slice; the join makes each child's partial result and any in-place writes safely readable by the parent. ## The invariant you must not break Sibling tasks must operate on **disjoint mutable data**, or share only immutable/read-only data. Fork-join provides no mutual exclusion between siblings - they are simply concurrent. If two forked subtasks write the same accumulator, you have a data race and the model does not save you. The usual fix is not a lock: it is to give each subtask its own result and combine the results at the join, which is exactly what the structure is for. ## Worked examples **Parallel sum.** Split the range in half, fork one half, sum the other half in place, join, add the two numbers. Total additions are the same as the sequential version; they just happen on many cores. **Parallel merge sort.** Split, fork-sort the left, sort the right, join, then merge. The sorting halves parallelize perfectly; the merge is the part that resists, which is why the merge step dominates how well such a sort scales. **Tree search.** Fork a task per child node; join and combine the matches. The task tree literally mirrors the data structure. ## Costs and limits Every fork costs bookkeeping - allocating a task object, pushing it on a queue, possibly having it stolen. Below some input size that overhead exceeds the work, which is why real implementations stop splitting at a threshold. Splits that are wildly uneven starve workers: an unbalanced tree produces one huge leaf that everyone waits on. And problems with a genuine sequential dependency - a running prefix where element i needs element i-1 - do not fit the model without being rewritten. ## When not to use it Fork-join assumes CPU-bound, non-blocking, side-effect-free-ish leaves. Work that blocks (I/O, locks, queues) starves the fixed worker pool and belongs on a different execution resource.