An invariant is a property that remains true as an algorithm progresses. In a parallel scan, it lets you check what each position represents after every round—and why the final values are correct. section 6.7 section 7.4
In scan algorithms, the invariant tracks how partial sums grow:
- Hillis-Steele: after round r, position i holds the sum of up to 2ʳ input values ending at i. Near the start of the array, the window is clipped at position 0 or the value is copied through. section 6.7
- Blelloch: during the up-sweep, each active position holds a sum over a growing range. During the down-sweep, each visited node holds the sum of original elements before its subtree. section 7.4
Following a scan
For [3, 1, 7, 0, 4, 1, 6, 3], Hillis-Steele grows each position’s window over three rounds. Once a window covers the whole array, each position holds its inclusive prefix sum: [3, 4, 11, 11, 15, 16, 22, 25]. section 6.7
Table 6.1 The three cases that arise when extending the Hillis-Steele invariant from round r−1 to round r. Each row gives the condition on position i, what happens at position i, and the figure that illustrates the case.
|
Case
|
Condition on i
|
What happens at position i
|
|
1
|
i ≥ 2ʳ − 1
|
Full window. Both position i
and position i − 2ʳ⁻¹ hold sums of 2ʳ⁻¹ elements; adding them produces a sum
of 2ʳ elements ending at i (figure 6.6).
|
|
2
|
2ʳ⁻¹ ≤ i < 2ʳ − 1
|
Partial left window. The left
neighbor’s window is clipped at position 0, so it holds fewer than 2ʳ⁻¹
elements; the sum at i still reaches all the way back to position 0 (figure
6.7).
|
|
3
|
i < 2ʳ⁻¹
|
No left neighbor at stride 2ʳ⁻¹. Position i copies its
value through; it already holds the sum of all input elements [0..i] from
earlier rounds (figure 6.8).
|
Use the cases to see how a Hillis-Steele round preserves the invariant at full windows, partial windows, and positions with no left neighbor. section 6.7

















