Cycle stealing under immediate dispatch task assignment

Mor Harchol‐Balter · Takayuki Osogami · Alan Andrew Scheller-Wolf · Mark S. Squillante

29 citations0/0 files storedACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Advanced Queuing Theory Analysis Cloud Computing and Resource Management Distributed and Parallel Computing Systems

Abstract

We consider the practical problem of task assignment in a server farm, where each arriving job is immediately dispatched to a server in the farm. We look at the benefit of cycle stealing at the point of the dispatcher, where jobs normally destined for one machine may be routed to a different machine if it is idle. The analysis uses a technique which we refer to as dimensionality reduction via busy period transitions. Our analysis is approximate, but can be made as close to exact as desired, and is validated via simulation. Results show that the beneficiaries of the idle cycles can benefit unboundedly, due to an increase in their stability region, while the donors are only slightly penalized. These results still hold even when there is only one donor server and 20 beneficiary servers stealing its idle cycles.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 29 citations exist upstream.

References

1961A Proof for the Queuing Formula: L = λ W 1999Introduction to Matrix Analytic Methods in Stochastic Modeling 1984Matrix-Geometric Solutions to Stochastic Models 1989Stochastic Modeling and the Theory of Queues 1991Structured Stochastic Matrices of M/G/1 Type and Their Applications.1977Optimality of the shortest line discipline 2000A Practical Guide to Heavy Tails 1980A simple dynamic routing problem

Cited by

2015The Benefit of Introducing Variability in Single-Server Queues with Application to Quality-Based Service Domains 2003Analysis of cycle stealing with switching cost 2013Lookahead actions in dispatching to parallel queues 2011Stability analysis of a two-station cascade queueing network 2010Stochastic Analysis and Optimization of Multiserver Systems

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.