IC-Scheduling: A New Scheduling Paradigm for Task-Hungry Platforms

Arnold Rosenberg
ACM Distinguished Speaker
Northeastern University and University of Massachusetts
Wachman 447
Wednesday, April 24, 2013 - 11:00
Technological and economic developments have made the Internet a viable platform for a new, "collaborative" modality of Internet-based computing (IC, for short). Within this modality, the owner of a large, typically compute-intensive, computation enlists remote clients to collaborate in performing the computation.  when the computation comprises only independent tasks, the temporal unpredictability of IC-- communication is over the Internet; computing is by clients who arrive at unpredictable times and who are typically not dedicated to the computation-- is at worst an annoying source of slowdown.  But when the computation's tasks have interdependencies that prioritze their execution, then the temporal unpredictability can confute attempts to benefit from parallel execution of tasks and can lead to a form of gridlock wherein no new tasks can be allocated to remote clients pending completion of already allocated tasks. In recent papers, we have proposed a new scheduling paradigm that aims to respond to the new challenges of IC.  Faced with the impossibility of scheduling to accomodate critical paths in a computation, we seek to schedule in a way that always renders as many tasks as possible eligible for allocation to remote clients. This has the dual goal of maximizing the utilization of available clients and minimizing the likelihood of gridlock.  We have formalized this scheduling problem and, under idealized assumptions, have developed the rudiments of an algorithmic theory of how to schedule complex computations for IC. I begin this talk with the concepts underlying the theory and the algorithms that emerge from them. I then describe several familiar computations and computational paradigms that the nascent theory can schedule optimally.  I finally describe simulation experiments whose results suggest that the theory's schedules have a measurable benign effect on "real" Internet-based computing.