1 . Introduction2 . Stream Applications2.1 . Graph Representation2.2 . Incremental Computation with Asynchronous Noisy Data2.3 . On-Arrival vs. Snapshot Processing2.4 . Snapshot Processing Algorithms3 . Resource Allocation for Stream Processing3.1 . Problem Formulation3.2 . Mapping Tasks to Machines3.3 . Single Market Resource Reservation System3.4 . Multiple Market Distributed Resource Reservation System3.5 . Simulation Results4 . Related Work5 . ConclusionEnterprise Computing Systems as Information FactoriesK. Mani Chandy, Lu Tian and Daniel M. ZimmermanComputer Science 256-80California Institute of TechnologyPasadena, California 91125 USA{mani, lutian, dmz}@cs.caltech.eduAbstractThe availability of streaming event data, from sourcesranging from sensors and RFID tags to commodity ex-changes and wire services, is growing rapidly. It is be-coming increasingly important for enterprises to build ap-plications that use this data to detect and react to poten-tial threats and opportunities (“critical states”). These“stream applications” analyze events from many differentsources and of many different forms—numerical, textual,and visual—to determine when a critical state exists andwhat the appropriate response should be. Stream appli-cations allow the enterprise computing system to act asan “information factory”; just as industrial factories cre-ate value by transforming raw materials into finished prod-ucts, information factories create value by transformingraw events into structured data. This transformation cantake considerable computational resources, so it is impor-tant both to design efficient and reliable algorithms and tomake the best possible use of the available computing in-frastructure when executing these algorithms. This paperexplores design considerations for stream applications andmethods for deploying stream applications on enterprisecomputing systems to maximize economic efficiency. Boththeoretical and quantitative results are presented.1. IntroductionAs sensors and RFID tags become more widely de-ployed, and streams of data from commodity exchanges,wire services, and other sources become more widely andfreely available, new application areas for enterprise com-puting systems are emerging. Like an automobile factory,which takes raw materials such as steel and glass as “in-puts” and creates value by transforming them into cars, anenterprise computing system can take raw events generatedby myriad sources as inputs and create value by transform-ing them into more structured information that allows theenterprise to react more quickly and more appropriately tothreats and opportunities in its extended environment thanit previously could.A stream application that transforms raw events fromdata streams in this way enables the enterprise computingsystem to serve as an information factory, capable not onlyof detecting threats and opportunities but also—at least insome cases—of reacting to them autonomously. The eco-nomic value added to an enterprise by a industrial factory,measured in dollars per unit time, can be estimated from therates of its economic input (the raw materials) and output(the finished products); industrial engineering and job-shopdesigns have focused on optimizing this means of addingeconomic value. An information factory takes streams ofraw information—stock and commodity prices, foreign ex-change rates, interest rates, information about events rel-evant to the enterprise (such as hurricanes), and informa-tion about events within the enterprise—as economic inputand generates streams of processed information as output.The nature of these output streams varies widely across in-dustries: a financial services company’s system may outputmessages that cause stocks and commodities to be boughtand sold, an airline’s system may output messages thatcause ticket prices for specific fare classes on various flightsto be changed, and a power company’s system may outputmessages that switch particular generators on or off. Likethe value added by an industrial factory, the value addedby an information factory can be measured, in part, by thedifference in values of the input and output streams.There are three critical differences between the industrialfactory of the past and the information factory of the presentthat influence the design of the information factory.Response Time The value added by the information fac-tory depends critically on response time (also called la-tency), the time delay between the arrival of raw informa-tion and the production of actionable output. For example,an arbitrage opportunity may disappear in seconds, so theeconomic value (or utility) of identifying arbitrage opportu-1nities is directly related to how quickly they are identified.The difference in utility between a response in one millisec-ond and a response in one hour depends critically on the ap-plication. In a Customer Relationship Management (CRM)application, a response need only occur in time to deal witha customer’s problem while they are on the phone; a re-sponse in one second provides as much utility as a responsein one millisecond. In a supply chain application dealingwith trucking logistics, a response in one minute may pro-vide as much utilty as a response within milliseconds. Thus,a careful analysis of the utility of responses as a function ofthe quality of the response and the response time is critical.Accuracy The decisions taken by an enterprise based onthe output of an information factory may be incorrect. Theappropriateness or accuracy of the response has a dramaticeffect on the value added by the response. One way of par-titioning some of the incorrect decisions is in terms of falsepositives and false negatives: a false positive arises whenthe system detects and responds to a threat or opportunitythat does not exist; a false negative arises when the systemeither detects a threat or opportunity too late for a usefulresponse, or does not detect it at all. Accuracy plays a rolein industrial factories too; some automobile factories pro-duce more reliable cars than others. The critical economicdifferences in outputs with varying accuracy is, however, acharacteristic of the information factory.Adaptability The information factory adapts continu-ously: new users and new computers are added almost daily,new network capabilites are added very frequently, and newapplications are added as needs arise. Industrial factoriesadapt too, but an automobile