Graduate Exam Abstract

Vladimir Shestak

Ph.D. Preliminary

April 4, 2007, 1:30 pm

Engineering C101B

Robust Resource Allocation in Parallel and Distributed Computing Systems

Abstract: Often, modern parallel and distributed computing systems must operate in an environment replete with uncertainty while providing a required level of quality of service (QoS). Determining a resource allocation that accounts for this uncertainty in a way that can provide a guarantee that a given level of QoS is achieved is an important research problem. The first part of this research presents the deterministic mathematical models and sophisticated resource allocation techniques designed to maximize the robustness of certain performance characteristics for parallel and distributed systems operating in overloaded and non-overloaded mode on periodically updated data sets. A large-scale shipboard computer system, designed for the US Navy, was used as a target system in this work. The second part defines a new stochastic methodology for quantifying a resource allocations ability to satisfy QoS constraints in the midst of uncertainty in system parameters. This new stochastic framework, where uncertainty in system parameters and its impact on system performance are modeled stochastically, is used to derive a quantitative probabilistic expression for the robustness of a resource allocation. The proposed stochastic robustness metric was integrated in greedy and iterative heuristics, and its utility was analyzed in a variety of simulated distributed computing system environments. The third part is a current research that addresses resource allocation in distributed systems prone to random node failures and recoveries. The solution methods being developed utilize the principles of the Markov Decision Processes (MDP) extrapolated to large-scale system state spaces. As a state of the system is changing dynamically, the probabilistically most efficient mapping is selected at each stage determined by the highest expected outcome from the current and possible future system states. The preliminary results indicate a significant potential of this novel approach to resource allocation in unstable distributed systems. As part of Vladimir Shestaks research activity for IBM, his work involves the design of a stochastic algorithm for workload distribution in a new generation of IBM production printer controllers.

Adviser: H. J. Siegel
Co-Adviser: A. A. Maciejewski
Non-ECE Member:
Member 3: E. K. P. Chong ECE Dept.
Addional Members:


Program of Study: