conference paper
The power of choice in priority scheduling
published
yes
Dan-Adrian
Alistarh
author 4A899BFC-F248-11E8-B48F-1D18A9856A87
Justin
Kopinsky
author
Jerry
Li
author
Giorgi
Nadiradze
author 3279A00C-F248-11E8-B48F-1D18A9856A87
DaAl
department
PODC: Principles of Distributed Computing
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.
ACM2017Washington, WA, USA
eng
Proceedings of the ACM Symposium on Principles of Distributed Computing
978-145034992-510.1145/3087801.3087810
Part F129314283 - 292
Alistarh, D.-A., Kopinsky, J., Li, J., & 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>
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.
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>.
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.
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>
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>.
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.
7912018-12-11T11:48:31Z2021-01-12T08:15:59Z