Pith. sign in

REVIEW 3 major objections 6 minor 11 references

Meeting QoS of Users in a Edge to Cloud Platform via Optimally Placing Services and Scheduling Tasks

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A global greedy heuristic can place edge-cloud services and schedule user tasks at near-optimal cost while meeting every user's deadline.

desk verdict The ILP model is a reasonable within-subfield contribution, but the global heuristic's prose description and pseudocode disagree in a way that undermines the near-optimality claim until corrected. read the letter →

arxiv 1908.04824 v1 pith:PMNDMMMP submitted 2019-08-13 cs.NI cs.DC

Matthew Turner , Hana Khamfroush This is my paper · ORCID
classification cs.NIcs.DC
keywords serviceplacementtaskschedulingedge-to-cloudplatformqualityofintegerlinearprogrammingNP-hardnessgreedyheuristiccostoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to show that a service provider can jointly choose where to place software services on edge cloudlets and which computational device should handle each user's task, so that every request meets its deadline while the provider's total cost is minimized. It casts that joint decision as an integer linear program and proves the problem is NP-hard by reducing the general assignment problem to it. The paper then proposes two greedy heuristics: one that fills each cloudlet with its own users' tightest-deadline tasks, and one that picks service/device pairs globally by the number of deadline-feasible tasks they can serve per unit of placement cost. The main empirical claim is that the global greedy heuristic lands close to the optimal ILP cost across the tested ranges of user count, QoS strictness, and cloudlet-versus-cloud pricing, while running far more cheaply. If that holds, providers can meet hard latency requirements in applications such as augmented reality and real-time video analysis without solving an exponentially hard optimization from scratch each time.

What carries the argument

The argument is carried by an ILP over two binary decision families: $X_{mj}$, whether service $m$ is placed on cloudlet $j$, and $Y_{tj}$, whether task $t$ is scheduled on device $j$. The objective sums placement costs $P^p_{mj}X_{mj}$ and serving costs $P^s_{M(t)j}Y_{tj}$; constraints enforce storage and processing limits per cloudlet, assign each task to exactly one device, force the completion time $\delta(t,j)=d_{J(t),j}\,t_{\mathrm{in}}+\sigma(t)+d_{J(t),j}\,t_{\mathrm{out}}$ below the QoS threshold $Q_t$, and allow scheduling only where the needed service is placed ($Y_{tj}\le X_{M(t)j}$). NP-hardness is shown by zeroing placement costs and making storage and deadlines infinite, which recovers the general assignment problem. The global heuristic's operative score is the profit of a service/device pair: the number of tasks of that service type that can still meet their deadlines on that device, divided by the placement cost, and the algorithm repeatedly commits to the highest-profit pair until every task is scheduled.

What would settle it

Under the paper's own parameters (four cloudlets, hundreds of services, 300–500 tasks, QoS factor 2.5 to 5), run the global greedy and the ILP optimum on every Monte-Carlo replication and record the cost ratio; if any tested scenario has the greedy cost more than ten percent above optimal, or leaves any user's deadline unmet while the ILP meets it, the paper's 'close to optimal' claim fails within its stated regime. A complementary adversarial search over tiny instances (four cloudlets, a handful of tasks) would establish whether the greedy-to-optimal gap is bounded or can grow without limit.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is that joint service placement and task scheduling in a three-tier edge-to-cloud platform—users, cloudlets, and remote cloud—admits a single ILP formulation whose objective is to minimize placement plus serving cost while satisfying per-task deadline, storage, and processing constraints, and that this problem is NP-hard. The companion algorithmic claim is that a global greedy rule, which repeatedly commits to the service/cloudlet combination with the highest ratio of deadline-feasible tasks served to placement cost, performs close to the ILP optimum in simulation and clearly outperforms a local greedy that packs each cloudlet with its own users' tightest-deadline services first. The paper also claims that QoS awareness is affordable: a QoS-less scheduler drops more than thirty percent of tasks in the simulated settings, while the QoS-aware version drops none, at only a modest increase in provider cost.

