DAI-List Digest        Tuesday, 17 April 1990        Issue Number 5

Topics:
 New Paper Available

Please send submissions to DAI-List@mcc.com.  Send other requests,
such as changes in your e-mail address, to DAI-List-Request@mcc.com.
----------------------------------------------------------------------

Date: Tue, 27 Mar 90 11:41:43 CST
From: Bernardo Huberman <huberman@parc.xerox.com>
Subject: New paper available

"DYNAMICS OF RESOURCE ALLOCATION IN DISTRIBUTED SYSTEMS"

E. Lumer and B. A. Huberman
Xerox PARC

Abstract.

We study the dynamics of resource allocation in computer networks and
show that, when process transfer rates depend on the number of tasks
executing in the system, fairness of use cannot be achieved beyond a
critical size.  We then demonstrate how the establishment of a hierarchy
of process transfer rates allows for optimal and stable dynamical
resource allocation in very large systems.  These results are used to
introduce a suitable hierarchical control structure that achieves
optimal load balance with little overhead in communication.  We also
study the effects of information delays on fairness of use and show that
oscillations in resource utilization appear when such delays exceed a
certain value.  These oscillations can be prevented by the establishment
of informal links in the organization, in agreement with observations in
the social arena.