Graph Algorithms in a Guaranteed-Deterministic Language
P. J. Narayanan, Ryan Newton · 2014
Deterministic implementations of graph algorithms have recently been shown to be reasonably performant. In this paper we explore a follow-on question: can deterministic graph algorithms be ex-pressed in guaranteed-deterministic parallel languages, which are necessarily restrictive in what concurrency idioms they employ? To find out, we implement several graph algorithms using the LVish library for Haskell (a deterministic language), which reveals its strengths as well as limitations. We surmount these limitations by (1) implementing a functional version of the deterministic reserva-tions mechanism, and (2) adding a new mechanism to LVish called BulkRetry. We present results from an early-stage prototype. 1.