Load-bearing premise

The load-bearing premise is that every task is known in advance and arrives at the same time, with deterministic execution and communication times; if requests arrive dynamically or runtimes vary, the ILP and both heuristics no longer directly apply, so the near-optimality result would not automatically transfer.

Editorial extensions

If this is right

  • The global greedy offers a practical way to meet all user deadlines at near-optimal provider cost without solving an ILP, so deployments where the optimum is computationally out of reach can still approach it.
  • Cloudlets that consider remote requests, not just their locally connected users, achieve lower provider cost, which supports the paper's recommendation for system-wide awareness in edge-cloud management.
  • As the QoS deadline becomes looser, the global heuristic's cost converges to the optimum because both it and the optimum shift more tasks to the inexpensive cloud, whereas the local heuristic cannot exploit that slack.
  • The QoS-aware formulation eliminates dropped tasks for only a modest cost increase, so enforcing user deadlines is presented as a worthwhile trade for the service provider.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper's static model, the near-optimality claim has not been tested for streaming workloads; re-running the global heuristic on batches of arriving tasks and comparing cost and deadline-miss rate against a reoptimizing baseline would show whether the result survives dynamic arrivals.
  • The NP-hardness reduction implies no polynomial algorithm can guarantee optimality unless P=NP, so the practically relevant open question is the heuristic's worst-case approximation ratio, which could be probed by searching small adversarial instances.
  • The profit score used by the global heuristic is a natural component to reuse for decisions the paper does not model, such as migrating a service between cloudlets or placing a popular service on several cloudlets at once.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies the joint problem of service placement and task scheduling in a three-tier edge-cloud platform, where each user task has a QoS deadline and the service provider minimizes placement and serving costs. The problem is formulated as an ILP (Eqs. 1-7), argued to be NP-hard via a reduction sketch to the general assignment problem, and solved approximately by two greedy heuristics: a local per-cloudlet algorithm and a global algorithm. Monte-Carlo simulations compare both heuristics against the Gurobi optimal solution while varying the number of users, the QoS factor, and the cost ratio beta. The paper claims that the global heuristic performs close to optimal with reduced complexity. The static, all-at-once workload model is acknowledged in the conclusion as a limitation and future work.

Significance. The problem is practically relevant, and the ILP formulation is clear and natural. The comparison between QoS-aware and QoS-less systems provides a useful sanity check, and the idea of comparing local versus global greedy decision making is reasonable. If the algorithmic description is made consistent and the empirical claims are properly supported with variability measures, the paper would be a useful contribution to edge-cloud service placement and task scheduling. At present, however, the central contribution is weakened by a major mismatch between the prose and pseudocode for the global heuristic, and by the lack of statistical evidence in the figures.

major comments (3)
  1. [V.D, Algorithms 1 and 2] The pseudocode of Algorithm 2 does not implement the 'highest profit' rule described in the text. In each while-loop iteration the algorithm sets s = service(t) for the first unscheduled task t, so only tasks of that single service are considered; the prose explicitly says that the algorithm considers every service on every computational device and chooses the service/device pair with the highest profit. In addition, the profit variable in the pseudocode is only a count of serviceable tasks and is never divided by the placement cost P^p_mj, so the placement-cost term of the objective function is absent from the greedy choice. Algorithm 1 has a related discrepancy: the prose says 'schedule all tasks that can be scheduled' after choosing a service, but the pseudocode schedules only the single task t1 with the tightest QoS constraint in each iteration. Because no code or data is released, the reader cannot determine whether the near-optimal results in Figures 4-6 are produced by the described heuristic or by a weaker variant. Please reconcile the prose and pseudocode, or provide the implemented code.
  2. [V.B, NP-Hardness] The NP-hardness argument is a sketch rather than a formal reduction. To establish NP-hardness, the authors should give an explicit polynomial-time mapping from instances of the general assignment problem to instances of their ILP and prove that optimal solutions correspond. In particular, the statement that Eq. 7 is 'non-conflicting' because X can always be set to one should be replaced with a concrete construction (e.g., zero placement costs and all X variables set to one) that preserves the objective value of the general assignment problem. As written, the generalization argument is plausible but not a complete proof.
  3. [V.E and Figures 4-6] The simulations use twenty Monte-Carlo scenarios per configuration, but Figures 4-6 show only point estimates or line plots without error bars, confidence intervals, or any statistical test. The paper's headline claim that the global heuristic is 'close to optimal' is therefore not quantitatively supported: the observed gaps could be small on average but large in individual instances, and the visual closeness cannot be assessed without a measure of variability. Please add error bars or confidence intervals and state the distribution of the optimality gap across the scenarios.
