A New Fairness Model based on User’s Objective for Multi-user Multi-processor Online Scheduling

Supercomputers, grids and clusters in High Performance Computing(HPC) and web servers in client-server networking have gained immense practical significance as Service Oriented System(SOS) in modern day computation [1]. Unlike the traditional computing system such as personal computer, the SOS supports multiple users. The users compete for system’s resources for execution of their jobs. The most popular cluster scheduler MAUI [2] and the well-known BOINC platform [3] deal with a number of competing users, where each user submits a set of jobs simultaneously and seeks for a minimum time of completion(makespan) for their respective submissions. A non-trivial challenge for the SOS is to ensure fair scheduling of jobs for multiple users while optimizing their respective makespans.
In this paper, we define and quantify fairness as a performance measure based on user’s objective for any resource allocation algorithm in multi users HPC systems. Particularly, we consider processors as the resources to be shared and makespan as the user’s objective in the Multi-user Multi-processor Online Scheduling Problem(MUMPOSP). We formally define the MUMPOSP as follows.

Multi-user Multi-processor Online Scheduling Problem(MUMPOSP)

• •

  Inputs: We are given a set of $m$ identical processors, i.e. $M$=$\{M_{1},M_{2},..,M_{m}\}$ and a set of $n$ jobs, where $m\geq 2$ and $n>>>m$. Let $U_{r}$ represents a user, where $1\leq r\leq k$ and $J^{r}$ is the sequence of jobs requested by user $U_{r}$, where $J^{r}$=$(J^{r}_{i}|1\leq i\leq n_{r})$ such that $J$=$\bigcup_{r=1}^{k}{J^{r}}$, $\sum_{r=1}^{k}{n_{r}}$=$n$ and $J^{x}\cap J^{y}$=$\phi$, where $x\neq y$ and $1\leq(x,y)\leq k$. The processing time of job $J^{r}_{i}$ is $p^{r}_{i}$, where $p^{r}_{i}\geq 1$.

• •

  Output: Generation of a Schedule($S$) in which makespan for each user ($U_{r}$) is denoted by $C^{r}_{max}$=$\max\{c^{r}_{i}|1\leq i\leq n_{r}\}$, where $c^{r}_{i}$ is the completion time of job $J^{r}_{i}$

• •

  Objective: Minimize $C^{r}_{max}$,   $\forall U_{r}$.

• •

  Constraint: The scheduler can receive a batch of at most $r$ jobs at any time step and the jobs must be irrevocably scheduled before the arrival of next batch of jobs, where $1\leq r\leq k$.

• •

  Assumption. The jobs are independent and are requested from $k$ parallel users, where $k\geq 2$

Illustration of MUMPOSP. For simplicity and basic understanding of the readers, we illustrate an instance of MUMPOSP for scheduling of $n$ jobs that are submitted by $k$ users($U_{r}$) as shown in Figure 1. Here, $M_{1}$, $M_{2}$,…,$M_{m}$ represent $m$ identical machines and $U_{1}$, $U_{2}$,…,$U_{k-1}$, $U_{k}$ denote job sequences for $k$ users. Here, each user has $\frac{n}{k}$ jobs. Jobs are submitted in batches online, where a batch is constructed after receiving exactly one job from each user(as long as an user has an unscheduled job). A batch consists of at least one job. Therefore, we have at least $1$ batch, where $k$=$n$ and at most $n-k+1$ batches, where any one of the users $U_{r}$ has $n_{r}$=$n-k+1$ and remaining users have exactly one job each. Each user($U_{r}$) seeks to obtain a minimum value for its makespan($C^{r}_{max}$) as the output, rather than the overall makespan($C_{max}$) of the system. Hence, it is indispensable for the scheduler to be fair while optimizing the $C^{r}_{max}$ for each user.

Representation of MUMPOSP. By following general framework $\alpha|\beta|\gamma$ of Graham et al.[16], we represent MUMPOSP as $MUMPOSP(k,P_{m}|C^{r}_{max})$, where $P_{m}$ denotes $m$-identical machines and $k$ is the number of users.

