  Task-parallel programs often enjoy deadlock freedom under certain
restrictions, such as the use of structured join operations, as in Cilk and
X10, or the use of asynchronous task futures together with deadlock-avoiding
policies such as Known Joins or Transitive Joins. However, the promise, a
popular synchronization primitive for parallel tasks, does not enjoy
deadlock-freedom guarantees. Promises can exhibit deadlock-like bugs; however,
the concept of a deadlock is not currently well-defined for promises.
  To address these challenges, we propose an ownership semantics in which each
promise is associated to the task which currently intends to fulfill it.
Ownership immediately enables the identification of bugs in which a task fails
to fulfill a promise for which it is responsible. Ownership further enables the
discussion of deadlock cycles among tasks and promises and allows us to
introduce a robust definition of deadlock-like bugs for promises.
  Cycle detection in this context is non-trivial because it is concurrent with
changes in promise ownership. We provide a lock-free algorithm for precise
runtime deadlock detection. We show how to obtain the memory consistency
criteria required for the correctness of our algorithm under TSO and the Java
and C++ memory models. An evaluation compares the execution time and memory
usage overheads of our detection algorithm on benchmark programs relative to an
unverified baseline. Our detector exhibits a 12% (1.12$\times$) geometric mean
time overhead and a 6% (1.06$\times$) geometric mean memory overhead, which are
smaller overheads than in past approaches to deadlock cycle detection.