minor comments (6)
  1. [Title and Abstract] The phrase 'in a Edge to Cloud Platform' should be corrected to 'in an Edge-to-Cloud Platform'; similar grammar issues appear in the abstract.
  2. [Eq. (5)] In Eq. (5), d_J(t)j is described as a distance measured in ping time while tIn and tOut are packet sizes, so the product d_J(t)j * tIn has inconsistent units. Please define the distance and packet quantities so that completion time is derived consistently.
  3. [V.E, Simulation Parameters] Please specify the exact random distributions used to generate cloudlet locations, service-task mappings, and cost parameters. The table lists ranges but not the generation procedure, which is needed for reproducibility.
  4. [Table II] The table lists |M| = 1000 service types while |T| is at most 500; please clarify how service types are assigned to tasks and whether the setting allows each task to have a unique service type.
  5. [Figures 4-6] Adding error bars would also help readers see the overlap between the global heuristic and the optimal solution; consider using markers and a legend that make the three curves distinguishable in grayscale.
  6. [Conclusion and Model Scope] The static 'arrives all at once' assumption is acknowledged in the conclusion, but the model section should state explicitly that online arrivals and execution-time uncertainty are out of scope, so that the claims of near-optimality are properly qualified.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the heuristic results are benchmarked against an independently solved ILP, and the paper's self-citations are contextual rather than load-bearing.

full rationale

The paper's central quantitative claim—that the proposed local and global heuristics perform close to optimal—is tested against an optimal ILP solution computed with Gurobi (Section V.E: "All scenarios were generated using original Python scripts, solved using the Gurobi optimizer, as well as in-house software to simulate the proposed heuristics"). The heuristics contain no fitted parameters taken from the Gurobi results, and the objective function in the heuristics follows the same cost model rather than being reverse-engineered to match the optimal outputs. The NP-hardness argument (Section V.B) is a self-contained reduction to the general assignment problem, not an appeal to prior authority. The authors' citations of their own earlier work [2], [4] in Section II are related-work context ("In our previous work, we had considered...") and are not used to justify the ILP, the NP-hardness proof, or the simulation methodology. The prose/pseudocode discrepancy in Algorithm 2 (Section V.D) is a real reproducibility and correctness concern but not a circularity: whether the implemented heuristic follows the prose or the pseudocode, the benchmark optimal value is independently computed. Similarly, the static, all-at-once task arrival assumption is acknowledged in Section VII as future work ("we would like to consider a more realistic request schedule where requests are entered ... dynamically"), so it is a scope limitation rather than a hidden reuse of the result. No equation is defined in terms of the quantity it is said to predict, and no fitted value is renamed as a prediction. The paper therefore exhibits no significant circularity.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central claim of near-optimal heuristic performance is evaluated only in simulation with hand-picked parameters and simple deterministic models, so the reader must accept several domain assumptions about task arrivals, communication latency, and cloud capabilities before the results apply.

