Hardness of approximation and greedy algorithms for the adaptation problem in virtual environments

Over the past decade, wide-area distributed computing has emerged as a powerful computing paradigm. Virtual machines greatly simplify wide-area distributed computing by lowering the abstraction to benefit both resource users and providers. A virtual execution environment consisting of virtual machines (VMs) interconnected with virtual networks provides opportunities to dynamically optimize, at run-time, the performance of existing, unmodified distributed applications without any user or programmer intervention. We have formalized the adaptation problem in virtual execution environments, and shown that it is NP-hard to both, solve and approximate within a factor of m ^1/2-δ for any δ > 0, where m is the number of edges in the virtual overlay graph. We also designed and evaluated greedy adaptation algorithms and found them to work well in practice.