Scalable planning for distributed stream processing systems

Anton Riabov, Zhen Liu

2006 · 39 citations · 10 references

Concepts

Abstract

Recently the problem of automatic composition of workflows has been receiving increasing interest. Initial investigation has shown that designing a practical and scalable composi-tion algorithm for this problem is hard. A very general com-putational model of a workflow (e.g., BPEL) can be Turing-complete, which precludes fully automatic analysis of com-positions. However, in many applications, workflow model can be simplified. We consider a model known as the Stream Processing Planning Language (SPPL), applicable in stream processing and other related domains. SPPL replaces the no-tion of concurrency by timeless functional computation. In addition, SPPL defines workflow metrics of resource con-sumption and quality of service. Experiments have shown earlier that even a naı̈ve SPPL planning algorithm signifi-cantly outperforms existing metric PDDL planners on stream processing workflow composition problems. In this paper we describe an efficient and scalable algorithm for finding high-quality approximate solutions for large instances of SPPL problems. We demonstrate the scalability of the algorithm on synthetic benchmarks that are derived from practical prob-lems. We also give an example of SPPL model for practical problems.

References

10