free parameters (5)
  • Beta (β) = 3 (varied in experiments)
    Cost multiplier for scheduling on a cloudlet versus the cloud; set by hand, not measured from provider prices.
  • QoS Factor = 2.5 (varied to 5)
    Multiplier defining each task's deadline as factor times computation time; chosen arbitrarily for simulation.
  • Cloud distance multiplier = 5 times max grid distance
    Arbitrary choice representing cloud latency relative to the grid.
  • Task computation time σ(t) = drawn from {2,4}
    Discrete values chosen for simulation; no real workload trace is used.
  • Communication packet sizes tIn, tOut = drawn from {2,4}
    Discrete values chosen for simulation.
assumptions (5)
  • domain assumption Each user has a single task that arrives to a computational device all at once (Section IV.A).
    This static batch assumption underlies both the ILP and the heuristics; dynamic arrivals are deferred to future work in Section VII.
  • domain assumption Each user is connected to exactly one local cloudlet and is unaware of where the request is solved (Section IV.A).
    Used to define the communication delay term in Eq. 5 and to structure the local heuristic.
  • domain assumption The cloud has effectively infinite storage and processing power and always hosts every service (Section IV.A).
    This makes the cloud a fallback for all tasks and avoids placement variables for the cloud.
  • domain assumption Completion time is modeled as δ(pt,j) = d_Jptq,j * tIn + σ(pt) + d_Jptq,j * tOut (Eq. 5).
    The linear dependence on packet sizes and ping distance is a simplification of real communication and processing behavior.
  • domain assumption QoS threshold Qt is a fixed multiple of computation time: Qt = QoS Factor * σ(pt) (Section V.E).
    A convenient parameterization for simulation; not derived from application requirements.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Meeting QoS of Users in a Edge to Cloud Platform via Optimally Placing Services and Scheduling Tasks." pith.science (2026). https://pith.science/paper/PMNDMMMP

@misc{pith2026190804824,
  author       = {Pith},
  title        = {Pith review of: Meeting QoS of Users in a Edge to Cloud Platform via Optimally Placing Services and Scheduling Tasks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PMNDMMMP}},
  note         = {Machine review of arXiv:1908.04824}
}
read the original abstract

This paper considers the problem of service placement and task scheduling on a three-tiered edge-to-cloud platform when user requests must be met by a certain deadline. Time-sensitive applications (e.g., augmented reality, gaming, real-time video analysis) have tight constraints that must be met. With multiple possible computation centers, the "where" and "when" of solving these requests becomes paramount when meeting their deadlines. We formulate the problem of meeting users' deadlines while minimizing the total cost of the edge-to-cloud service provider as an Integer Linear Programming (ILP) problem. We show the NP-hardness of this problem, and propose two heuristics based on making decisions on a local vs global scale. We vary the number of users, the QoS constraint, and the cost difference between remote cloud and cloudlets(edge clouds), and run multiple Monte-Carlo runs for each case. Our simulation results show that the proposed heuristics are performing close to optimal while reducing the complexity.

Figures

Figures reproduced from arXiv: 1908.04824 by the authors.

