ABSTRACT
We give distributed approximation algorithms for job scheduling in a ring architecture. In contrast to almost all other parallel scheduling models, the model we consider captures the influence of the underlying communications network by spec- ifying 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 algorithms must balance both com- putational load and communication time.
The algorithms are simple, require no global con- trol, and work in a variety of settings. All come with small constant-factor approximation guar- antees; the basic algorithm yields schedules of length at most 4.22 times optimal. We also give a lower bound on the performance of any dis- tributed algorithm and the results of simulation experiments, which give better results than our worst-case analysis.
|