A time optimization algorithm for scheduling bag-of-task applications in auction-based proportional share systems

Grid and peer-to-peer (P2P) network technologies enable aggregation of distributed resources for solving large-scale and computationally-intensive applications. These technologies are well-suited for bag-of-tasks (BoT) applications, because each application consists of many parallel and independent tasks. With multiple users competing for the same resources, the key challenge is to finish a user application within a specified deadline. In this paper, we propose a time optimization algorithm that schedules a user application on auction-based resource allocation systems. These allocation systems, which are based on proportional share, allow users to bid higher in order to gain more resource shares. Therefore, this algorithm adjusts a user bid periodically on these systems in order to finish the application on time.