Question 61

Find forbidden latencies by taking differences of time slots where any stage is reused:

• Stage $S_1$ is used at times 1 and 5: difference $= 5 - 1 = 4$.
• Stage $S_2$ is used at times 2 and 4: difference $= 4 - 2 = 2$.
• Stage $S_3$ is used only at time 3: no collision.
  Forbidden latency set $F = \{2, 4\}$.

Initial collision vector: $C_0 = (b_4 b_3 b_2 b_1) = (1, 0, 1, 0)$.

State transitions:

• Latency 1 is permissible ($b_1 = 0$):
  Next state $= \text{shift}(1010, 1) \mid (1010) = 0101 \mid 1010 = 1111$.
  From $(1111)$, only latencies $\ge 5$ are allowed, returning to $C_0$.
  Cycle: $(1, 5)$ with average latency $= \frac{1 + 5}{2} = 3$.

• Latency 3 is permissible ($b_3 = 0$):
  Next state $= \text{shift}(1010, 3) \mid (1010) = 0001 \mid 1010 = 1011$.
  From state $(1011)$, latency 3 is permissible ($b_3 = 0$):
  Next state $= \text{shift}(1011, 3) \mid (1010) = 0001 \mid 1010 = 1011$ (self-loop).
  Cycle: $(3)$ with average latency $= 3$.

The minimum average latency among all simple cycles is $\text{MAL} = 3$.