In this research, We introduce two probabilistic mechanisms to certificate parallel applications on distribute architecture supposing that there are no oracles on which we depend on certification, in addition to introducing cost model of two mechanisms and compare them. In this research, we are interested in parallel applications, which are represented by data-flow graph that is built dynamically during the execution and which are executed in a wide distributed heterogeneous and dynamic environment and these applications use the principle of work stealing to distribute the tasks among the processors.