A fundamental problem in distributed computing is the task of cooperatively executing a given set of t tasks by pprocessors where the communication medium is dynamic and subject to failures. The dynamics of the communicationmedium lead to groups of processors being disconnected and possibly reconnected during the entire course of thecomputation. The primary objective in this scenario is for the group of p processors to compute all the t tasks whileminimizing the total work done. In the partitionable network paradigm, work is defined as the total numberof tasks performed (counting multiplicities) by all the processors during the course of the computation. In prior work (Work-competitive scheduling for cooperative computingwith dynamic groups. In SIAM Journal on Computing: Volume 34, Issue 4, pages 848–862, 2005.), the authors have studied such a partitionable network scenario and analyze a simple randomized scheduling algorithm for the case where the tasks to be completed are independent of each other. In this paper, we study a natural generalization of this problem where the tasks have dependencies among them defined by a task dependency graph. In particular, we consider task dependency graphs that are k-partite task graphs. Such task dependency graphs have been studied extensively in performing dependency analysis of PRAM algorithms. Specifically, 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 present a randomized algorithm whose competitive ratio is dependent on the dynamics of the communication medium and also on the nature of the dependencies among the t tasks characterized by the task graph.