Distributed Job Scheduling in Rings

✍ Scribed by Perry Fizzano; David Karger; Clifford Stein; Joel Wein

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 235 KB
• Volume: 45
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1373

✦ Synopsis

We give a distributed approximation algorithm for job scheduling in a ring architecture. In contrast to many other parallel scheduling models, the model we consider captures the influence of the underlying communications network by specifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithm must balance computational load and communication time. The algorithm is simple, requires no global control, and yields schedules of length at most 4.22 times optimal. We also give a lower bound on the performance of any distributed algorithm and the results of simulation experiments which suggest better performance than does our worst-case analysis.