TITLE: Assignment-Based Partitioning in a Condition Monitoring System

AUTHORS:
Yongqiang Huang and Hector Garcia-Molina
Department of Computer Science
Stanford University
Stanford, CA 94305
{yhuang, hector}@cs.stanford.edu

ABSTRACT:
A condition monitoring system tracks real-world variables and alerts
users when a predefined condition becomes true, e.g., when enemy
planes take off, or when suspicious terrorist activities and
communication are detected.  However, a monitoring server can easily
get overwhelmed by rapid incoming data.  To prevent this, we partition
the condition being monitored and distribute the workload onto several
independent servers.  In this paper, we study the problem of how to
make a partitioned system behave "equivalently" to a one-server
system.  We identify and formally define three desirable properties of
a partitioned system, namely, orderedness, consistency, and
completeness.  We propose assignment-based partitioning as a solution
that can handle opaque conditions and simplifies load balancing.  We
also look at a few typical partitioned systems, and discuss their
merits using several metrics that we define.  Finally, an algorithm is
presented to reduce complex system configurations to simpler ones.