Perspectives of Fairness. Fairness has been considered as a major performance criterion for the scheduling algorithms in multi-user systems [4, 5]. Fairness has been studied from two perspectives such as allocation of resources to the users and user’s objective. Fairness of an algorithm with respect to resource allocation, guarantees uniform allocation of resources to the competing users [6]. The resources to be shared are application dependent. For example, in client-server networking, the shared resources may be throughput or network delay or specific time quantum [7, 8], whereas in distributed systems, the resources may be processors or memory or time slice [9, 10].
Algorithmic fairness based on user’s objective is evaluated by the objective values achieved for respective users. An equality in the obtained objective values for a user ensures fairness of a scheduling algorithm. It is important for a fairness measure to define the equality for quantifying how far an achieved objective value is far from the defined equality.

Related Work. Fairness as a quantitative performance measure based on resource allocation was comprehensively studied by Jain et al. [6]. A set of properties for an ideal fairness measure was defined and a fairness index $F(x)$ was proposed for resource allocation schemes. If any scheduling algorithm assigns resources to $k$ competing users such that $r^{th}$ user gets an allocation of $x_{r}$. then $F(x)$ is defined as follows.

                            $F(x)$=$\frac{[{\sum_{r=1}^{k}{x_{r}}}]^{2}}{\sum_{r=1}^{k}{{x_{r}}^{2}}}$,            where $x_{r}\geq 0$.

The value of $F(x)$ is bounded between $0$ and $1$ to meaningfully show percentage of fairness and discrimination of a resource allocation scheme for each user. Fairness based on sharing of resources such as processors, memory, system clock and system bus in multi-programmed multi-user system was well studied in [9-11]. Some recent works with contributions on algorithmic fairness of online scheduling can be found in [17-18]. According to our knowledge, study of fairness based on user’s objective has not been exhaustively studied in the literature.
In [12-15], stretch matrix has been considered as a user’s objective based fairness measure for resource scheduling algorithms in multi-user system. Stretch($d^{r}_{A}$) is defined as a degradation factor in the objective value obtained by any algorithm A for each user $U_{r}$. Let us consider $V^{r}_{A}$ is the objective value achieved by algorithm A and $V^{r}_{OPT}$ is the optimum objective value for respective $U_{r}$. Now, stretch can be defined as
                             $d^{r}_{A}$=$\frac{V^{r}_{A}}{V^{r}_{OPT}}$

The objective of any scheduling algorithm is to incur an equal stretch for each $U_{r}$ to ensure fairness. Stretch matrix guarantees fairness based on equality in achieved objective values. However, it fails to bound the fairness and unable to show the exact value of fairness per user as well as overall fairness of a scheduling algorithm. Further, the discrimination of any scheduling algorithm for the deprived users can not be captured by the stretch matrix. Therefore, it is quintessential to define a formal fairness measure based on user’s objective.

Our Contribution. In our work, we propose a new model for fairness in Multi-user Multi-processor Online Scheduling Problem(MUMPOSP). We introduce and formally define quantitative fairness measures based on user’s objective by optimizing makespan for individual user in our proposed fairness model. We also define the unfairness of deprived users and absolute fairness of an algorithm. We obtain lower bound results for the absolute fairness for $m$-identical machines with equal length jobs. We show that our proposed fairness model can serve as a framework for measuring algorithmic fairness by considering various optimality criteria such as flow time and sum of completion times.

We develop a new fairness model in which, we define five quantitative measures to ensure algorithmic fairness. Instead of considering the resource allocation at the input level, the model considers the achieved value of user’s makespan at the output level to determine the fairness of a scheduling algorithm. The model captures the issues of relative and global parameters for fairness by a Fairness Index(FI). The issues of unfairness is captured by a Discrimination Index(DI). The FI includes fairness measures such as Relative Fairness(RF) and Global Fairness(GF). Higher value of any fairness measure indicates more fair algorithm. The DI includes unfairness measures such as User Discrimination Index(UDI), Global Discrimination Index(GDI) and Relative Discrimination Index(RDI). Lower value of any unfairness measure indicates more fair algorithm. Before defining the fairness measures, we illustrate our proposed fairness model and discuss the characteristics of a good fairness model as follows.

Illustration of our Proposed Fairness Model. We illustrate our proposed fairness model as shown in Figure 2. The model considers the MUMPOSP and captures the fairness of online scheduling algorithm by considering the makespan($C^{r}_{max}$) of individual user at the output.

We define absolute fairness as a quantitative measure and provide lower bound results for characterization of the same as follows.

