Wednesday, November 21, 2012

Simulating Stochastic Models

Recently I’ve been tasked with working on an infrastructure system which comprises several computationally intensive tasks that can be scheduled on a series of host machines. Some tasks have dependencies on other tasks, and cannot be scheduled before its dependencies have finished. In a simplified setup we assume that any task can run on any machine, provided that machine is not busy with running another task.

The following picture illustrates the system

Host A runs task 1 and 3, while host B runs task 2 and 4. Task 4 has a dependency on task 1 and task 3 has one on task 2. When all tasks are completed the job is considered completed. It is evident from the picture that a task (task 3) may be delayed in its scheduling even though its dependencies are satisfied due to resource constraints.