BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR86-129
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: An Algorithm for Resource Allocation Requiring Low Overhead Communication
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Marks, Ann
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1986
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:: PDF at http://www.cs.dartmouth.edu/reports/TR86-129.pdf
ABSTRACT::
	A heuristic algorithm for allocating resource units to sites
in a distributed system is presented.  Starting with a given
allocation of sites, the algorithm performs a series of optimizations
involving pairs of sites in an attempt to improve the worst pair-wise
imbalance present in the system; termination occurs when no further
improvement is possible.  After outlining the general form of the
algorithm, which effectively defines an entire family of algorithms,
we present theoretical results that speak to the performance of the
algorithm as measured in the number of optimizations that can be done,
the amount of control communication required and the worst case
imbalance of the resulting allocation.  Subsequently, two particular
algorithms in the family are given and the results of a simulation
study of their performance is presented.
END:: ncstrl.dartmouthcs//TR86-129