Nodes in a Distributed system (DS) are prone to failure due to link failure, resource failure or any other reason have to be tolerated for the execution of the system smoothly and accurately. Faults may affect the operation of DS at any time. In this regard diagnosing the faulty nodes in the distributed system is one of the requirements to make the system more reliable and efficient. Faults can be detected and recovered by many techniques according to the requirement. In this thesis we presented a robust stochastic search method based on evolutionary algorithmic approach to detect faults in a k-connected DS with at most (n-1)/2 permanent faulty components out of ‘n’ tested components using two approaches. The first approach is by using a Genetic algorithm with Fuzzy controlled mutation and Tournament selection which provides how a fuzzy-logic can be applied to the algorithm in order to detect permanent faults in a k-connected distributed System. The second approach is a parallel evolutionary algorithm based on immunity theory, which provides how parallel evolution is efficient in this context. The program is implemented in C++ and was tested with random test graphs. Empirical results reveal that the proposed immune parallel evolutionary algorithm (IPEA) method for fault detection in DS is more efficient when compared to fuzzy genetic algorithm (FGA) and the standard basic genetic algorithm (BGA) approaches. The results are satisfactory and demonstrated the efficiency of genetic operators combined with parallel evolution and immune selection used for this study than FGA and BGA.