The paper deals with mesh-connected massively-parallel systems affected by failures. The complexity of a local diagnosis procedure, based on new definitions of the local k-diagnosability and the r-fault-tolerance, is analysed. It depends on distances between individual fault clusters 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 the two clusters. The criterion function for the optimal diagnostic examination for local diagnosis is proposed.