  We establish optimal bounds on the number of nested propagation steps in
$k$-consistency tests. It is known that local consistency algorithms such as
arc-, path- and $k$-consistency are not efficiently parallelizable. Their
inherent sequential nature is caused by long chains of nested propagation
steps, which cannot be executed in parallel. This motivates the question "What
is the minimum number of nested propagation steps that have to be performed by
$k$-consistency algorithms on (binary) constraint networks with $n$ variables
and domain size $d$?"
  It was known before that 2-consistency requires $\Omega(nd)$ and
3-consistency requires $\Omega(n^2)$ sequential propagation steps. We answer
the question exhaustively for every $k\geq 2$: there are binary constraint
networks where any $k$-consistency procedure has to perform
$\Omega(n^{k-1}d^{k-1})$ nested propagation steps before local inconsistencies
were detected. This bound is tight, because the overall number of propagation
steps performed by $k$-consistency is at most $n^{k-1}d^{k-1}$.
