Optimal distributed task scheduling in volunteer clouds. (May 2017)

• Record Type: Journal Article
• Authors: Sebastio, Stefano; Gnecco, Giorgio; Bemporad, Alberto
• Is Part Of: Computers & operations research. Volume 81(2017)
• Page Start: 231
• Page End: 246
• Publication Date: 2017-05
• Subjects: Cloud computing -- Distributed optimization -- Integer programming -- Combinatorial optimization -- ADMM; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.11.004
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A framework for task scheduling policies in a large-scale distributed cloud. A mathematical formulation driven by real system requirements. Model with: FIFO queue, tasks with deadlines, the actual load on the machines. Application of the distributed Alternating Direction Method of Multipliers (ADMM). Abstract: The ever increasing request of computational resources has shifted the computing paradigm towards solutions where less computation is performed locally. The most widely adopted approach nowadays is represented by cloud computing. With the cloud, users can transparently access to virtually infinite resources with the same aptitude of using any other utility. Next to the cloud, the volunteer computing paradigm has gained attention in the last decade, where the spared resources on each personal machine are shared thanks to the users' willingness to cooperate. Cloud and volunteer paradigms have been recently seen as companion technologies to better exploit the use of local resources. Conversely, this scenario places complex challenges in managing such a large-scale environment, as the resources available on each node and the presence of the nodes online are not known a-priori. The complexity further increases in presence of tasks that have an associated Service Level Agreement specified, e.g., through a deadline. Distributed management solutions have then be advocated as the only approaches that are realistically applicable. In this paper, we propose a framework to allocate tasks according to different policies, defined by suitable optimization problems. Then, we provide a distributed optimization approach relying on the Alternating Direction Method of Multipliers (ADMM) for one of these policies, and we compare it with a centralized approach. Results show that, when a centralized approach can not be adopted in a real environment, it could be possible to rely on the good suboptimal solutions found by the ADMM.