Guidelines for data-parallel cycle-stealing in networks of workstations. II. On maximizing guaranteed output

For pt. I see 12th IEEE Intl. Parallel Proc. Symp., p. 519-23 (1998). We derive efficient guidelines for scheduling data-parallel computations within a draconian mode of cycle-stealing in networks of workstations wherein an interruption by the owner of the “borrowed” workstation kills all jobs currently in progress. We derive both adaptive and non-adaptive scheduling guidelines that maximize, up to low-order additive terms, the amount of work that one is guaranteed to accomplish during a cycle-stealing opportunity, no matter when the opportunity is interrupted-up to a prespecified number of times