Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Randomized load balancing in finite regimes

Tools
- Tools
+ Tools

Godtschalk , A. S. and Ciucu, Florin (2016) Randomized load balancing in finite regimes. In: ICDCS 2016 : IEEE International Conference on Distributed Computing Systems , Nara, Japan, 27-30 Jun 2016. Published in: 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS) ISSN 1063-6927. doi:10.1109/ICDCS.2016.97

[img]
Preview
PDF
WRAP_pid4225803.pdf - Accepted Version - Requires a PDF viewer.

Download (1703Kb) | Preview
Official URL: https://doi.org/10.1109/ICDCS.2016.97

Request Changes to record.

Abstract

Randomized load balancing is a cost efficient policy for job scheduling in parallel server queueing systems whereby, with every incoming job, a central dispatcher randomly polls some servers and selects the one with the smallest queue. By exactly deriving the jobs' delay distribution in such systems, in explicit and closed form, Mitzenmacher~\cite{Mi03} proved the so-called `power-of-two' result, which states that by randomly polling only two servers yields an exponential improvement in delay over randomly selecting a single server. Such a fundamental result, however, was obtained in an asymptotic regime in the total number of servers, and does do not necessarily provide accurate estimates for practical finite regimes with small or moderate number of servers. In this paper we obtain stochastic lower and upper bounds on the jobs' average delay in non-asymptotic/finite regimes, by borrowing ideas for analyzing the particular case of Join-the-Shortest-Queue (JSQ) policy. Numerical illustrations indicate not only that the obtained (lower) bounds are remarkably accurate, but also that the existing exact but asymptotic results can be largely misleading in finite regimes (e.g., by more than $100\%$ in the case of $12$ servers).

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Client/server computing -- Mathematical models , Queuing networks (Data transmission), Queuing theory, Computer networks
Journal or Publication Title: 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS)
Publisher: IEEE
ISSN: 1063-6927
Official Date: 11 August 2016
Dates:
DateEvent
11 August 2016Published
DOI: 10.1109/ICDCS.2016.97
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Funder: Deutsche Forschungsgemeinschaft (DFG), Deutsche Telekom. Telekom Innovation Laboratories (T-Labs)
Grant number: Ci 195/1-1 (DFG)
Conference Paper Type: Paper
Title of Event: ICDCS 2016 : IEEE International Conference on Distributed Computing Systems
Type of Event: Conference
Location of Event: Nara, Japan
Date(s) of Event: 27-30 Jun 2016
Related URLs:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us