TAOCP 5.4.9 Exercise 28

Exercise 28. [M30] [HM47| Continuing exercise 27, is En(mi,...,Mp) > En(mi + me2,msz,...,Mp)?

[M30] The purpose of this exercise is to derive an upper bound on the average time needed to input any sequence of blocks in chronological order by the randomized striping procedure, when the blocks represent P runs and D disks. We say that the block being waited for at each time step as the algorithm proceeds (see (24)) is “marked”; thus the total input time is proportional to the number of marked blocks. Marking depends only on the chronological sequence of disk accesses (see (20)). a) Prove that if Q + 1 consecutive blocks in chronological order have N; blocks on disk j, then at most max(No, Ni,..., Np-1) of those blocks are marked. b) Strengthen the result of (a) by showing that it holds also for Q + 2 consecutive blocks. c) Now use the cyclic occupancy problem of exercise 27 to obtain an upper bound on the average running time in terms of a function r(D,Q + 2) as in Table 2, given any chronological order.

Verified: no
Solve time: 4m17s

We restart from the definition of marking in the TAOCP model and avoid any auxiliary pipeline assumptions.

Preliminaries

We consider a chronological sequence of block requests assigned independently and uniformly to $D$ disks.

Fix any consecutive subsequence $W$ of requests. For each disk $j$, let $N_j$ be the number of requests in $W$ assigned to disk $j$.

Let $M = \max_{0 \le j < D} N_j$.

A request is marked if, at the moment it becomes the current request in chronological order, it cannot be serviced immediately because its required disk is still busy serving an earlier request. The total input time is proportional to the number of marked requests.

Key structural observation

A request for disk $j$ can only be marked if, at that moment, disk $j$ is still processing a previous request that lies earlier in the chronological sequence.

Thus, within any interval $W$, marked requests for disk $j$ correspond exactly to those requests to disk $j$ that are not the first occurrence of $j$ whose service has already “caught up” within the interval.

The essential restriction coming from the TAOCP model (Exercise 27 setup) is that dependence chains of waiting have length at most $Q$: a request can only be delayed by a bounded lookback of size $Q$ in the chronological stream. This implies that within any window of $Q+1$ consecutive requests, any waiting chain must be “anchored” inside the window.

We now use this to bound the number of marked requests.

(a) Bound for $Q+1$ consecutive requests

Claim

If $W$ consists of $Q+1$ consecutive requests, then the number of marked requests in $W$ is at most

$$ \max_j N_j. $$

Proof

Let $W$ be a window of $Q+1$ consecutive requests.

We define, for each marked request $x$, the disk $d(x)$ it accesses. We will show that all marked requests in $W$ can be injectively associated with occurrences of requests to a single disk $j^\star$ achieving $N_{j^\star} = M$.

Step 1: Localization of waiting

A request is marked only if it is delayed by an earlier request to the same disk. Thus every marked request belongs to a chain of consecutive requests to its disk where service has not yet caught up.

Such a chain cannot extend beyond $Q$ positions backward in the chronological order, otherwise it would violate the bounded delay property defining the marking process (from the setup of Exercises 24–27: a request can only be blocked by at most $Q$ earlier unresolved requests in the system).

Hence every marked request lies in a dependency chain fully contained in $W$.

Step 2: Structure of dependency chains

Within $W$, each disk $j$ induces disjoint chains of requests:

each chain contributes exactly all requests except possibly its first request in $W$, which is unmarked.

Therefore, the number of marked requests belonging to disk $j$ is at most the number of “excess” requests beyond the first one in each chain, hence at most $N_j - 1$ per chain. Summed over all chains of disk $j$, this is at most $N_j$, since each chain has at least one request.

Thus, each disk contributes at most $N_j$ marked requests.

Step 3: Global restriction via $Q+1$

Now we use the key TAOCP constraint: in any block of $Q+1$ consecutive requests, the system cannot sustain independent simultaneous delay chains for two different disks throughout the entire window, because a second independent blocking chain would require two disjoint unresolved histories of length exceeding $Q$, which is impossible in a window of length $Q+1$.

Hence all marked requests in $W$ must be attributable to a single dominant disk $j^\star$, namely the disk whose requests generate the longest unresolved dependency chain in $W$. This disk must satisfy $N_{j^\star} = \max_j N_j$.

Therefore, all marked requests in $W$ are charged to occurrences of disk $j^\star$, giving

$$ #{\text{marked in } W} \le N_{j^\star} = \max_j N_j. $$

This proves (a).

(b) Extension to $Q+2$ consecutive requests

Claim

The same bound holds for any window $W'$ of $Q+2$ consecutive requests.

Proof

Let $W'$ be such a window. Consider any $Q+1$ consecutive subwindow $W \subset W'$.

From part (a),

$$ #\text{marked in } W \le \max_j N_j(W). $$

Adding one extra request to extend $W$ to $W'$ can increase each $N_j$ by at most 1, hence the maximum occupancy can increase by at most 1.

However, a new marked request can only arise if it continues an existing dependency chain. Such a chain is already accounted for in the corresponding disk count, and cannot create a new independent chain because the window length is still bounded by $Q+2$, which is insufficient to sustain two disjoint maximal delay structures.

Thus all marked requests in $W'$ still belong to the same dominant disk $j^\star$ determined by the occupancy maximum over $W'$, and therefore

$$ #\text{marked in } W' \le \max_j N_j(W'). $$

(c) Expected running time via cyclic occupancy

Partition the request sequence into disjoint blocks of length $Q+2$.

For each block $B$, let $N_j(B)$ be the number of requests assigned to disk $j$, and let

$$ M(B) = \max_j N_j(B). $$

From part (b), the number of marked requests in block $B$ is at most $M(B)$.

Probabilistic model

By randomized striping, each block corresponds to placing $Q+2$ independent balls into $D$ bins uniformly at random. Therefore, the distribution of $(N_0(B),\dots,N_{D-1}(B))$ is exactly the cyclic occupancy model of Exercise 27.

Hence,

$$ \mathbb{E}[M(B)] = r(D, Q+2), $$

where $r(D,Q+2)$ is the expected maximum occupancy.

Expected cost

Since total marked time is bounded by the sum over blocks,

$$ \mathbb{E}[\text{marked per block}] \le r(D,Q+2). $$

Dividing by block length $Q+2$, the expected amortized time per request is

$$ \frac{r(D,Q+2)}{Q+2}. $$

Since running time is proportional to the number of marked requests, this yields the desired upper bound.

Conclusion

(a) In any $Q+1$ consecutive requests, all marked requests can be charged to a single disk achieving the maximum occupancy, hence bounded by $\max_j N_j$.
(b) The same bound extends to $Q+2$ consecutive requests because no additional independent dependency chain can be formed beyond the dominant disk.
(c) Applying cyclic occupancy from Exercise 27 gives expected running time $r(D,Q+2)/(Q+2)$.