A Caltech Library Service

Scheduling in Distributed Stream Processing Systems


Khorlin, Andrey (2006) Scheduling in Distributed Stream Processing Systems. Master's thesis, California Institute of Technology. doi:10.7907/4MH9-9104.


Stream processing systems receive continuous streams of messages with relatively raw information and produce streams of messages with processed information. The utility of a stream-processing system depends, in part, on the accuracy and timeliness of the output. Streams in complex event processing systems are processed on distributed systems; several steps are taken on different processors to process each incoming message, and messages may be enqueued between steps. This work explores the problem of distributed dynamic control of streams to optimize the total utility provided by the system. A system can be controlled using central control or distributed control. In the former case a single central controller maintains the state of the entire system and controls the operation of all processors. In distributed control systems, each processor controls itself based on its state and information from other processors. A challenge of distributed control is that timeliness of output depends only on the total end-to-end time and is otherwise independent of the delays at each separate processor whereas the controller for each processor takes action to control only the steps on that processor and cannot directly control the entire network. In this work, we discuss a framework for design and analysis of the control-based scheduling algorithms for a distributed stream processing system and illustrate our framework with two concrete scheduling algorithms.

Item Type:Thesis (Master's thesis)
Subject Keywords:control theory; data streams; markov chains; process sharing; QoS function; queuing theory; scheduling; stream; stream processing system
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Chandy, K. Mani
Thesis Committee:
  • Unknown, Unknown
Defense Date:26 May 2006
Non-Caltech Author Email:akhorlin (AT)
Record Number:CaltechETD:etd-05242006-175006
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2012
Deposited By: Imported from ETD-db
Deposited On:05 Jun 2006
Last Modified:27 Mar 2020 00:07

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page