マージキューは主ブランチの不変条件を保つ

検査 $\chi$ は決定的で、最初の先頭 $h_0$ は $\chi(h_0) = \text{合格}$ を満たし、先頭はマージキューの規則（定義 3.2）によってのみ更新されるとする。

(a) 先頭の列 $h_0, h_1, h_2, \ldots$ のすべてについて $\chi(h_k) = \text{合格}$ である。

(b) （楽観的な並列化）先頭が $h$ のとき、待っている変更 $\delta_1, \ldots, \delta_k$ に対して $s_0 = h$、$s_j = \delta_j(s_{j-1})$ と順に定め（衝突が出たらそこで止める）、定まった $s_1, s_2, \ldots$ の検査を同時に実行する。$s_j$ が衝突であるか不合格である最小の $j$ を $j^{*}$ とし（なければ $j^{*} = k + 1$）、先頭を $s_{j^{*}-1}$ に進め、$\delta_{j^{*}}$ を却下し、$\delta_{j^{*}+1}, \ldots, \delta_k$ を待ち行列に戻して同じことを繰り返す。この方式の先頭の列と却下される変更の集合は、変更を 1 つずつ処理した場合と同じである。特に不変条件は保たれる。

(c) (b) の方式で $k$ 個の変更を処理し終えるまでに実行する検査の回数は、却下が $r$ 個のとき $(r + 1)k$ 以下である。却下が 1 つ出るたびに捨てられる検査の結果は、その変更より後ろに並んでいた変更の個数以下である。