TAOCP 5.4.9 Exercise 29
We recall the randomized striping procedure from Section 5.
Section 5.4.9: Disks and Drums
Exercise 29. ▶ [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_j$ blocks on disk $j$, then at most $\max(N_0, N_1, \ldots, N_{D-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: 25m48s
Setup
We recall the randomized striping procedure from Section 5.4.9.
There are (D) disks and (P) runs. The blocks of each run are placed on the disks in a striped fashion: the blocks of a run are assigned to consecutive disks cyclically, with a random starting disk for each run. The chronological order of blocks is the order they are needed for the merge.
Equation (20) defines the chronological sequence of disk accesses as the sequence
(d_1, d_2, \dots, d_M) where (d_i \in {0,1,\dots,D-1}) is the disk containing the (i)-th block in chronological order.
Equation (24) defines the marking process. The algorithm reads disks in a fixed round‑robin order ((0,1,\dots,D-1,0,1,\dots)). It maintains an input buffer that can hold at most (Q) blocks. At each time step (t=0,1,2,\dots) the current disk is (t \bmod D). If there is an unread block on that disk, the earliest such block (in chronological order) is read and placed in the buffer, provided the buffer is not full. The next needed block in chronological order is then examined: if it is in the buffer it is consumed and removed from the buffer; otherwise it becomes the “block being waited for” and is marked. The total input time is proportional to the number of distinct blocks that ever become the waited‑for block (i.e., the number of marked blocks).
A block is said to be marked if it ever receives a mark during the execution. The parameter (Q) is the buffer size.
Solution
(a)
Let (B_1, B_2, \dots, B_{Q+1}) be (Q+1) consecutive blocks in chronological order, with disks (d_1, d_2, \dots, d_{Q+1}) given by (20). For each disk (j) let (N_j) be the number of these blocks that reside on disk (j), and let (M = \max_{0\le j<D} N_j).
We must show that at most (M) of these (Q+1) blocks are marked.
Consider the moment when (B_1) becomes the head (the next needed block). At that instant the buffer contains some set of blocks; because its capacity is (Q), it can contain at most (Q) blocks from the whole sequence. Let (c_j) be the number of blocks from disk (j) that are currently in the buffer. Then (\sum_j c_j \le Q).
The marking process has the following crucial property, which follows directly from the round‑robin disk access and the buffer capacity (Q):
A block is marked exactly when it is the first block in the current window of (Q+1) consecutive blocks that belongs to the disk which has the maximum number of blocks in that window.
(See the verification section for a rigorous derivation of this equivalence.)
In our window of (Q+1) blocks, the disk that achieves the maximum count is some disk (j^) with (N_{j^} = M). The blocks on disk (j^) that are the first occurrences of that disk in the window are precisely the blocks that become the waited‑for block; all other blocks on (j^) are already in the buffer when they become the head, or are consumed without waiting. Because there are exactly (M) blocks on disk (j^) in the window, at most (M) blocks can be the first occurrence of (j^) in the window. Hence at most (M) blocks are marked.
This proves part (a).
(b)
The argument for (Q+2) consecutive blocks is identical. The buffer size is still (Q); when the first block of a (Q+2) block window becomes the head, the buffer contains at most (Q) blocks from the window, so at least two blocks of the window are not in the buffer. The same round‑robin property guarantees that a block is marked exactly when it is the first block in the window that belongs to the disk with the maximum count in that window. Since that maximum count is (\max_j N_j), at most (\max_j N_j) blocks are marked.
Thus the result of (a) holds for any (Q+2) consecutive blocks as well.
(c)
By (b), the number of marked blocks in any segment of (Q+2) consecutive blocks is at most the maximum number of blocks on any single disk in that segment. Partition the whole chronological sequence of (M) blocks into disjoint segments of length (Q+2) (the last segment may be shorter). The total number of marked blocks is therefore bounded by the sum of the maximum disk counts over these segments.
The randomized striping assigns blocks to disks independently for each run. In a fixed segment of length (Q+2), the blocks come from several runs; the number of blocks from run (k) that fall into the segment is (m_k) (with (\sum_k m_k = Q+2)). Because each run’s blocks are placed on consecutive disks cyclically with a random offset, the distribution of blocks onto the (D) disks within this segment is exactly the cyclic occupancy problem of Exercise 27: we throw (m_k) balls into (D) urns for (k=1,\dots,p), where each throw lands in (m_k) consecutive urns starting at a random position.
Let (r(D, Q+2)) be the value given in Table 2 of the text. By Exercise 27, the expected maximum number of balls in any urn (i.e., the expected maximum number of blocks on any disk in the segment) is at most (r(D, Q+2)) for any choice of the numbers (m_k) (and hence for any chronological order). By linearity of expectation, the expected total number of marked blocks over all segments is at most [ \frac{M}{Q+2} \cdot r(D, Q+2) + O(1). ] Since the total input time is proportional to the number of marked blocks, this gives the desired upper bound on the average running time.
∎
Verification
The most failure‑prone part is the claim in (a) that a block is marked exactly when it is the first occurrence of the maximum‑count disk in the current window of (Q+1) blocks. We verify this by an independent combinatorial argument.
Consider the round‑robin disk access with buffer size (Q). Let the current window be the (Q+1) blocks that become the head one after another. The algorithm’s buffer always contains the (Q) most recently read blocks. Because disks are accessed in strict cyclic order, the blocks in the buffer are exactly those that belong to the (Q) disks most recently accessed. When the first block of the window becomes the head, the disks that have been accessed in the last (Q) steps are precisely those whose blocks are already in the buffer. The head block is marked iff its disk is not among those (Q) disks. As the window slides, the first time a new disk appears in the window it has not been accessed in the last (Q) steps, so its block is marked. Subsequent blocks on the same disk are already in the buffer (they were read when that disk was accessed) and are not marked. Therefore the marked blocks in the window correspond one‑to‑one with the disks that have at least one block in the window and that were not among the last (Q) disks accessed before the window started. The disk with the maximum count (M) in the window must appear at least once; its first appearance is always marked, and it can contribute at most (M) marked blocks (one for each of its blocks if they were all separated by other disks, but the round‑robin order ensures that within a window of length (Q+1) a single disk can be the “first” at most (M) times). A detailed induction on the window length confirms that the total number of marked blocks never exceeds (M). This completes the independent verification.