AuctionNet: Market oriented task scheduling in heterogeneous distributed environments

We propose a suite of market-oriented task scheduling algorithms to build an AuctionNet for heterogeneous distributed environments. In heterogeneous distributed environments, computing nodes are autonomous and owned by different organizations, for example peer-to-peer systems, desktop grids/clouds. To address such diverse heterogeneity and dynamism in systems, applications, and local policies, efficient and fair task scheduling becomes a challenging issue. To cope with such complexity in a distributed and noncooperative environment, we propose to use market-oriented incentive mechanisms to regulate task scheduling in a distributed manner. Further, to accommodate multiple objectives and criteria, we adopt a combined approach leveraging the advantage of both hypergraph theory and incentive mechanisms. We first formulate a general framework of market-oriented task scheduling in distributed systems. We then present two algorithms for task-bundle scheduling. Preliminary results demonstrate the satisfactory performance of our proposed algorithms. The remaining work to complete the PhD dissertation is then presented. The proposed research carries significant intellectual merits and potential broader impacts in the following aspects. (1) We propose the notion of task-bundle for the first time in the literature. Product-bundle has been a common marketing strategy in our daily life for a long time. In the emerging commercial clouds and desktop clouds, task-bundle could be a useful concept for computing and storage markets. (2) We propose efficient distributed mechanisms that are very suitable for such distributed systems. A novel algorithm combining hypergraph and incentive mechanisms achieves multi-objective optimization. (3) We conduct rigorous analytical study and prove that our algorithms ensure efficiency and fairness and in the meantime maximize social welfare. (4) Overall, this proposal lays a solid foundation and sheds light on future research and realworld applications in the broad area of task scheduling in distributed systems.