Efficient Deadlock Avoidance for Streaming Computation With Filtering
Parallel streaming computation has been studied extensively, and many languages, libraries, and systems have been designed to support this model of computation. While some streaming computations send data at a priori predictable rates on every channel between compute nodes, many natural applications lack this property. In particular, the authors consider acyclic streaming computations in which individual nodes can choose to filter, or discard, some of their inputs. While streaming computation with filtering is an attractive model for many applications, if the channels between nodes have finite buffers, the computation can deadlock.