Resource Allocation in Streaming Environments

This paper considers resource allocation algorithms for processing streams of events on computational grids. For example, financial trading applications are executed on large computational grids that receive streams of data such as stock ticker prices, commodity prices, foreign-exchange rates and total risk exposure. The economic value of a computation depends on the time taken to execute it; an arbitrage opportunity can disappear in seconds. Given limited resources, it is not possible to process all streams without delay. The more resource available to a computation, the less time it takes to process the input, and thus the more value it generates. Therefore, the scheduling policy should be designed to optimize the net economic value of computations executed on the grid. In this paper, we propose two scheduling/resource allocation algorithms for processing streams on computational grids to optimize economic value. Both algorithms are based on market mechanisms; one uses a centralized market and the other decentralized markets. We prove bounds on performance and present measurements to show that the performances of the resource allocation systems are near-optimal and outperform load-balancing heuristics