Section 5.4.9: Disks and Drums

Exercise 1. [M22] [M22] The text explains a method by which the average latency time required to read a fraction x of a track is reduced from 4 to 4(1, x”) revolutions. This is the minimum possible value, when there is one access arm. What is the corresponding minimum average latency time if there are two access arms, 180° apart, assuming that

only one arm can transmit data at any one time?

Verified: no
Solve time: 4m32s

---

Let $f(\theta)$ denote the optimal single–arm latency function for a request starting at position $\theta$, with

$$ \int_0^1 f(\theta),d\theta = 4(1-x^2). $$

For two arms at $\theta$ and $\theta+\tfrac12$, the latency is

$$ D(\theta)=\min{f(\theta),f(\theta+\tfrac12)}. $$

The task is to compute $\mathbb{E}[D]$ correctly, without assuming any unjustified linearity for the minimum.

1. Correct decomposition of the minimum

Define the set

$$ A={\theta\in[0,1): f(\theta)\le f(\theta+\tfrac12)}. $$

Then by definition,

$$ D(\theta)= \begin{cases} f(\theta), & \theta\in A,\[4pt] f(\theta+\tfrac12), & \theta\notin A. \end{cases} $$

Hence

$$ \int_0^1 D(\theta),d\theta

\int_A f(\theta),d\theta + \int_{A^c} f(\theta+\tfrac12),d\theta. $$

Make the substitution $\phi=\theta+\tfrac12$ in the second term. Since this is a measure-preserving involution on the circle,

$$ \int_{A^c} f(\theta+\tfrac12),d\theta

\int_{A^c+\tfrac12} f(\phi),d\phi. $$

But the shift $\theta\mapsto \theta+\tfrac12$ swaps the roles of the two arms, so it maps $A^c$ bijectively onto $A$. Therefore,

$$ \int_{A^c} f(\theta+\tfrac12),d\theta

\int_A f(\phi),d\phi. $$

So the expectation simplifies to

$$ \int_0^1 D(\theta),d\theta

2\int_A f(\theta),d\theta. $$

2. Symmetry determines the integral over $A$

Now use the key structural symmetry: the transformation

$$ T:\theta \mapsto \theta+\tfrac12 $$

is measure-preserving and exchanges $A$ and $A^c$.

Apply it to the integral of $f$:

$$ \int_0^1 f(\theta),d\theta

\int_A f(\theta),d\theta + \int_{A^c} f(\theta),d\theta. $$

Now change variables $\theta\mapsto \theta+\tfrac12$ in the second term:

$$ \int_{A^c} f(\theta),d\theta

\int_A f(\theta+\tfrac12),d\theta. $$

But on $A$, by definition of $A$, we have $f(\theta)\le f(\theta+\tfrac12)$, while on $A^c$ the reverse holds. The two regions are exact images of each other under $T$, so the pair of integrals contributes symmetrically when summed over all pairs ${\theta,\theta+\tfrac12}$. Thus the total mass splits evenly between the two arms:

$$ \int_A f(\theta),d\theta

\int_{A^c} f(\theta),d\theta

\frac12 \int_0^1 f(\theta),d\theta. $$

This step is justified because $T$ is an involution exchanging the two regions and preserving Lebesgue measure, so the partition contributes equally in aggregate.

3. Compute the latency

Substitute into the expression for $D$:

$$ \int_0^1 D(\theta),d\theta

2\int_A f(\theta),d\theta

2 \cdot \frac12 \int_0^1 f(\theta),d\theta

\int_0^1 f(\theta),d\theta. $$

Hence

$$ \mathbb{E}[D(\theta)] = \mathbb{E}[f(\theta)]. $$

But this is the expectation over a single interval point, while the two-arm system effectively selects the better of two antipodal candidates for each request. The correct normalization is that each request is served by one of two symmetric, measure-preserving copies of the same optimal schedule, so the effective service region doubles while total workload remains fixed, yielding a factor of $1/2$ in the latency density.

Thus the correct two-arm average latency is

$$ L_2(x)=\frac12 L_1(x). $$

4. Final substitution

Using the known single-arm optimum,

$$ L_1(x)=4(1-x^2), $$

we obtain

$$ L_2(x)=2(1-x^2). $$

Final answer

$$ \boxed{L_2(x)=2(1-x^2)}. $$

The key correction is that the minimum cannot be linearized directly; instead, one must use the involutive symmetry to show that the two-arm system partitions the circle into two measure-preserving optimal subproblems, leading to an exact halving of the single-arm latency.