conference paper published yes Dan-Adrian Alistarh author 4A899BFC-F248-11E8-B48F-1D18A9856A870000-0003-3650-940X Giorgi Nadiradze author 3279A00C-F248-11E8-B48F-1D18A9856A870000-0001-5634-0731 Nikita Koval author 2F4DB10C-F248-11E8-B48F-1D18A9856A87 DaAl department SPAA: Symposium on Parallelism in Algorithms and Architectures Elastic Coordination for Scalable Machine Learning project Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(łog n poly(k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O(poly(k), dmax / wmin), where dmax is the maximum distance between two nodes, and wmin is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers. ACM2019Phoenix, AZ, United States eng 9781450361842 2003.09363 00050761850001810.1145/3323165.3323201 145-154 https://research-explorer.ista.ac.at/record/10429 Alistarh, Dan-Adrian, Giorgi Nadiradze, and Nikita Koval. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” In <i>31st ACM Symposium on Parallelism in Algorithms and Architectures</i>, 145–54. ACM, 2019. <a href="https://doi.org/10.1145/3323165.3323201">https://doi.org/10.1145/3323165.3323201</a>. D.-A. Alistarh, G. Nadiradze, and N. Koval, “Efficiency guarantees for parallel incremental algorithms under relaxed schedulers,” in <i>31st ACM Symposium on Parallelism in Algorithms and Architectures</i>, Phoenix, AZ, United States, 2019, pp. 145–154. Alistarh D-A, Nadiradze G, Koval N. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In: <i>31st ACM Symposium on Parallelism in Algorithms and Architectures</i>. ACM; 2019:145-154. doi:<a href="https://doi.org/10.1145/3323165.3323201">10.1145/3323165.3323201</a> Alistarh, D.-A., Nadiradze, G., &#38; Koval, N. (2019). Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In <i>31st ACM Symposium on Parallelism in Algorithms and Architectures</i> (pp. 145–154). Phoenix, AZ, United States: ACM. <a href="https://doi.org/10.1145/3323165.3323201">https://doi.org/10.1145/3323165.3323201</a> Alistarh D-A, Nadiradze G, Koval N. 2019. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. 31st ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 145–154. D.-A. Alistarh, G. Nadiradze, N. Koval, in:, 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2019, pp. 145–154. Alistarh, Dan-Adrian, et al. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” <i>31st ACM Symposium on Parallelism in Algorithms and Architectures</i>, ACM, 2019, pp. 145–54, doi:<a href="https://doi.org/10.1145/3323165.3323201">10.1145/3323165.3323201</a>. 66732019-07-24T08:59:36Z2026-04-08T07:00:45Z