108
D. Lin et al.
2.2 Steady-State Conditions of Queuing Models
As shown in Fig. 1, the data flow through the map and reduce ends can be
represented as two coupled queues. In the following, we investigate the steadystate conditions of both queueing models. Given the data rate λ, we can easily
show that the necessary and sufficient steady-state condition of the first queue
(i.e., the queue at the map stage) is λ ≤ K 1 μ, and also we can show that the
condition of the second queue (i.e., the queue at the reduce stage) is R T ≤
K 2 μ R . However, we cannot determine whether these two queues are capable of
achieving the steady state because of the unknown μ, which depends on both
the service rate at the mappers μ 0 and the service rate at the reducers. Also,
μ is interdependent with P B (shown in Eq. (1)), and neither of them can be
mathematically expressed in a closed form. In the following, we investigate the
computation of μ to achieve a necessary and sufficient steady-state condition.
Lemma 1. The following equation has at least one feasible solution
y 1 (μ) + y 2 (μ) − 1/μ = y 0 ,
(3)
any solution ˆ
μ satisfies ˆ
μ ∈ [μ min , μ max ], given μ min = 1/(1/μ 0 + mean
(min
j
W j )), μ max = μ 0 , y 1 (μ) = 1/μ, y 2 (μ) = 1/μ − P b × mean(min
i
W i ), and
y 0 = 1/μ 0 .
Proof. We proof it by contradiction. Set y(μ) = y 1 (μ) + y 2 (μ) − 1/μ. By Eq. (1),
we can get y 2 (ˆ μ) ≤ y(ˆ μ) ≤ y 1 (ˆ μ). If Eq. (3) has no feasible solution, then y 0 =
y 2 (ˆ μ) < y(ˆ μ) at ˆ
μ = μ min , otherwise μ min is the feasible solution. Since y(μ) is
continuous and we assume no feasible solution in the range of [μ min , μ max ], we
can deduce that y(ˆ μ) > y 0 for ˆ
μ ∈ [μ min , μ max ]. At ˆ
μ = μ max , we can achieve
that y(ˆ μ) > y 0 = y 1 (ˆ μ), which is contradicted with y(ˆ μ) ≤ y 1 (ˆ μ) by Eq. (1).
Beyond the proof, we present that at least one solution exists, which is
intuitively demonstrated in circle in Fig. 2, since y 2 (μ) ≤ y(μ) ≤ y 1 (μ),
y 2 (μ min ) = y 0 , and y 1 (μ max ) = y 0 .
If a unique solution ˆ
μ to Eq. (3) exists, we can easily show the necessary and sufficient steady-state condition as λ ≤ K 1 ˆ
μ for the first queue and
min{λ, K 1 ˆ
μ} ≤ K 2 μ R for the second queue (shown in Theorem 2). If multiple solutions to Eq. (3) exist, we cannot achieve the necessary and sufficient
steady-state condition. Instead, we can find the tightest sufficient (not necessary) condition. Denote that ˆ
μ min and ˆ
μ max as the minimal and maximal
feasible solutions, respectively. We can easily show that the tightest sufficient
(not necessary) steady-state condition: λ ≤ K 1 ˆ
μ min for the first queue and
min{λ, K 1 ˆ
μ min }+ ≤ K 2 μ R for the second queue. All the above-mentioned discussions can be summarized in Theorems 1 and 2, respectively.
Theorem 1. The necessary and sufficient steady-state condition of the coupled
queues for map and reduce stages exists if Eq. (3) has a unique solution ˆ
μ. The
necessary and sufficient steady-state condition can be shown as λ ≤ K 1 ˆ
μ for the
first queue and min{λ, K 1 ˆ
μ} ≤ K 2 μ R for the second queue.
D. Lin et al.
2.2 Steady-State Conditions of Queuing Models
As shown in Fig. 1, the data flow through the map and reduce ends can be
represented as two coupled queues. In the following, we investigate the steadystate conditions of both queueing models. Given the data rate λ, we can easily
show that the necessary and sufficient steady-state condition of the first queue
(i.e., the queue at the map stage) is λ ≤ K 1 μ, and also we can show that the
condition of the second queue (i.e., the queue at the reduce stage) is R T ≤
K 2 μ R . However, we cannot determine whether these two queues are capable of
achieving the steady state because of the unknown μ, which depends on both
the service rate at the mappers μ 0 and the service rate at the reducers. Also,
μ is interdependent with P B (shown in Eq. (1)), and neither of them can be
mathematically expressed in a closed form. In the following, we investigate the
computation of μ to achieve a necessary and sufficient steady-state condition.
Lemma 1. The following equation has at least one feasible solution
y 1 (μ) + y 2 (μ) − 1/μ = y 0 ,
(3)
any solution ˆ
μ satisfies ˆ
μ ∈ [μ min , μ max ], given μ min = 1/(1/μ 0 + mean
(min
j
W j )), μ max = μ 0 , y 1 (μ) = 1/μ, y 2 (μ) = 1/μ − P b × mean(min
i
W i ), and
y 0 = 1/μ 0 .
Proof. We proof it by contradiction. Set y(μ) = y 1 (μ) + y 2 (μ) − 1/μ. By Eq. (1),
we can get y 2 (ˆ μ) ≤ y(ˆ μ) ≤ y 1 (ˆ μ). If Eq. (3) has no feasible solution, then y 0 =
y 2 (ˆ μ) < y(ˆ μ) at ˆ
μ = μ min , otherwise μ min is the feasible solution. Since y(μ) is
continuous and we assume no feasible solution in the range of [μ min , μ max ], we
can deduce that y(ˆ μ) > y 0 for ˆ
μ ∈ [μ min , μ max ]. At ˆ
μ = μ max , we can achieve
that y(ˆ μ) > y 0 = y 1 (ˆ μ), which is contradicted with y(ˆ μ) ≤ y 1 (ˆ μ) by Eq. (1).
Beyond the proof, we present that at least one solution exists, which is
intuitively demonstrated in circle in Fig. 2, since y 2 (μ) ≤ y(μ) ≤ y 1 (μ),
y 2 (μ min ) = y 0 , and y 1 (μ max ) = y 0 .
If a unique solution ˆ
μ to Eq. (3) exists, we can easily show the necessary and sufficient steady-state condition as λ ≤ K 1 ˆ
μ for the first queue and
min{λ, K 1 ˆ
μ} ≤ K 2 μ R for the second queue (shown in Theorem 2). If multiple solutions to Eq. (3) exist, we cannot achieve the necessary and sufficient
steady-state condition. Instead, we can find the tightest sufficient (not necessary) condition. Denote that ˆ
μ min and ˆ
μ max as the minimal and maximal
feasible solutions, respectively. We can easily show that the tightest sufficient
(not necessary) steady-state condition: λ ≤ K 1 ˆ
μ min for the first queue and
min{λ, K 1 ˆ
μ min }+ ≤ K 2 μ R for the second queue. All the above-mentioned discussions can be summarized in Theorems 1 and 2, respectively.
Theorem 1. The necessary and sufficient steady-state condition of the coupled
queues for map and reduce stages exists if Eq. (3) has a unique solution ˆ
μ. The
necessary and sufficient steady-state condition can be shown as λ ≤ K 1 ˆ
μ for the
first queue and min{λ, K 1 ˆ
μ} ≤ K 2 μ R for the second queue.