Name
Abstract | ||
|---|---|---|
The paradigm of computation on streaming data has received considerable recent attention. Streaming computations can be efficiently parallelized using systems of computing nodes organized in dataflow-like architectures. However, when these nodes have the ability to filter, or discard, 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 describe 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 resizing of buffers. This approach is particularly well-suited to preventing deadlock in distributed systems of diverse computing architectures, where global coordination or modification of buffer sizes may be difficult or impossible in practice. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1810479.1810526 | SPAA |
Keywords | Field | DocType |
finite buffering,considerable recent attention,diverse computing architecture,dataflow-like architecture,global coordination,deadlock avoidance,dynamic resizing,buffer size,global run-time coordination,computation system,data stream,dataflow,distributed system,computer architecture | Edge chasing,Data stream mining,Computer science,Parallel computing,Deadlock,Filter (signal processing),Dataflow,Streaming data,Deadlock prevention algorithms,Distributed computing,Computation | Conference |
Citations | PageRank | References |
20 | 0.93 | 19 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peng Li | 1 | 81 | 11.75 |
| Kunal Agrawal | 2 | 687 | 50.08 |
| Jeremy Buhler | 3 | 821 | 93.45 |
| Roger D. Chamberlain | 4 | 616 | 65.36 |