Randomized Work-Competitive Scheduling for Cooperative Computing on k-partite Task Graphs

A fundamental problem in distributed computing is the problem of cooperatively executing a given set of tasks in a dynamic setting. The challenge is to minimize the total work done and to maintain efficiency in the face of dynamically changing processor connectivity. In this setting, work is defined as the total number of tasks performed (counting multiplicities) by all the processors during the course of the computation. In this scenario, we are given a set of t tasks that must be completed in a distributed setting by a set of p processors where the communication medium is subject to failures. We assume that the t tasks are similar, in that they require the same number of computation steps to finish execution. We further assume that the tasks are idempotent - executing a task multiple times has the same effect as a single execution of the task. The tasks have a dependency relationship defined among them captured by a task dependency graph.