Probabilistic certification of divide & conquer algorithms on global computing platforms

Abstract

In [6], a new approach for certifying the correctness of program executions in hostile environments has been proposed. The authors presented probabilistic certification by massive attack detection through two algorithms MCT and EMCT. The execution to certify is represented by a macro-data flow graph which is used to randomly extract some tasks to be re-executed on safe resources in order to determine whether the execution is correct or faulty. Bounds associated with certification have been provided for general graphs and for tasks with out-tree dependencies.