
CMUCS98146
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS98146
On Distributed Network Resource Allocation
Andrea Werneck Richa
August 1998
Ph.D. Thesis
CMUCS98146.ps
CMUCS98146.pdf
Keywords: Distributed network, resource allocation, approximation
algorithm, randomized algorithm, shared object, widearea network,
hierarchical model, expected cost, packet routing, scheduling, Lovasz
Local Lemma, optimal schedule, network emulation, embedding, congestion,
dilation, ordering, linear arrangement, linear array, combinatorial
optimization, interval graph, storagetime product, spreading metric, planar graph
This thesis addresses several resource allocation problems that arise in
the context of distributed networks. First, we present a scheme for
accessing shared copies of objects in a network that has asymptotically
optimal expected cost per access for a class of cost functions that
captures the hierarchical structure of most widearea networks. Second, we
present an offline polynomialtime algorithm that finds an asymptotically
optimal schedule for the movement of packets whose paths through a network
have already been determined. This is an improvement on a previous
result by Leighton, Maggs, and Rao, who proved the existance of such
schedules; their proof, however, was not constructive. Finally we present
a polynomialtime O(log n)approximation algorithm for finding an
embedding of a network with nprocessors into an nnode
linear array so as to minimize the weighted sum of the edge dilations 
i.e., for the minimum linear arrangement problem. This problem is NPhard,
and the previous best approximation bound known was O(log n log log n).
In the case of planar networks, we bring the approximation factor down to
O(log log n). We also extend our approximation techniques to the
minimum storagetime product and the minimum containing interval graph
problem.
122 pages