Figure 1
Figure 1. Example of “edge-to-cloud platform” to achieve a balance in the trade-off of users’ QoS and service provider cost. Here, cost to the service provider is expressed as a function of the number of services that they need to place on the computational devices, as well as the cost of serving the users’ requests on a particular device. QoS is expressed as a function of the time that users must wait for their tasks to be c… view at source ↗
Figure 2
Figure 2. Number of Users vs Percentage of Tasks Dropped: [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Number of Users vs Objective Value: Comparing [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Number of Users vs Objective Value: Comparing [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: QoS factor vs Objective Value: Comparing optimal [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 6
Figure 6. Figure 6: β Value vs Objective Value: Comparing optimal to local and global placement and scheduling algorithms. QoS constraint becomes more lax, the global algorithm approaches the optimal value. This is because it is optimal for the service provider to send tasks to the cloud.…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [1]

    H c MwT EkbUWýyԡ 0B # 0B # 0B # 0B # 0B # 0B 8 5999

    11em plus .33em minus .07em @technote 4000 4000 100 4000 4000 500 `\.=1000 = #1 #1 #1 0pt [0pt][0pt] #1 * \| ** #1 \@IEEEauthorblockNstyle \@IEEEauthorblockAstyle \@IEEEauthordefaulttextstyle \@IEEEauthorblockconfadjspace -0.25em \@IEEEauthorblockNtopspace 0.0ex \@IEEEauthorblockAtopspace 0.0ex \@IEEEauthorblockNinterlinespace 2.6ex \@IEEEauthorblockAinte...

    work page

  2. [2]

    M. Chen, B. Liang, and M. Dong. Joint offloading decision and resource allocation for multi-user multi-task mobile cloud. In 2016 IEEE International Conference on Communications (ICC) , pages 1--6, May 2016

    work page 2016

  3. [3]

    Service placement and request scheduling for data-intensive applications in edge clouds

    Vajihe Farhadi, Fidan Mehmeti, Tom La Porta, Ting He, Hana Khamfroush, Shiqiang Wang, and Kevin Chan. Service placement and request scheduling for data-intensive applications in edge clouds. IEEE INFOCOM , April 2019

    work page 2019

  4. [4]

    Edge-centric computing: Vision and challenges

    Pedro Garcia Lopez, Alberto Montresor, Dick Epema, Anwitaman Datta, Teruo Higashino, Adriana Iamnitchi, Marinho Barcellos, Pascal Felber, and Etienne Riviere. Edge-centric computing: Vision and challenges. SIGCOMM Comput. Commun. Rev. , 45(5):37--42, September 2015

    work page 2015

  5. [5]

    It's hard to share: Joint service placement and request scheduling in edge clouds with sharable and non-sharable resources

    Ting He, Hana Khamfroush, Shiqiang Wang, Tom La Porta, and Stephan Stein. It's hard to share: Joint service placement and request scheduling in edge clouds with sharable and non-sharable resources. IEEE ICDCS , July 2018

    work page 2018

  6. [6]

    Ksentini , T

    A. Ksentini , T. Taleb , and M. Chen . A markov decision process-based service migration procedure for follow me cloud. In 2014 IEEE International Conference on Communications (ICC) , pages 1350--1354, June 2014

    work page 2014

  7. [7]

    M. R. Rahimi, N. Venkatasubramanian, S. Mehrotra, and A. V. Vasilakos. On optimal and fair service allocation in mobile cloud computing. IEEE Transactions on Cloud Computing , 6(3):815--828, July 2018

    work page 2018

  8. [8]

    Towards qos-aware fog service placement

    Olena Skarlat, Matteo Nardelli, Stefan Schulte, and Schahram Dustdar. Towards qos-aware fog service placement. 2017 IEEE 1st International Conference on Fog and Edge Computing (ICFEC) , pages 89--96, 2017

    work page 2017

Show all 11 references
  1. [9]

    Y. Song, S. S. Yau, R. Yu, X. Zhang, and G. Xue. An approach to qos-based task distribution in edge computing networks for iot applications. In 2017 IEEE International Conference on Edge Computing (EDGE) , pages 32--39, June 2017

    2017

  2. [10]

    Chan, and Kin K

    Shiqiang Wang, Rahul Urgaonkar, Murtaza Zafer, Ting He, Kevin S. Chan, and Kin K. Leung. Dynamic service migration in mobile edge-clouds. CoRR , abs/1506.05261, 2015

    2015 arXiv

  3. [11]

    Cankaya, Qiong Zhang, Weisheng Xie, and Jason P

    Ashkan Yousefpour, Ashish Patil, Genya Ishigaki, Inwoong Kim, Xi Wang, Hakki C. Cankaya, Qiong Zhang, Weisheng Xie, and Jason P. Jue. Qos-aware dynamic fog service provisioning. CoRR , abs/1802.00800, 2018

    2018 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.