---
res:
bibo_abstract:
- '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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Dan-Adrian
foaf_name: Alistarh, Dan-Adrian
foaf_surname: Alistarh
foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Justin
foaf_name: Kopinsky, Justin
foaf_surname: Kopinsky
- foaf_Person:
foaf_givenName: Jerry
foaf_name: Li, Jerry
foaf_surname: Li
- foaf_Person:
foaf_givenName: Giorgi
foaf_name: Nadiradze, Giorgi
foaf_surname: Nadiradze
foaf_workInfoHomepage: http://www.librecat.org/personId=3279A00C-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1145/3087801.3087810
bibo_volume: Part F129314
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-145034992-5
dct_language: eng
dct_publisher: ACM@
dct_title: The power of choice in priority scheduling@
...