Scalable planning for distributed stream processing systems

Recently the problem of automatic composition of workflows has been receiving increasing interest. Initial investigation has shown that designing a practical and scalable composition algorithm for this problem is hard. A very general computational model of a workflow (e.g., BPEL) can be Turing-complete, which precludes fully automatic analysis of compositions. 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 notion of concurrency by timeless functional computation. In addition, SPPL defines workflow metrics of resource consumption and quality of service. Experiments have shown earlier that even a naïve SPPL planning algorithm significantly 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 problems. We also give an example of SPPL model for practical problems. Copyright © 2006, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.