World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Work-Competitive Scheduling on Task Dependency Graphs

    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 omniscient offline algorithm which has complete knowledge of the dynamics of the communication medium. We show that the competitive ratio of our algorithm is tight and depends on the dynamics of the communication medium viz. the computational width defined in [2] and also on the number of partitions of the task dependency graph.

    Communicated by K. Qiu