The paper deals with mesh-connected massively-parallel systems affecte
d by failures. The complexity of a local diagnostic procedure, based o
n new definitions of the local k-diagnosability and the r-fault-tolera
nce, is analysed. It depends on distances between individual fault clu
sters and on fault cluster diameters. In particular cases the minimum
distance between fault clusters can be enlarged on the account of the
maximum fault cluster diameter, e.g., by merging of two clusters. The
criterion function for the optimal diagnostic examination for local di
agnosis is proposed.