---
res:
  bibo_abstract:
  - 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.@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
    orcid: 0000-0003-3650-940X
  - foaf_Person:
      foaf_givenName: Giorgi
      foaf_name: Nadiradze, Giorgi
      foaf_surname: Nadiradze
      foaf_workInfoHomepage: http://www.librecat.org/personId=3279A00C-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0001-5634-0731
  - foaf_Person:
      foaf_givenName: Nikita
      foaf_name: Koval, Nikita
      foaf_surname: Koval
      foaf_workInfoHomepage: http://www.librecat.org/personId=2F4DB10C-F248-11E8-B48F-1D18A9856A87
  bibo_doi: 10.1145/3323165.3323201
  dct_date: 2019^xs_gYear
  dct_identifier:
  - UT:000507618500018
  dct_isPartOf:
  - http://id.crossref.org/issn/9781450361842
  dct_language: eng
  dct_publisher: ACM@
  dct_title: Efficiency guarantees for parallel incremental algorithms under relaxed
    schedulers@
...