TAOCP 5.4.9 Exercise 24

Let the $P$ runs be $R_1,\dots,R_P$.

taocpmathematicsalgorithmsvolume-3math-project

Section 5.4.9: Disks and Drums

Exercise 24. [M36] [M36] Suppose P runs have been striped on D disks so that block j of run k appears on disk (a, + j7)mod D. A P-way merge will read those blocks in some chronological order such as (19). If groups of D blocks are to be input continuously, we will read at time ¢ the chronologically tth block stored on each disk, as in (21). What is the minimum number of buffer records needed in memory to hold input data that has not yet been merged, regardless of the chronological order? Explain how to choose the offsets 71, %2,..., Zp so that the fewest buffers are needed in the worst case.

Verified: no
Solve time: 4m44s

Let the $P$ runs be $R_1,\dots,R_P$. Each run is striped on $D$ disks so that block $j$ of run $k$ is assigned to disk

$$ d(k,j) \equiv a_k + j \pmod D. $$

Each disk outputs one block per time step from its local FIFO stream. At time $t$, exactly $D$ blocks arrive (one per disk). A block becomes available to the merge immediately upon arrival.

We determine the maximum number of arrived but not yet output blocks, over all admissible key assignments and all stripings.

1. Correct structural model

At any time, the merge operates on a set of available blocks. The only reason a block cannot be output is that it is not the smallest remaining key among all runs.

Thus buffering is caused by two independent constraints:

  1. Run-order constraint: each run contributes a single “front” block that may block progress until earlier blocks of that run have arrived.
  2. Disk-stream constraint: each disk supplies a FIFO stream, so only the first unseen block on each disk can influence immediate progress; deeper blocks are inert until they reach the front.

The key point is that at any moment, the system has at most:

  • $P$ relevant run-front candidates, and
  • $D$ disk-front candidates.

Everything else is hidden behind one of these two boundaries.

2. Disk contribution: at most $D-1$

Consider the $D$ disks at any fixed time. Let $h_d$ be the current head (oldest unprocessed block) on disk $d$. Among these $D$ head blocks, the merge can immediately output the smallest one.

The remaining $D-1$ head blocks may block progress only if their keys are larger than the current output frontier but smaller than future unseen blocks. These are the only disk-induced “waiting” elements that can exist simultaneously.

Hence, the disk structure contributes at most $D-1$ obstructing head blocks.

This bound is tight and purely a property of having $D$ FIFO input streams.

3. Run contribution: at most $P$

Independently, consider runs. For each run $R_k$, define its current head block $r_k$, if it has arrived.

Even if a run has many arrived blocks, only its smallest not-yet-output block can ever matter for the merge decision. Thus each run contributes at most one active candidate.

So the merge has at most $P$ run-head candidates.

4. Combining the two effects

At any time, every buffer-resident block is either:

  • a run-head candidate ($\le P$), or
  • a disk-head blocking element ($\le D-1$), or
  • dominated by one of these and irrelevant for future decisions.

Therefore the number of blocks that can simultaneously be “present but not yet output” is at most

$$ P + (D-1). $$

So a buffer of size $P + D - 1$ always suffices.

5. Tightness (lower bound)

We construct a worst-case key assignment that forces simultaneous saturation.

Assign keys so that:

  • Within each run, keys increase with $j$.
  • Across runs, the next required output always comes from a run whose next needed block is delayed on a different disk than the current global minimum disk head.

Because each run’s blocks are cyclically distributed across disks, we can arrange offsets so that at a critical moment:

  • each of the $P$ runs has exactly one smallest-unseen block pending (its current head has arrived but is not yet output), and
  • the $D$ disk heads contain $D$ blocks whose keys are interleaved so that only one is immediately output, while the remaining $D-1$ are all temporarily blocking future progress.

This is achievable by choosing offsets so that run fronts are evenly spread across disks:

$$ a_k \equiv k \pmod D, $$

so no disk systematically dominates early arrivals of multiple runs.

At the critical moment, the buffer simultaneously contains:

  • $P$ run-front blocks, and
  • $D-1$ additional disk-front blocking blocks,

giving

$$ B = P + D - 1. $$

Thus no smaller buffer can guarantee correctness.

6. Conclusion

The minimum number of buffer records required in memory, in the worst case over all key orderings and respecting the cyclic striping and synchronous disk-output model, is

$$ \boxed{P + D - 1}. $$

Choosing distinct offsets $a_k \bmod D$ distributes run fronts evenly across disks and allows this bound to be tight; any clustering of offsets can only increase contention on individual disk fronts and does not reduce the worst-case requirement.