Power-of-two sampling in redundancy systems: The impact of assignment constraints

Research output: Contribution to journalArticleAcademicpeer-review

34 Downloads (Pure)

Abstract

A classical sampling strategy for load balancing policies is power-of-two, where any server pair is sampled with equal probability. This does not cover practical settings with assignment constraints which force non-uniform sampling. While intuition suggests that non-uniform sampling adversely impacts performance, this was only supported through simulations, and rigorous statements have remained elusive. Building on product-form distributions for redundancy systems, we prove the stochastic dominance of uniform sampling for a four-server system as well as arbitrary-size systems in light traffic.

Original languageEnglish
Pages (from-to)699-706
Number of pages8
JournalOperations Research Letters
Volume50
Issue number6
DOIs
Publication statusPublished - Nov 2022

Keywords

  • Light traffic
  • Load balancing
  • Parallel-server systems
  • Power-of-two
  • Redundancy scheduling
  • Stochastic comparison

Fingerprint

Dive into the research topics of 'Power-of-two sampling in redundancy systems: The impact of assignment constraints'. Together they form a unique fingerprint.

Cite this