  There is a growing demand for live, on-the-fly processing of increasingly
large amounts of data. In order to ensure the timely and reliable processing of
streaming data, a variety of distributed stream processing architectures and
platforms have been developed, which handle the fundamental tasks of
(dynamically) assigning processing tasks to the currently available physical
resources and routing streaming data between these resources. However, while
there are plenty of platforms offering such functionality, the theory behind it
is not well understood. In particular, it is unclear how to best allocate the
processing tasks to the given resources. In this paper, we establish a
theoretical foundation by formally defining a task allocation problem for
distributed stream processing, which we prove to be NP-hard. Furthermore, we
propose an approximation algorithm for the class of series-parallel
decomposable graphs, which captures a broad range of common stream processing
applications. The algorithm achieves a constant-factor approximation under the
assumptions that the number of resources scales at least logarithmically with
the number of computational tasks and the computational cost of the tasks
dominates the cost of communication.

Distributed, Parallel, and Cluster Computing