Resource allocation in networked and distributed environments
Aravind Srinivasan, Srinivasan Parthasarathy · 2006
A central challenge in networked and distributed systems is resource management: how can we partition the available resources in the system across competing users, such that individual users are satisfied and certain system-wide objectives of interest are optimized? In this thesis, we deal with many such fundamental and practical resource allocation problems that arise in networked and distributed environments. We invoke two sophisticated paradigms---linear programming and probabilistic methods---and develop provably-good approximation algorithms for a diverse collection of applications. Our main contributions are as follows. 1. Assignment problems: An assignment problem involves a collection of objects and locations, and a load value associated with each object-location pair. Our goal is to assign the objects to locations while minimizing various cost functions of the assignment (determined by the load values). This abstract setting models many applications in manufacturing, parallel processing, distributed storage, and wireless networks. We present a single algorithm for assignment which generalizes and unifies many classical assignment schemes known in the literature (V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. Approximation Algorithms for Scheduling on Multiple Machines. IEEE FOCS 2005). Our scheme is derived through a fusion of linear algebra and randomization. In conjunction with other ideas, it leads to novel guarantees for multi-criteria parallel scheduling, broadcast scheduling, and social network modeling ( Samir Khuller, Rajiv Gandhi, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent Rounding in Bipartite Graphs. To appear in Journal of the ACM; earlier version appears in IEEE FOCS 2002). 2. Precedence constrained scheduling: We consider two precedence constrained scheduling problems, namely sweep scheduling (V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan, and Sybille Zust. Provable Parallel Scheduling for Generalized Sweep Scheduling. To appear in Journal of Parallel and Distributed Computing; earlier version appears in IEEE IPDPS 2005) and tree scheduling ( V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. Scheduling on Unrelated Machines under Tree-like Precedence Constraints. To appear in Algorithmica; earlier version appears in APPROX 2005), which are inspired by emerging applications in high performance computing. Through a careful use of randomization, we devise the first approximation algorithms for these problems with near-optimal performance guarantees. 3. Wireless communication: Wireless networks are prone to interference. This prohibits proximate nodes in the network from transmitting simultaneously, and introduces fundamental challenges in the design of wireless communication protocols. We develop fresh geometric insights for characterizing and reasoning about wireless interference. We combine our geometric analysis with linear programming and randomization, to obtain centralized and distributed algorithms for latency minimization (V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. End-to-End Packet Scheduling in Wireless Ad Hoc Networks. ACM-SIAM SODA 2004) and throughput capacity estimation in wireless networks (V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. Algorithmic Aspects of Capacity in Wireless Networks. ACM SIGMETRICS 2005 ). In summary, the innovative use of linear programming and probabilistic techniques for resource allocation, and the novel ways of connecting them with application-specific ideas is the pivotal theme and the focal point of this thesis.