Technical Report Number
In this report, we show that deadlock avoidance for streaming computations with filtering can be performed efficiently for a large class of DAG topologies. We first give efficient algorithms for dummy interval computation in series-parallel DAGs, then generalize our results to a larger graph family, the CS4DAGs, in which every undirected cycle has exactly one source and one sink. Our results show that, for a large set of application topologies that are both intuitively useful and formalizable, the streaming model with filtering can be implemented safely with reasonable compilation overhead.
Buhler, Jeremy; Agrawal, Kunal; Li, Peng; and Chamberlain, Roger D., "Efficient Deadlock Avoidance for Streaming Computation with Filtering" Report Number: WUCSE-2011-59 (2011). All Computer Science and Engineering Research.