---
_id: '791'
abstract:
- lang: eng
  text: 'Consider the following random process: we are given n queues, into which
    elements of increasing labels are inserted uniformly at random. To remove an element,
    we pick two queues at random, and remove the element of lower label (higher priority)
    among the two. The cost of a removal is the rank of the label removed, among labels
    still present in any of the queues, that is, the distance from the optimal choice
    at each step. Variants of this strategy are prevalent in state-of-the-art concurrent
    priority queue implementations. Nonetheless, it is not known whether such implementations
    provide any rank guarantees, even in a sequential model. We answer this question,
    showing that this strategy provides surprisingly strong guarantees: Although the
    single-choice process, where we always insert and remove from a single randomly
    chosen queue, has degrading cost, going to infinity as we increase the number
    of steps, in the two choice process, the expected rank of a removed element is
    O(n) while the expected worst-case cost is O(n log n). These bounds are tight,
    and hold irrespective of the number of steps for which we run the process. The
    argument is based on a new technical connection between "heavily loaded"
    balls-into-bins processes and priority scheduling. Our analytic results inspire
    a new concurrent priority queue implementation, which improves upon the state
    of the art in terms of practical performance.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Justin
  full_name: Kopinsky, Justin
  last_name: Kopinsky
- first_name: Jerry
  full_name: Li, Jerry
  last_name: Li
- first_name: Giorgi
  full_name: Nadiradze, Giorgi
  id: 3279A00C-F248-11E8-B48F-1D18A9856A87
  last_name: Nadiradze
  orcid: 0000-0001-5634-0731
citation:
  ama: 'Alistarh D-A, Kopinsky J, Li J, Nadiradze G. The power of choice in priority
    scheduling. In: <i>Proceedings of the ACM Symposium on Principles of Distributed
    Computing</i>. Vol Part F129314. ACM; 2017:283-292. doi:<a href="https://doi.org/10.1145/3087801.3087810">10.1145/3087801.3087810</a>'
  apa: 'Alistarh, D.-A., Kopinsky, J., Li, J., &#38; Nadiradze, G. (2017). The power
    of choice in priority scheduling. In <i>Proceedings of the ACM Symposium on Principles
    of Distributed Computing</i> (Vol. Part F129314, pp. 283–292). Washington, WA,
    USA: ACM. <a href="https://doi.org/10.1145/3087801.3087810">https://doi.org/10.1145/3087801.3087810</a>'
  chicago: Alistarh, Dan-Adrian, Justin Kopinsky, Jerry Li, and Giorgi Nadiradze.
    “The Power of Choice in Priority Scheduling.” In <i>Proceedings of the ACM Symposium
    on Principles of Distributed Computing</i>, Part F129314:283–92. ACM, 2017. <a
    href="https://doi.org/10.1145/3087801.3087810">https://doi.org/10.1145/3087801.3087810</a>.
  ieee: D.-A. Alistarh, J. Kopinsky, J. Li, and G. Nadiradze, “The power of choice
    in priority scheduling,” in <i>Proceedings of the ACM Symposium on Principles
    of Distributed Computing</i>, Washington, WA, USA, 2017, vol. Part F129314, pp.
    283–292.
  ista: 'Alistarh D-A, Kopinsky J, Li J, Nadiradze G. 2017. The power of choice in
    priority scheduling. Proceedings of the ACM Symposium on Principles of Distributed
    Computing. PODC: Principles of Distributed Computing vol. Part F129314, 283–292.'
  mla: Alistarh, Dan-Adrian, et al. “The Power of Choice in Priority Scheduling.”
    <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>,
    vol. Part F129314, ACM, 2017, pp. 283–92, doi:<a href="https://doi.org/10.1145/3087801.3087810">10.1145/3087801.3087810</a>.
  short: D.-A. Alistarh, J. Kopinsky, J. Li, G. Nadiradze, in:, Proceedings of the
    ACM Symposium on Principles of Distributed Computing, ACM, 2017, pp. 283–292.
conference:
  end_date: 2017-07-27
  location: Washington, WA, USA
  name: 'PODC: Principles of Distributed Computing'
  start_date: 2017-07-25
date_created: 2018-12-11T11:48:31Z
date_published: 2017-07-26T00:00:00Z
date_updated: 2025-06-04T09:44:47Z
day: '26'
department:
- _id: DaAl
doi: 10.1145/3087801.3087810
external_id:
  arxiv:
  - '1706.04178'
  isi:
  - '000462995000035'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1706.04178
month: '07'
oa: 1
oa_version: Submitted Version
page: 283 - 292
publication: Proceedings of the ACM Symposium on Principles of Distributed Computing
publication_identifier:
  isbn:
  - 978-145034992-5
publication_status: published
publisher: ACM
publist_id: '6864'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The power of choice in priority scheduling
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: Part F129314
year: '2017'
...