Paper Info
Title
Batch-Scheduling dags for internet-based computing
Abstract
The process of scheduling computations for Internet-based computing presents challenges not encountered with more traditional computing platforms. The looser coupling among participating computers makes it harder to utilize remote clients well, and raises the specter of a kind of “gridlock” that ensues when a computation stalls because no new tasks are eligible for execution. This paper studies the problem of scheduling computation-dags in a manner that renders tasks eligible for execution at the maximum possible rate. Earlier work has developed a framework for such scheduling when a new task is allocated to a remote client as soon as it returns the results from an earlier task. The proof in that work that many dags cannot be scheduled optimally within this paradigm signaled the need for a companion theory that addresses the scheduling problem for all computation-dags. A new, batched, scheduling paradigm for Internet-based computing is developed in this work. Although optimal batched schedules always exist, computing such a schedule is NP-Hard, even for bipartite dags. In response, a polynomial-time algorithm is developed for producing optimal batched schedules for a rich family of dags obtained by “composing” tree-structured building-block dags. Finally, a fast heuristic schedule is developed for “expansive” dags.
Year
DOI
Venue
2005
10.1007/11549468_31
Euro-Par
Keywords
Field
DocType
optimal batched schedule,fast heuristic schedule,earlier work,remote client,earlier task,new task,traditional computing platform,internet-based computing,batch-scheduling dag,renders task,scheduling problem,tree structure
Heuristic,Batch production,Job shop scheduling,Scheduling (computing),Computer science,Schedule,Job scheduler,Time complexity,Distributed computing,The Internet
Conference
ISBN
Citations 
PageRank 
3-540-28700-0
8
0.53
References 
Authors
12
2
Name
Order
Citations
PageRank
Grzegorz Malewicz1178175.89
Arnold L. Rosenberg22107640.21