  We show that the problem of deciding for a given finite relation algebra A
whether the network satisfaction problem for A can be solved by the
k-consistency procedure, for some natural number k, is undecidable. For the
important class of finite relation algebras A with a normal representation,
however, the decidability of this problem remains open. We show that if A is
symmetric and has a flexible atom, then the question whether NSP(A) can be
solved by k-consistency, for some natural number k, is decidable (even in
polynomial time in the number of atoms of A). This result follows from a more
general sufficient condition for the correctness of the k-consistency procedure
for finite symmetric relation algebras. In our proof we make use of a result of
Alexandr Kazda about finite binary conservative structures.
