A fundamental problem in distributed computing is the task of cooperatively executing a given set of t tasks by p asynchronous processors where the communication medium is dynamic and subject to failures. Also known as do-all, this problem been studied extensively in various distributed settings. In [2], the authors consider a partitionable network scenario and analyze the competitive performance of a randomized scheduling algorithm for the case where the tasks to be completed are independent of each other. In this paper, we study a natural extension of this problem where the tasks have dependencies among them. We present a simple randomized algorithm for p processors cooperating to perform t known tasks where the dependencies between them are defined by a k-partite task dependency graph and additionally these processors are subject to a dynamic communication medium. By virtue of the problem setting, we pursue competitive analysis where the performance of our algorithm is measured against that of the omni...
['Chadi Kari', 'Alexander Russell', 'Narasimha Shashidhar']
Work-Competitive Scheduling on Task Dependency Graphs