Lemma 1. If any algorithm A incurs ${RDI}^{r}_{A}$=$0$, $\forall U_{r}$, then it achieves absolute fairness.
Proof. If ${RDI}^{r}_{A}$=$0$, $\forall U_{r}$, then by Eq. (8), we have
            ${RF}(C^{r}_{A})\geq{GF}(C^{r}_{A})$                                                             (10)
By Eqs. (3) and (10), we can infer that ${RF}(C^{r}_{A})$=${GF}(C^{r}_{A})$, $\forall U_{r}$
Therefore Lemma 1 holds true. $\Box$

Theorem 1. Any algorithm that achieves absolute fairness for $MUMPOSP(k,P_{2}|C^{r}_{max})$ must be at least $(\frac{1}{k})$-fair, where $k\geq 2$ and $1\leq r\leq k$.
Proof. Let us consider an instance of $MUMPOSP(k,P_{2}|C^{r}_{max})$, where $k$=$2$. We analyze two cases based on $n_{r}$ as follows.
Case $1$: $n_{1}\neq n_{2}$.
Case $1$.(a): If the first job pair($J^{1}_{1},J^{2}_{1}$) are scheduled on different machines. Let us consider the following instance $U_{1}:<J^{1}_{2}/2,J^{1}_{1}/1>$, $U_{2}:<J^{2}_{1}/1>$, where each job is specified by its processing time. Assigning $J^{1}_{1}/1$ and $J^{2}_{1}/1$ to machines $M_{1}$ and $M_{2}$ respectively followed by the assignment of $J^{1}_{2}/2$ to either of the machines such that $C^{1}_{A}$=$3$ and $C^{2}_{A}$=$1$, where $C^{1}_{OPT}\geq 1.5$ and $C^{2}_{OPT}\geq 0.5$. Therefore, we have $\frac{C^{1}_{OPT}}{C^{1}_{A}}\geq\frac{1}{2}$ and $\frac{C^{2}_{OPT}}{C^{2}_{A}}\geq\frac{1}{2}$
Case $1$.(b): If the first job pair($J^{1}_{1},J^{2}_{1}$) are scheduled on the same machine. Let us consider the following instance $U_{1}:<J^{1}_{3}/2,J^{1}_{2}/1,J^{1}_{1}/1>$, $U_{2}:<J^{2}_{2}/2,J^{2}_{1}/1>$. If the first job pair($J^{1}_{1}/1,J^{2}_{1}/1$) are scheduled either on machine $M_{1}$ or on $M_{2}$, then by assigning the next pair of jobs ($J^{1}_{2},J^{2}_{2}$) to the same or different machines, followed by the assignment of job $J^{1}_{3}/2$ such that $C^{1}_{A}$=$4$ and $C^{2}_{A}$=$3$, where $C^{1}_{OPT}\geq 2$ and $C^{2}_{OPT}\geq 1.5$. Therefore, we have $\frac{C^{1}_{OPT}}{C^{1}_{A}}\geq\frac{1}{2}$ and $\frac{C^{2}_{OPT}}{C^{2}_{A}}\geq\frac{1}{2}$.
Case 2: $n_{1}$=$n_{2}$.
Case 2.(a): If the first job pair($J^{1}_{1},J^{2}_{1}$) are scheduled on different machines. Let us consider the following instance $U_{1}:<J^{1}_{3}/2,J^{1}_{2}/1,J^{1}_{1}/1>$, $U_{2}:<J^{2}_{3}/2,J^{2}_{2}/2,J^{2}_{1}/1>$. Assigning jobs $J^{1}_{1}/1$ and $J^{2}_{1}/1$ to machines $M_{1}$ and $M_{2}$ respectively, followed by the assignment of the subsequent jobs as shown in Figure 3.(a), such that $C^{1}_{A}$=$4$ and $C^{2}_{A}$=$5$, where $C^{1}_{OPT}\geq 2$ and $C^{2}_{OPT}\geq 2.5$. Therefore, we have $\frac{C^{1}_{OPT}}{C^{1}_{A}}\geq\frac{1}{2}$ and $\frac{C^{2}_{OPT}}{C^{2}_{A}}\geq\frac{1}{2}$.
Case 2.(b): If the first job pair($J^{1}_{1},J^{2}_{1}$) are assigned to the same machine. We consider the same instance of Case 2.(a). Assigning $J^{1}_{1}/1$ and $J^{2}_{1}$ on either machine $M_{1}$ or on $M_{2}$, followed by the assignment of the subsequent jobs as shown in Figure3.(b) such that $C^{1}_{A}$=$4$ and $C^{2}_{A}$=$5$. Therefore, we have $\frac{C^{1}_{OPT}}{C^{1}_{A}}\geq\frac{1}{2}$ and $\frac{C^{2}_{OPT}}{C^{2}_{A}}\geq\frac{1}{2}$. $\Box$

