Deadlock avoidance for streaming computations with filtering

The paradigm of computation on streaming data has re-ceived considerable recent attention. Streaming computa-tions can be efficiently parallelized using systems of com-puting nodes organized in dataflow-like architectures. How-ever, when these nodes have the ability to filter, or dis-card, some of their inputs, a system with finite buffering is vulnerable to deadlock. In this paper, we formalize a model of streaming computation systems with filtering, de-scribe precisely the conditions under which such systems may deadlock, and propose provably correct mechanisms to avoid deadlock. Our approach relies on adding extra “dummy ” tokens to the data streams and does not require global run-time coordination among nodes or dynamic resiz-ing of buffers. This approach is particularly well-suited to preventing deadlock in distributed systems of diverse com-puting architectures, where global coordination or modifica-tion of buffer sizes may be difficult or impossible in practice