BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR94-236
ENTRY:: March 10, 1997
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Distributed Scheduling in Finite Capacity Networks 
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Fizzano, Perry 
AUTHOR:: Stein, Clifford
DATE:: November, 1994 
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: Compressed Postscript at http://www.cs.dartmouth.edu/reports/TR94-236.ps.Z
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR94-236.pdf
ABSTRACT:: 
We consider the problem of scheduling unit-sized jobs in a distributed
network of processors.  Each processor only knows the number of jobs
it and its neighbors have.  We give an analysis of intuitive algorithm
and prove that the algorithm produces schedules that are within a
logarithmic factor of the length of the optimal schedule given that
the optimal schedule is sufficiently long.  
END:: ncstrl.dartmouthcs//TR94-236