The paper deals with the problem of analyzing fault susceptibility of a parallel algorithm designed for a multiprocessor array (MIMD structure). This algorithm realizes quite complex communication protocol in the system. We present an original methodology of the analysis based on the use of software implemented fault injector. The considered algorithm is modeled as a multithreaded application. The experiment set up and results are presented and commented. The performed experiments proved relatively high natural robustness of the analyzed algorithm and showed further possibilities of its improvement.