Distributed computing

Earliest Deadline First -- pure alg does badly

• If you have k tasks where each takes 1 second and they have deadlines 1 sec, 2 sec, …, k sec, you can do them all.
• What if we add a new task that takes 1/1000 sec with deadline 0.5 seconds.
• We execute new task but no other task completes by its deadline.

Earliest Deadline First -- heuristic partial solution

• Never execute a task having negative slack time (no way it can finish on time).
• But this doesn’t necessarily lead to an optimal solution.
• Sometimes you are faced with two tasks, each of which could finish if you terminated the other.

Earliest Deadline First -- value density lower bound

• Suppose tasks have values and computation times. Value density = value/computation time.
• If all tasks have same value density, but different computation times, cannot guarantee better than a factor of ½ of optimal score.
• Can you think of an example?

Earliest Deadline First -- value density scenario

• No slack time for any task
• Task 1 lasts 1 sec, value of 1
• Task 2 arrives at 1-epsilon and lasts 2 secs, value of 2.
• Task 3 arrives at 1 and lasts epsilon seconds.
• Do we abandon task 1 for task 2 or do we do task 3?

Earliest Deadline First -- value density outcome 1

• If we drop task 1 in favor of task 2, then there might be more and more epsilon length tasks until time 3 – 2 epsilon when a task of length 2 arrives.
• Optimal algorithm would have done task 1, all the little epsilons, and then the final 2 second task. Optimal: 5 – 2 epsilon; Switcher: 2

Earliest Deadline First -- value density outcome 2

• If we don’t drop task 1 in favor of task 2, then there might be no more tasks.
• Optimal algorithm would have done task 2, whereas your algorithm did task 1 plus epsilon. Optimal: 2; Non-switcher: 1

Earliest Deadline First -- competitive factor

• At time 1-epsilon, your scheduler can’t know what to do, so an optimal (clairvoyant) scheduler may get at least a factor of 2 more.
• Meeting this competitive factor was the PhD work of Gilad Koren here at NYU.
• See the D-over algorithm in the pdf notes.
• Squash club puzzle.