Proactive resource allocation in fine -grained cycle sharing systems

Fine-Grained Cycle Sharing (FGCS) systems aim at utilizing the large amount of idle computational resources available on the Internet. Such systems allow guest jobs to run on a host if they do not significantly impact the local users of the host. Since the hosts are typically provided voluntarily, their availability fluctuates greatly. To provide fault tolerance to guest jobs without adding significant computational overhead, we propose techniques of proactive resource allocation that predict resource availability and apply the prediction to manage guest jobs. We present empirical studies on resource availability in FGCS systems and a prediction method. From the studies on resource contention, we develop a multi-state availability model that enables non-intrusive detection of failures. We analyze the traces collected from a production FGCS system. The results suggest the feasibility of predicting resource availability, and motivate our method of applying semi-Markov Process models for the prediction. Through the experiments on an FGCS testbed, we demonstrate that the prediction achieves an accuracy of 86% on average and outperforms linear time series models, while the computational cost is negligible. We apply the prediction in a proactive scheduler. The scheduler allocates guest jobs onto host machines with high availability as well as high computing capability. To reduce the work loss caused by inevitable failures, especially for long-running guest jobs, we develop failure-aware checkpointing methods that apply availability prediction to select checkpoint repositories and to determine checkpoint intervals . We evaluate these techniques on the FGCS testbed, using trace-based simulation. The results show that our techniques achieve better application performance than the prevalent methods which use checkpointing with a fixed periodicity on dedicated or randomly selected checkpoint servers. We describe the framework of our techniques of proactive resource allocation and its implementation in the iShare Internet sharing system that supports FGCS. The iShare system realizes a decentralized architecture for resource allocation