A probabilistic approach for task and result certification of large-scale distributed applications in hostile environments

Abstract. This paper presents a new approach for certifying the cor-rectness of program executions in hostile environments, where tasks or their results have been corrupted due to benign or malicious act. Extend-ing previous results in the restricted context of independent tasks, we introduce a probabilistic certification that establishes whether the results of computations are correct. This probabilistic approach does not make any assumptions about the attack and certification errors are only due to unlucky random choices. Bounds associated with certification are pro-vided for general graphs and for tasks with out-tree dependencies found in a medical image analysis application that motivated the research.