Blog
About

77
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Multi-resource Fair Allocation with Bounded Number of Tasks in Cloud Computing Systems

      Preprint

      , , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Dominant resource fairness (DRF) is a popular mechanism for multi-resource allocation in cloud computing systems. In this paper, we consider a problem of multi-resource fair allocation with bounded number of tasks. Firstly, we propose the lexicographically max-min normalized share (LMMNS) fair allocation mechanism, which is a natural generalization of DRF, and design a non-trivial optimal algorithm to find a LMMNS fair allocation, whose running time is linear in the number of users. Secondly, we prove that LMMNS satisfies envy-freeness (EF) and group strategy-proofness (GSP), and analysis the approximation ratios of LMMNS, by exploiting the properties of the optimal solution. Thirdly, we propose a modified version of LMMNS, which is the second mechanism satisfying sharing incentive, EF, and GSP. Finally, we have implemented LMMNS, and show that it has a good average-case performance, especially when the number of resources is 2.

          Related collections

          Author and article information

          Journal
          2014-10-06
          2015-02-03
          1410.1255

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          Custom metadata
          cs.GT cs.NI

          Theoretical computer science, Networking & Internet architecture

          Comments

          Comment on this article