Computer Science Department
School of Computer Science, Carnegie Mellon University


On Distributed Network Resource Allocation

Andrea Werneck Richa

August 1998

Ph.D. Thesis

Keywords: Distributed network, resource allocation, approximation algorithm, randomized algorithm, shared object, wide-area 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, storage-time 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 wide-area networks. Second, we present an off-line polynomial-time 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 polynomial-time O(log n)-approximation algorithm for finding an embedding of a network with nprocessors into an n-node linear array so as to minimize the weighted sum of the edge dilations -- i.e., for the minimum linear arrangement problem. This problem is NP-hard, 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 storage-time product and the minimum containing interval graph problem.

122 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by