  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.
