This paper presents a theoretical study to evaluate the performance of a family of parallel implementations of the propagation algorithm. The propagation algorithm is used to an image interpolation application. The theoretical performance analysis is based on the construction of generic models using Stochastic Automata Networks (SAN) formalism to describe each implementation scheme. The prediction results can be compared to the achieved performance in some real test cases to verify the accuracy of our modeling technique. The main contribution of this paper is to point out the advantages and problems of our approach to the development of generic models of parallel implementations.