The Unreliable Assignment Problem

We introduce The Unreliable Assignment Problem, the UAP, as a framework for evaluating the effectiveness of fault tolerant systems. We also present a broad investigation into solutions to the UAP.;Modern computational environment tend to be highly distributed across pools of commodity hardware which can make high availability challenging. One solution is the use of mirrors that duplicate applications in a geographically separate location so that in the event of a power outage or natural disaster the application continues to run. Mirrored systems have the disadvantage of being extremely costly to run, primarily due to a duplication of resources. With extremely low latency links it has become possible to migrate the contents of a virtual machine over a physical link to be run on another machine.;We demonstrate that the UAP can be effectively modeled in terms of the standard bin packing problems. Additionally we present two algorithms that solve the UAP and result in lower resource requirements than systems that use mirrors, First Fit Reserved and First Fit Conversion. First Fit Reserved was able to produce comparable levels of fault tolerance as a mirror system for single failure problems on a fully connected graph while using 22.5% and 32.5% fewer bins overall in comparison to a mirror approach. First Fit reserved also had comparable levels of performance to a mirror in multiple failure scenarios on a fully connected graph using pairwise assignment but did not result in any measurable reduction in required resources. First Fit Conversion is designed specifically to operate on graphs with scale-free topology which are commonly found in large networks such as the Internet. First Fit Conversion resulted in comparable levels of fault tolerance as a mirror in single failure environments while using 48.5% to 49.5% fewer resources overall. First Fit Conversion performed poorly for multiple failure scenarios but modifications allow it to achieve comparable performance using comparable levels of resources.;In conclusion it is shown that the First Fit Reserved and First Fit Conversion algorithms have viable applications in real world fault tolerance systems and that they are effective in reducing overall resource requirements for comparable levels of performance when compared with those required by a standard mirrored system.