Job Scheduling in Rings

Dartmouth Technical Report PCS-TR94-213

	Perry Fizzano
	Clifford Stein
	David R. Karger
	Joel Wein

Date:  1994

URL (compressed postscript): <http://www.cs.dartmouth.edu/reports/TR94-213.ps.Z> (96KB)

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR94-213.pdf> (224KB)

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 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 algorithms must balance both computational load and
 communication time.
 	The algorithms are simple, require no global control, and work
 in a variety of settings.  All come with small constant-factor
 approximation guarantees; the basic algorithm yields schedules of
 length at most 4.22 times optimal.  We also give a lower bound on
 the performance of any distributed algorithm some results for a simple
 capacitated case, and the results of simulation experiments, which
 give better results than our worst-case analysis.