We show that our proposed Fairness Index can be served as a framework for measuring fairness of any algorithm based on well-known user’s objectives such as sum of completion times($S^{r}$) or weighted sum of completion times($W^{r}$) or sum of flow times($SF^{r}$). Selection of an user’s objective is application dependent. For instance, users of interactive systems require optimized value for respective flow time $f^{r}$, where $f^{r}_{i}$ of any $J^{r}_{i}$ is the difference between its completion time $c^{r}_{i}$ and arrival time($t^{r}_{i}$). We now define relative fairness measures based on the above mentioned user’s objectives respectively by our proposed FI.

• •

  Sum of Completion Times($S^{r}$): Here, the objective for each $U_{r}$ is to obtain a minimum $S^{r}$=$\sum_{i=1}^{n_{r}}{c^{r}_{i}}$. The relative fairness for any $U_{r}$, obtained by any algorithm A based on $S^{r}$ is defined as
             $R_{A}(S^{r}_{A})$=$\frac{S^{r}_{OPT}}{S^{r}_{A}}$,          where $S^{r}_{OPT}$ is the optimum value for $S^{r}$.
  

• •

  Weighted Sum of Completion Times($W^{r}$): Here, the $c^{r}_{i}$ is associated with certain positive weight $w^{r}_{i}$. The objective for each $U_{r}$ is to obtain a minimum $W^{r}$=$\sum_{i=1}^{n_{r}}{w^{r}_{i}\cdot c^{r}_{i}}$. The relative fairness for any $U_{r}$ obtained by algorithm A based on $W^{r}$ is defined as
             $R_{A}(W^{r}_{A})$=$\frac{W^{r}_{OPT}}{W^{r}_{A}}$           where, $W^{r}_{OPT}$ is the optimum value for $W^{r}$.
  

• •

  Sum of Flow Times(${SF}^{r}$): Here, each $U_{r}$ wants a minimum value for respective ${SF}^{r}$=$\sum_{i=1}^{n_{r}}{f^{r}_{i}}$, where $f^{*r}_{i}$ is the desired value of $f^{r}_{i}$ and ${SF}^{r}_{OPT}$=$\sum_{i=1}^{n_{r}}{f^{*r}_{i}}$. The relative fairness for any $U_{r}$ obtained by algorithm A based on ${SF}^{r}$ is defined as
                               $R_{A}({SF}^{r}_{A})$=$\frac{{SF}^{r}_{OPT}}{{SF}^{r}_{A}}$.

In our work, we addressed the non-trivial research challenge of defining a new fairness model with quantitative measures of algorithmic fairness for Multi-users Multi-processor Online Scheduling Problem(MUMPOSP) based on user’s objective. We formally presented the MUMPOSP with an illustration followed by perspectives on fairness. We proposed a new fairness model and defined five quantitative measures to ensure algorithmic fairness by considering minimization of makespan as the user objective. By considering the properties of a good fairness model, our fairness measures were formally defined. We defined absolute fairness and obtained lower bound results for MUMPOSP with identical machines for equal length jobs. We show that our proposed fairness measure can serve as a framework for measuring algorithmic fairness based on other well-known user’s objective such as flow time and completion time.
Scope of Future Work. We assumed a theoretical bound for the value of $C^{r}_{OPT}$ for each $U_{r}$. It is still open to find a realistic bound for the value of $C^{r}_{OPT}$. It is a non-trivial research challenge to compare the fairness of any two algorithms $A$ and $B$, when global fairness of algorithm $A$ and algorithm $B$ are same and the relative fairness of $A$ is more than the relative fairness of $B$ for some users or vice versa. In this scenario, it is interesting to make a trade-off by considering the number of users and individual relative fairness of each user for comparison of fairness of two different algorithms.