This paper investigates algorithms for deadlock avoidance in parallel streaming computations. The basic paradigm, used in such diverse fields as signal processing, multimedia applications, and computational biology, is a directed acyclic graph of nodes and edges, where each node receives data from one or more input edges, processes the data, and then may emit data on one or more output edges. For the sake of theoretical analysis, the data stream is abstractly modeled with indexed tokens and the nodes may filter--pass on--a token. Furthermore, the channels are assumed to be buffered. In this setup, deadlock can happen, for example, when one node needs a token to progress on one channel, but the token cannot be sent because the sending node is (transitively) blocked on another channel--a channel that would be freed in case the first node made progress.

The paper establishes a few abstract results that give sufficient and necessary conditions for deadlock to occur (essentially, there must be some kind of transitively blocking circle in the topology of the nodes). The basic idea for the deadlock avoidance algorithm is to emit dummy tokens. This is underpinned by a theorem that states: in the absence of filtering, deadlock cannot occur. The remainder of the paper is concerned with an algorithmic design that keeps the number of dummy tokens emitted to a minimum (there is a straightforward solution that emits a dummy token for each filtered token, but this is, of course, impractical).

This well-written paper includes relevant examples from a computational biology system developed by the authors. The algorithms are explained in detail, so they could be implemented for similar streaming applications.