Wireless Sensors and Controls for ... - EECS at UC …
Proposal Outline and approximate page budget (total = 15 pages)
Introduction (1 page)
Applications
Energy (2 pages)
Disaster (2 pages)
SIS design
Sensor-net level design (1 page)
Service level design (1 page)
Data Handling (1 page)
Human-Centered-Computing (UCB) (.5 page)
Visualization (UCD) (.5 page)
Foundations:
Reliability (2-3 pages)
Availability (2-3 pages)
Security and Policy (1 page)
Outreach (.25 pages)
1. Introduction (Target: 1 page)
Information technology (IT) is transforming society at an accelerating pace, from business systems and social and political infrastructure to our personal lives. But the current path for developing IT will, at best, severely underutilize its potential and, at worst, yield a fragile IT infrastructure which is not of high enough confidence to meet many of society’s most vital needs, such as emergency preparedness and response and energy usage monitoring and control. We propose to establish the Center for Information Technology Research in the Interest of Society (CITRIS) to sponsor collaborative, IT-focused research to find solutions to grand-challenge social and commercial problems affecting the quality of life of individuals and organizations. CITRIS will be a multicampus center, including UC Berkeley (UCB), UC Davis (UCD) and UC Merced (UCM). This proposal is to support the key underpinning long term, high risk scientific and technological research endeavors within CITRIS. The NSF-ITR award will have the potential of high leverage from other CITRIS activities paid for by private and industrial donations (See Appendix A.)
CITRIS’s driving applications include (1) boosting efficiency of energy production and consumption, and (2) saving lives and property and establishing emergency response IT infrastructure in the wake of disasters, among others [CITRIS]. The solutions to these applications have the common feature that they depend on highly-distributed, reliable, and secure (briefly: high-confidence) information systems that can evolve and adapt to radical changes in their environment, delivering networked information services and up-to-date sensor network data stores over ad-hoc, flexible and fault tolerant networks that adapt to the people and organizations that need them. We call such systems Societial-Scale Information Systems (SISs). An SIS must easily integrate devices, ranging from distributed ad-hoc sensors and actuators, to hand-held information appliances (such as PDAs), workstations, and room-sized cluster supercomputers at Network Operation Centers. Such devices must be connected by ad-hoc sensor nets, extranets, short-range wireless networks as well as by very high-bandwidth, long-haul optical backbones. Distributed data and services must be secure, reliable, and high-performance, even if part of the system is down, disconnected, under repair, or under (information) attack. The SIS must configure, install, diagnose, maintain, and improve its quality of service features — this applies especially to the vast numbers of sensors that will be cheap, widely dispersed, and even disposable. Finally, the SIS must allow vast quantities of data to be easily and reliably accessed, manipulated, interactively explored, disseminated, and used in a customized fashion by users, from expert to novice.
The web, telephone network, and some military and intelligence systems are limited, albeit highly successful, SISs. Yet none satisfies the needs of the societal problems. Only by attacking more than one driving application will we learn to design a system that will meet the needs of other applications that we can only now imagine. Open problems we will address are lack of dense instrumentation (§3.1), lack of dynamic peering (§3.2), inexpressive and incomposable interfaces (§3.2), lack of information access and integration (§3.3), processing interactive faulty data (§2.2, 3.3), visualizing vast data (§3.4), complexity of systems (§4.1), software quality (§4.1), need for repair centric design (§4.2), denial of service (§4.3), and authentication (§4.3).
CITRIS will have 3 tiers of activity: Driving Applications (for which we deliver an Energy Management SIS (§2.1) and a Disaster Response SIS (§2.2)), SIS Design (Sensor level (§3.1), Service level (§3.2), Data Handling (§3.3), Human-Centered Computing (§3.4)), and Foundations (Reliability (§4.1), Availability (§4.2), and Security (§4.3)). Each activity has a leader and affiliates shown below.
For the two driving applications, we will use and leverage ubiquitous wireless sensor devices, called SmartMotes which are about one inch cube in size and include an embedded (StrongArm) processor, a radio, a sensor board with microsensors for measuring acceleration, strain, temperature, light, relative humidity and a battery. We have had around 500 (and expect to have at least 1000 more) of these made for us by Crossbow, Inc.(not priced on this grant). Each of these with a 1% duty cycle and 2 AA batteries will last about a year. The next generation of these MEMS devices called SmartDust will have this functionality integrated into a single chip with on board solar power, (2mm cube) with ultra-high–bandwidth radio (the size of the sensor will be dominated by the antenna size), and will provide the distributed, adaptive self-organizing ubiquitous sensing and computational fabric. All are our design.
2. Driving Applications
2.1 Energy Management (Target: 2 pages) (Faculty: Rabaey;Pister, Arens, Sastry)
The deregulation of electricity and the increasing cost of natural gas have made energy front page news. A recent CITRIS working group of the above faculty plus key researchers in energy and resources groups at Lawrence Berkeley Laboratories have established that that SISs can address and resolve major issues hampering the effective generation, distribution and utilization of energy, potentially saving $55B/year and 35M metric tons/year of carbon emissions nationwide [Rabaey01] just from better control of HVAC in large buildings. We will demonstrate such an SIS on the Berkeley campus.
It is possible to save energy on the demand side and the supply side; we first consider demand.
Demand Side. Two-thirds of primary energy use is in the form of electricity and about two-thirds of all electricity generated nationally is used in buildings [Interlaboratory Working Group, 2000]. We will use SISs consisting of high density wireless sensor/actuator networks to enable energy conscious control of buildings (including reducing both total energy as well as peak power demanded. (Wires can be up to 90% of the total cost of such a system, so they must be wireless.)
• High-density sensor networks will allow existing environmental control technologies to operate in more sophisticated and energy-efficient ways, and the redundancy of sensors will improve the reliability of control by detecting faulty signals.
• High-density sensor networks will also allow new energy-efficient environmental control technologies to become feasible for the first time.
Imagine, for example, the following scenario. All significant energy-consuming devices in buildings are equipped with a multifunctional metering, communications, and control devices. These devices provide real-time information to building owners and occupants on rate of energy use (e.g., kW), cost associated with energy use rate ($ per hour), cumulative energy usage and associated costs for past 24 h, month, and year. By itself, this information would help energy users to make rational decisions such as how much and when to use certain devices, and when to take inefficient ones out of service.
In addition to reducing total energy use, it is important to limit peak demand through mechanisms like real-time pricing. Real-time pricing will require more sophisticated electricity meters than are currently in common use. However, for optimal performance, devices that are moderate to heavy electricity users should also be equipped with controls that would permit rational response to real-time price signals. With the right combination of distributed ubiquitous sensing and processing smart appliances could use electricity mostly at off-peak periods.
Thus, by making end-users of the energy-supply chain part of an integrated network of monitoring, information processing, controlling, and actuating devices, we enable a wide range of techniques that will both help to spread the consumption of energy over time reducing peak demand, as well as help to reduce the average demand of energy through efficiency increase. While the process of designing, constructing, starting up, controlling, and maintaining building systems is very complex, and changing the building and appliance industry overnight is not possible, we believe that a gradual roll-out plan can show impact in the very near future. We envision a triple-tiered research program for the introduction of societal-scale information systems into the demand side of the electrical energy equation.
• Phase 1: Passive monitoring. We will monitor energy usage of buildings and the health of individual appliances. The availability of cheap, connected (wired or wireless) sensors enables the end-user to monitor energy-usage of buildings as well as the health of individual appliances and act there-on. It has been estimated that the cost of the operation of “broken systems” in energy usage of commercial buildings is a whopping 30% of their operational budget ($45B/year nationwide) This information feedback plays the dual role of (1) primary feedback to the user on energy-consumption statistics, and (2) monitoring the health of the equipment and the environment – detect problems at the source.
Specifically, we will start by fully instrumenting several buildings on the UCB campus with networked light and temperature sensors in each room, and make the data available on a website. Then we will make a wireless power monitor with a standard 3-prong feedthrough receptacle so people can monitor power consumption of electronic devices as a function of time, providing roughly one thousand such devices for rotating use around the campus to educate, chart usage, verify compliance, real-time display of consumption in a given room or lab. The impact of these simple devices could be tremendous. A similar device would be passively coupled to high-power wiring to monitor total power consumption through breaker boxes. This would give us a much finer granularity of power-consumption details, and let us look at clusters of rooms, floors, etc. We will also instrument the campus steam network.
• Phase 2: Developing Mechanisms for Monitoring and Control. By combining the monitoring information with feedback on the cost of usage (augmented by an hourly pricing system reflecting wholesale market prices) helps to close the feedback loop between end-user and supplier. Key challenges here are to develop a pricing scheme which does not in itself cause instabilities in the bidding and consumption process by hierarchical verification.
• Phase 3: Active Energy-Management through Feedback and Control(Smart Buildings and Intelligent Appliances. The addition of instantaneous and distributed control functionality to the sensory and monitoring functions (measuring the operation of systems such as climate conditioning and lighting) increases the energy-efficiency of these functions dramatically, while at the same time improving the comfort of the users. We will experiment with control of power at UCB, enforcing compliance with load reduction, and charging/rewarding departments according to their use during peak times.
Supply Side: The deployment of SISs can substantially increase the efficiency and improve the control of the electricity-supply infrastructure as well. Through a combination of sensing, communication, computation, and control, the network can achieve major improvements in (1) the management and utilization of the distributed generation resources, (2) the efficiency of the distribution network, and (3) dealing with overflow conditions and emergencies. Especially the fine granularity of the information contents, combined with its timeliness, make it possible to introduce management and control techniques that otherwise would be impossible or useless. We list a few examples below; their ultimate implementation will require collaboration with State agencies.
Demand response. As identified earlier, exposing the true cost of energy to the end-user through, say, hourly pricing, encourages users to move their usage from expensive to inexpensive peiods. This demand response approach deals with a key deficiency in California’s market design – the disconnection between wholesale and retail markets. Closing the feedback loop in real time is essential in the long term but in the short time merely making costs visible to the end-user has proven effective: Georgia Power Company operates the largest real-time pricing program in the nation, with more than 1,600 commercial and industrial customers accounting for up to 5,000 MW of demand. Georgia Power estimates that it achieved load reductions ranging from 400 to 750 MW on moderate to very high-price days in 1999.
Increase in the transmission capacity of the grid. Constraints on line flows limit the use of the transmission grid to transfer power from the least expensive sources. Such line flow limits are proxy measures to prevent overheating of transmission line or other transmission equipment and sag of the lines (that could result in touching of trees leading to catastrophic failures). Without direct measurements the flow limits are set conservatively thus unnecessarily limiting the utilization of the transmission grid. Massive deployment of sensors that could measure and transmit data on temperature and line sag coupled with computation that would assimilate such data could significantly increase grid utilization and enhance the efficiency of electricity supply. While power companies currently using global environmental data to determine the load a transmission line can carry at a given time, dynamic and real-time distributed measurements of the weather conditions may increase the peak load of a wire as much as 30%.
Emergency Management. In case of emergencies (natural disasters, an overburdening of the distribution network, or through shortfall in available energy), the utilities must now lock off complete blocks of the power-grid (e.g. rolling blackouts). These blackouts have an enormous impact on the economy, and may cause life-threatening situations. The increased control granularity made available through widely dispersed SISs would make it possible to selectively manage power-consuming components and systems, and avoid blunt load-shedding. In the case of rolling blackouts, for instance, it would be possible to keep critical businesses and functions such as traffic lights on line. When even a larger granularity is available, one could even turn off non-essential devices, such as air-conditioning units, individually. For example, devices could routinely be equipped with a “standby” setting in addition to direct on/off control.
2.2 Disaster Risk Reduction and Emergency Response(Faculty: Fenves, Glaser, Kanafani, Demmel)
Each year large natural disasters cost the U.S. hundreds of lives, many critical structures, and billions of dollars in economic disruption. In particular, earthquakes present a substantial risk to large urban regions in the Western U.S., with probabilities exceeding 60% that a major earthquake will strike California in the next 30 years. Casualty estimates number in the thousands, direct damage losses are on the order of $100 to $200 billion and indirect losses due to disruptions in the economic base could be several times greater. Seismic hazard is not confined to California; with equally significant risks to the central and eastern U.S. from the New Madrid, Boston, and Charleston earthquake zones.
A recent NRC Report [NRC, 1999] states that improved information on natural disasters is the key to reducing losses and speeding recovery. Effective decisions by owners, operators and occupants of buildings is hampered today by lack of information about their structural safety. We contend that SISs can be used to protect lives and speed the economic recovery of a city after a large earthquake. These same technologies will be equally effective in response to tornadoes, hurricanes, fires, and floods. Here we describe SIS for three applications: (1) structural health prognosis of individual buildings and bridges, which pose the most hazard to the public in an earthquake, (2) real-time evaluation of inventories of buildings and lifeline networks, and (3) adaptive coordination of emergency response and recovery. We concentrate our efforts in this proposal on the first SIS, but note that it is an integral part of the latter two. All these SISs can share much of the same IT infrastructure as the SISs for energy and transportation (the latter is part of CITRIS not described here), making their costs marginal.
The NRC report also emphasizes the importance of tailoring information to the consumers in a disaster scenario, who comprise three main groups: (1) the system designers and developers, (2) the official emergency response staff, (3) the public at large. Designing for these groups, especially the last two, requires careful user needs analysis. We will apply our extensive experience [Newman 00, Elliott 00] in needs analysis to the analysis of these communities for SIS.
A current example of a regional sensor network is the Tri-Net system in California (Heaton, et al. 1996; NRC, 1999; Trinet, 2001), which contains approximately 750 ground accelerometers, communicating by digital telemetry to a central server. The ground motion data collected during an earthquake is used to develop “shakemaps” showing the distribution of ground motion. Currently, the shakemap is used to estimate losses (Buicka, et al., 1998; Scrivner, et al. 2000), although there is no direct measurement or assessment of loss. With the proposed sensor and distributed service technologies, information gathering can be scaled to much denser coverage of not only the ground motion but more importantly direct sensing of the effects of the ground motion on individual structures in an urban region.
2 Structural Health Diagnosis and Prognosis for Buildings and Bridges. With thousands of sensors monitoring a large structure, there is not enough power, bandwidth or space to collect and process all data in a central server (§3.1). Instead we must process data hierarchically, only occasionally collecting compressed traces [Ramachandran]. We propose to integrate modeling, data acquisition, and sensing processes that will allow civil engineers to approach design and prognostication problems from a new cognitive viewpoint – a move beyond the linear, off-line tradition.
We propose a new approach to structural health prognosis. Since damage begins locally, we will deploy “dense-packs” of sensors around key structural points e.g. a dozen 3-D accelerometers distributed around each key beam-column connection.
The most common approach to structural damage prognoses has been global modal analysis (e.g. McConnell, 1995), although recent full-scale experiments show that it is far too insensitive to yield usable information in practice (Farrar et al., 2001). A prime example is the modal analysis work undertaken on an abandoned bridge in Albuquerque, NM. It was only after the main longitudinal plate girder was cut more than 2/3 through that even a small change was seen in the modal parameters (Farrar and Doebling, 1997). Global modal analysis is doomed for several reasons: Because evolving damage is local, a complex structure will redistribute internal forces to stiffer members as particular beams, columns, etc. are weakened. It is only when damage is sufficient to affect the performance of the entire structure will it be visible through global modal analysis – well after the safety of the structure is compromised.
Evaluation of damage in structural terms (diagnosis of cracking, yielding, buckling, etc.) is not sufficient for making decisions about the safety of a building. A prognosis must be based on forward simulation of the effects of the damage with the current loading and expected aftershocks, and requires integration of measuring and modeling, constantly updating both the model and information sensed. Each building can have an online model of itself, constantly updated with parameters estimated from the damage detection network. As a major change in state is detected, the updated model will determine the safety of the structure in the short term, prioritize the inspection and repair in the longer term, and reprogram the sensor agents and constitutive model as needed. Information on prognosis may be condensed into an automatic notification system for occupants, including safe egress routes.
2.2.3 Approach to Structural Data Interpretation. Development of analytical tools for determining system response in terms of damage initiation and damage propagation, - understanding the interaction between the structural system and its components - is essential for performance-based design. The so-called system identification (SI) approach is a powerful statistical tool to quantify and assess system damage parameters, and has been applied by many structural researchers (e.g., Beck, 1978; Safak, 1997; Udwadia, 1985; Werner et. al., 1994; Stewart and Fenves, 1998; Arici and Mosalam, 2000; Baise and Glaser, 2000; Glaser and Baise, 2000).
System identification requires a model, whether black-box (e.g. a linear filter) or white box (a physical model). Identification can be made through the extended Kalman filter (e.g. Lin and Zhang, 1994; Koh and See, 1994;) which has successfully identified various physical systems. Physical parameters like elastic moduli, damping coefficients and effects of soil-structure interaction, can be identified.(e.g. Beck and Katafygiostis, 1998; Smyth et al., 1998; Stewart and Fenves, 1998; Lus et al., 1999; Glaser and Baise, 2000). Updating parameterized constitutive models with measured global response data has been attempted (Hjelmstad, et al. 1995; Fenves and DesRoches, 1997). Integration of finite element modeling with SI of boundary conditions has been done successfully at UCB (Arici and Mosalam, 2000). The most promising parameterization of an evolving system is a unified methodology based on Bayesian/State-Space identification and adaptive estimation (Sohn and Law, 1997; Beck and Katafygiotis, 1998).
With updated models, developed locally, forward simulations can be used to prognosticate the effects of damage. This is particularly critical when evaluating the safety of a building after a major earthquake and estimating the probability of collapse in an aftershock. For forward simulation, parameterized models can be updated and assembled in an object-oriented framework for simulation (Archer, et al., 1999; McKenna and Fenves, 2000). The models will be updated locally and assembled over the network in a dynamic process depending on processing, communication, and power available. Simulations may be centralized or distributed also. There can be hierarchies of simulation models: reduced parameter sets for rapid estimates, and more detailed models as processing power becomes available or sensitivity analysis shows that more refined models will reduce uncertainty in the prognosis.
Milestones. In year 1 we will develop model update procedures using sensor data and evaluate with small-scale laboratory tests. In year 2 we will implement sensing and diagnosis/progrognosis on structural specimens of building frames that will be tested on the Pacific Earthquake Engineering Research Center’s earthquake simulator (“shaking table”). This will provide a controlled laboratory setting to serve as the first-level testbed for the sensors, networking, and algorithms. In year 3: we will do field deployment on one of the new buildings planned for construction at UCB during the scope of the project. We anticipate collecting data during construction with forced-vibration tests to verify the system.
2.2.4. SIS for Inventories of Buildings and Lifeline Networks. Scaling up from individual buildings, owners of multiple buildings (corporate or university campus) are concerned with the effect of a disaster on the operation of their enterprise. Similarly, utility networks (electricity, gas, water) and transportation networks (highways, railways, ports and harbors, airports) must synthesize damage information to determine how to restore service. Owners of multiple facilities require assessment of damage, estimate of repairs, prioritization of repair, and acquiring and deploying resources at short time scales rather than weeks or months for repair.
3 SIS for Regional Emergency Response and Recovery. Emergency disaster response can be chaotic for lack of detailed information on damage location and severity, search and rescue needs, communication interruptions, and transportation interruptions for emergency service personnel and equipment. The potential for casualties can be reduced substantially by using SISs to prioritize and rout emergency services. Monitored buildings and precincts will be able to communicate relevant information to emergency services about extent and location of damage and needs for search, rescue, and fire response. This information, coupled with smart sensor and ubiquitous information appliance-based SIS information on the capacity of transportation systems, hospitals, fire fighting equipment, and heavy construction equipment, will allow rapid and effective matching of needs with capabilities.
For emergency response, its essential for staff to be able to reach key decision-makers and maintain awareness of the organization and activities of other response teams. This requires new techniques for representing user expertise and current activity. We will develop tools that build expertise profiles of decision-makers, track their post-disaster actions, and provide a “knowledge network” so that staff can (i) find an available decision-maker with expertise in an area and who has (ii) reviewed particular information about the situation and (iii) provide a visualization of disaster-response teams, including members, information they are reviewing, and issues that they are dealing with. Such distributed networks can accelerate decision-making in time-critical situations, and are tolerant of communication failures. A prototype will be built for the UCB campus.
3. SIS Design
The key open problems in designing an SIS to support the driving applications are as follows.
Sensor Level Architecture (§3.1): How should the underlying sensor network be programmed, synchronized, and maintained in the face of real time and low power constraints, intermittent and permanent failures of individual sensors, the need to download new software periodically, and physical inaccessibility preventing local maintenance?
Service Architecture for Distributed Systems (§3.2): A sensor network will be just one component in an SIS consisting of multiple data repositories, computational services, and system or user interfaces; some commercial, government, or academic; some reliable and some unreliable; some trustworthy or untrustworthy. These services will be created and establish relationships in real time. How?
Adaptive Data Management and Query Processing (§3.3): The data collected by sensor networks will be massive, real-time, intermittent, and noisy. How will it be collected, summarized, filtered and indexed to provide diverse users the data they want reliably and in real-time?
Human-Centered-Computing (§3.4): How do we determine and support the needs of diverse users who need (some of) the data? How should the data be presented to help them make decisions?
We will demonstrate such SISs on the room, building and campus scale.
3.1 Sensor Network Level Architecture (Target: 1 page) (Faculty: Culler, Pister)
1. Experimental Networked Sensor System Architecture
We will build on the SmartMotes and SmartDust described in §1, with which we have extensive experience: We recently dropped a number of styrofoam-encased SmartMotes from an airplane. They landed, formed a local area ad-hoc wireless network, tracked the movement of nearby traffic, and sent it to a remote server. But many problems remain to make them easily and reliably useful.
The sensor network architecture has 3 tiers. The microsensor tier consists of the sensor devices themselves. Device locations and their communication structure will change over time due to environmental factors or mobility. The nodes will create a self-configured, multihop distributed network with extensive in situ data filtering capability. They must operate unattended for long periods.
The sensor-base tier has far fewer and more powerful base-stations to serve as gateways to longer range networks and provide analysis and storage services. These devices are embedded PCs with a sizable power storage, network connectivity providing a bridge between the low-power wireless network and a conventional LAN or WAN interfaces, and a rich sensor suite. This tier provides additional sensor modes with a wider range to be focused on areas of interest, as determined by localized sensor data, as well as providing communication, programming, storage, and landmark resources to the microsensor tier.
The analysis and control tier provides storage and data analysis resources, as well as facilities to interactively program the lower tiers. Typically, it consists of powerful arrays of servers and services.
4 Nodal Operating Environment
The nodal operating system must be extremely energy efficient, especially in low duty-cycle vigilance mode, and be extremely facile under a burst of events. It must meet hard real-time constraints, such as sampling the radio signal within bit windows, while handling asynchronous sensor events and supporting localized data processing algorithms. It must be robust and re-programmable in the field.
Our starting point is our recent TinyOS event-driven system [Hill00]. We began this work because no existing OS provided the ability to deal with extensive concurrency, bit or bytewise processing, and dynamic events in just a few kilobytes of space. We will use very fine-grained and light weight multithreading. But the programming problem is different from either parallel programming or distributed systems because sensor networks operate largely as aggregates, where information moves from regions of the network to other regions according to some higher-level transformation, often with real time requirements, rather than point-to-point streams and file transfers between named devices. Our proposed nodal communication model provides 5 primitives: (1) local multicast transmission, (2) event driven reception, (3) retransmission pruning (4) aggregation and (5) buffer management. These core primitives serve both as compilation targets from higher-level descriptions and as a basis for algorithmic analysis. Networking concepts such as directed diffusion are built upon them.
Not only are traditional Internet layers and protocols too heavy-weight, but the communication patterns are very different. The identity of a node is not usually significant, relative to its role in the overall physical topology and the ability to precisely name data collected by the node[Int00]. Since low-power radio distance is limited, any node may have to serve as a router and the collection must self-organize into a dynamic, ad-hoc multi-hop network connecting to external tiers. While ad hoc routing algorithms can be developed independently of any particular application, application specific aspects must be incorporated to extract the most value out of each precious message [CACM00].
5 Aggregate Programming for Collaborative Processing.
Ideally, application scientists should be able to program sensor nets with aggregate query and processing expressions, that would be translated into specific sensor acquisition on the nodes, triggers, interrupts, and communication flow. The problem is related to database query processing, if one views the sensor data as a fine-grained distributed database, with data identified by key, rather than address. Rather than regular tables and records, we have a pool of intermittent, noisy data streams. A related viewpoint is that the sensor network is an extremely fine-grained tuple-space, as in Linda or JINI. Many operation are naturally data parallel, but on unstructured, constantly changing, real-time data, and so are likely to be statistical, rather than deterministic. We can borrow techniques from of online query processing [H+99] to report the result statistically and with tolerance for adversarial inputs from the nodes.These incremental techniques also provide a means of implementing triggers to indicate unusual events. In general, the aggregation operations must handle outliers within the network to be robust to processing and networking errors. We will investigate the right set of data parallel operations for programming sensor networks.
1. Service Architecture for Distributed Systems (Target: 1 page) (Faculty: Katz, Joseph),
Our overarching goal is to developing a deeper understanding of how to create end-to-end services with desirable and predictable properties, such as predictable performance and reliability, when provisioned from multiple and independent service providers. Services, such as distribution and caching of content (and its dual of sensor-based data collection and aggregation), mediation and adaptation for diverse end devices and access networks, billing and accounting subsystems, network mechanisms for indexing, service location, redirection, and naming, etc., represent the building blocks from which complex distributed applications are constructed. We seek to understand service level peering (SLP): building distributed services from multiple providers with desirable performance and reliability. Service platforms like .NET [Microsoft01] and ONE [Sun01] are monolithic with limited cross-platform interoperability and no performance guarantees. SLP is essential for more rapid SIS construction, by reducing the time to build services from independently deployed implementations, e.g., if electricity operators select alternative stand-alone systems for collecting real-time demand information, SLP allows these to interoperate under end-to-end constraints, such as sufficient bandwidth for data collection combined with limited latency to feed the demand management algorithms.
Our service architecture must support the dynamic confederation of collaborating and competing service provider. Most prior work has focused on the single provider case, e.g., [Brayton97, Duffeld99, Verma99]. Our Clearinghouse [Chuah00] offers a starting point for a scalable network resource manager based on reservations, admission, and policing, primarily for performance sensitive packet voice and video applications, that works across service providers. While focused on network bandwidth, it can be extended to manage processing and storage in the wide-area [Gribble01, Mao01, Kubi00], and its applications can be generalized to wide-area content distribution and assembly [Zhuang01]. It combines hierarchical monitoring and allocation with service provider peer-to-peer negotiation to achieve a combination of local control and scalability.
The primary challenge is to achieve SLP and resource sharing in an environment of limited trust and cooperation. The elements include: (i) an open service and resource allocation model, (ii) description of service provider resources, capabilities, and current status [3GPP], (iii) resource allocation mechanisms based on economic methods, such as electronic auctions, coupled with real-time accounting/billing/settlement systems [Stiller99] for the resources used, (iv) mechanisms for managing trust relationships among clients and service providers, and between service providers, based on trusted third party monitors, and (v) general services for forming dynamic confederations, such as discovering potential confederates and managing trust relationships.
We will construct testbeds at a variety of scales to investigate how the proposed architecture generalizes: room, building, campus, and regional-scales. At room-scale, the architecture coordinates bandwidth and limited processing among collaborating sensors and access points. At the building-scale, the testbed is extended to investigate resource coordination for bandwidth, processing, and storage across independent service providers in different regions of the building. The campus-scale testbed extends the environment in the directions of greater diversity of network technologies, with overlay service providers intermixed with departmental service providers within builders. Through some of our industrial collaborators (Appendix A), we plan to obtain measurements, experiment with new services and their resource demands, and generally gain experience of the opportunities and constraints in the wide-area through a regional-scale testbed.
2. Adaptive Data Management and Query Processing (Target: 1 page) (Faculty: Franklin and Hellerstein)
Societal Information Systems present challenges that cannot be met by existing data management technology. These challenges stem from their large scale, highly-distributed nature, and the need to actively assist users in wading through vast quantities of data in a near-real time manner. A key requirement for data management in SIS is adaptability. That is, the data management components of the SIS infrastructure must be able to quickly evolve and adapt to radical changes in data availability and content, systems and network characteristics, and user needs and context.
Traditional database query processing systems break down in such environments for a number of reasons: First, they are based on static approaches to query optimization and planning. Database systems produce query plans using simple cost models and statistics about the data to estimate the cost of running particular plans. In a dynamic dataflow environment, this approach simply does not work because there are typically no reliable statistics about the data and because the arrival rates, order, and behavior of the data streams are too unpredictable [UFA98] [HFCD+00].
Second, the existing approaches cannot adequately cope with failures that arise during the processing of a query. In current database systems, if the failure of a data source goes undetected, the query processor simply blocks, waiting for the data to arrive. If a failure is detected, then a query is simply aborted and restarted. Neither of these situations is appropriate in an SIS environment in which sources and streams behave unpredictably, and queries can be extremely long-running (“continuous”).
Third, existing approaches are optimized for a batch style of processing in which the goal is to deliver an entire answer (i.e., they are optimized for the delivery of the last result). In an SIS environment, where users will be interacting with the system in a fine-grained fashion, such approaches are unacceptable. Processed data (e.g., query results, event notifications, etc.) must be passed on to the user as soon as they are available. Furthermore, because the system is interactive, a user may choose to modify her queries on the basis of previously returned information or other factors. Thus, the system must be able to gracefully adjust to changes in the needs of the users [HACO+99].
The research topics we plan to address in data management for SIS are the following:
Adaptive Data Flow Processing . The Telegraph project at UC Berkeley is developing an adaptive dataflow processing engine. Telegraph uses a novel approach to query execution based on “eddies”, which are dataflow control structures that route data to query operators on an item-by-item basis [AH00]. Telegraph does not rely upon a traditional query plan, but rather, allows the ”plan” to develop and adapt during the execution. For queries over continuous streams of data, the system can continually adapt to changes in the data arrival rates, data characteristics, and the availability of processing, storage, and communication resources. An initial prototype of Telegraph has been built, but much remains to be done. The challenges to be addressed include: 1) the development of cluster-based and wide-area implementations of the processing engine, 2) the design of fault-tolerance mechanisms, particularly for long-running queries, 3) support for continuous queries over streaming data from sensors and web-based sources, and 4) the development of appropriate user interfaces for manipulating data flows.
Sensor Query Processing. Much of the data to be processed in SIS will be continually streaming in from tiny, low-power sensors. Techniques for querying these sensor data streams will be crucial. These techniques must not only be efficient, but must also be tolerant of the power limitations and error characteristics of the sensors. We plan to extend the data flow query processing architecture with two techniques for dealing with sensors: 1) the “Fjords” operator architecture, and 2) power-sensitive “sensor proxy” operators. The Fjords architecture provides the functionality and interfaces necessary to integrate erratic, streaming dataflows into query plans. It allows streaming data to be pushed through operators that pull from traditional data sources, efficiently merging streams and local data as samples flow past. Fjords also allow processing from multiple queries to share the same data stream, thereby providing huge scalability improvements. Sensor proxies are specialized query operators that serve as mediators between sensors and query plans, using sensors to facilitate query processing while adapting to their power, processor, and communications limitations.
Context Aware Data and Event Dissemination. Due to the huge volume of data managed by the SIS, such a system must provide special support for the targeted and timely delivery of relevant data and notifications to users based on their interests, roles, and context at a particular time. Such dissemination must be driven by user profiles, which contain information about user requirements, priorities, and information needs [CFG 00] [CFZ01]. We envision a user profile language that allows the specification of three types of information: 1) Domain specification: a specification of the kinds of data that are of interest to the user. This description must be declarative in nature, so that it can encompass newly created data in addition to existing data. The description must also be flexible enough to express predicates over different types of data and media. 2)Utility specification: because of limitations on bandwidth, device-local storage, and human attention, only a small portion of available information can be sent to a user. Thus, the profile must also express the user’s preferences in terms of priorities among data items, desired resolutions of multi-resolution items, consistency requirements, and other properties. 3) Context specification: user context can be dynamically incorporated into the dissemination process by parameterizing the user profile with user context information. This context information may be obtained through on-line observation of users, or from other sources such as data stored in Personal Information Management (PIM) applications such as the calendar, contact list, and To Do list. The challenges here involve language development, profile processing issues, and delivery scheduling. We plan to draw on our earlier work on large-scale XML document filtering for this purpose.
3. Human Centered Computing(Target: .5 pages) (Faculty: Canny, Hearst, Landay, Saxenien)
As per the NRC report, information visualization tools for disaster response should help diverse groups of users make sense of the situation as it unfolds in real time. Converting a massive, linked and distributed multi-sensor environment into human-understandable organizations will require development of fundamentally new human-computer interaction methods. Visualization will be critical both for helping system developers understand the placement and use of real-time sensor data, and for emergency response staff when responding to a disaster situation, but the interfaces for these two groups are likely to differ radically. The UCD visualization group has extensive experience in the problems of scalable, hierarchically-organized information visualization (§3.4.1), and others at UCB have been examining how to convert non-spatial information into human-understandable knowledge. [Olsen et al. 98, Avnur et al. 98, Hearst 99, Glaser 99, Yee 01]
(see
).
Innovative interfaces will be developed for the emergency response staff in the field and the public at large, both for monitoring the situation and for understanding what they specifically should do in response. The information must be accessible from a large number of different devices with different kinds of network connectivity, and it cannot be assumed that devices available to the public will be of the same quality as those available to the emergency response staff. User interfaces techniques must be designed that are sensitive to the size and the bandwidth of the access device, and so must work across large-wall sized displays, the web and on PDAs.
We have had some early experience building wall-sized interfaces to support the management of firefighters on the scene of a fire (see ). We will continue this work and adapt it to other situations, such as earthquakes. Interfaces must also work seamlessly in different modalities; for example, audio input and output will be necessary for the visually impaired or for those driving emergency vehicles. We are developing a design tool called CrossWeaver to help design and build these types of cross-platform, multimodal user interfaces (see ). Interfaces should also respond to the context of use -- for example, where the user is located and what level of stress or danger they are under should be determined automatically and used to modify what is displayed on the interface. Researchers at UCB are developing context-aware interface systems for distributed devices [Hong 01]. We will use CrossWeaver along with this context-aware infrastructure to develop a variety of interfaces for the emergency response staff as well as the public.
1. Interactive Visualization and Exploration of Multi-source Data Streams in Collaborative Environments Using Parallel and Distributed Computing (Target: .5 pages) (Faculty: Hamann; Max, Joy, Ma)
The required data visualization and exploration technology for massive data streams generated by up to millions of sensors monitoring energy status and consumption in large building complex do not yet exist. How do we visualize vast amounts of data over long distances where collaborative and/or time-critical data exploration is essential? How can we combine data streams generated by sensor arrays and visualize them in a super-imposed fashion? What type of networking technology and architecture can facilitate data collection and interpretation? Can topological approaches, used in scientific data analysis help "simplifying" massive sensor data?
The data sets generated by these types of applications must be reduced and compressed, and “summary" views provided. To achieve the needed compression, we will investigate hierarchical networking architectures in support of hierarchical data representations/formats. We will design hierarchical compression schemes (multi-resolution/wavelet methods) to support progressive data transmission for this purpose. These are research areas we will focus on: real-time multi-resolution compression and decompression schemes; collaborative data exploration over high-speed networks, real-time feature extraction of topologically/qualitatively relevant subsets; rendering and immersive interaction technology for large-scale display environments (power walls); and parallel and distributed computing technology for compression, analysis, and visualization. We will need to merge multiple views of an event, such as Image-Based Rendering with maps superimposed with damage data.
For this project, the UC Davis Group will build on its experience with the development of innovative techniques for geometric modeling, hierarchical data approximation and visualization, and multi-resolution rendering in immersive environments. This Group has published extensively during the past five years; emphasis areas that are related directly to this ITR proposal include hierarchical representation of massive data sets, see [Bertram00a], [Bertram00b], [Bertram00c], [Bremer01], [Gieng98], [Hamann99a], [Heckel99b], [Kreylos99], [Schussman00], and [Trotts99]; reconstruction of geometrical information/models, see [Bonnell00], [Gregorski00], [Hamann99b], and [Heckel99a]; rendering of massive data sets, see [Kreylos00], [Kuester00], and [LaMar99]; and topological, qualitative analysis of flow data, see [Scheuermann00].
4.Foundations
1. System Reliability (Target 2-3 pages) (Faculty: Henzinger, Aiken, Necula, Pister, Sastry, Wagner) (no refs yet!)
Concerns over IT system reliability increase with society's reliance on these systems. From a historical standpoint, this corresponds to the maturing of new technologies when the search for additional features is replaced by the need for High Confidence Systems. While functionality, speed, and availability dominate the headlines about new IT systems, the success of SISs will ultimately depend on reliability, including safety, predictability, fault tolerance, and their ability to interact with hard real-time constraints. Hand in hand with these demands are the needs to understand the vulnerabilities of SISs to information attack. We expect SISs to be subjected to either malicious or accidental attack, and cannot afford to have societal-scale systems be compromised. We believe that there are three central issues that need to be addressed in order to achieve acceptable reliability in SISs:
Modeling, prediction, and design of complex systems.
The first "weak link" in current design practice stems from the intrinsic *complexity* of SISs. While "complexity" in science usually refers to the understanding of complex systems that occur in nature (such as weather prediction), we submit that a different kind of complexity arises in systems that are designed by humans, and that if properly understood, this complexity can be controlled. The complexity of SISs arises from the large number of distributed but interacting components, the heterogeneous nature of components (digital computers as well as analog devices), the many levels of abstraction used in design (such as physical, system, protocol, and application layers), the many different aspects of system performance(such as functionality, timing, fault tolerance), and the many, often unpredictable ways in which the environment (sensors, users, failures, attackers) can influence the behavior of the system. Since current design practices are hitting their limits in the design of more homogeneous complex systems, such as microprocessors and software (see below), they cannot achieve acceptable reliability in SISs. We propose research in two key directions towards managing complexity by design: Modeling and analysis of networked hybrid and embedded systems, and Multi-aspect interfaces for component-based design.
Software quality.
The second weak link in current design practice concerns the lack of quality control in the development of large, concurrent software systems. As every SIS has significant software components that interact with each other as well as with sensors and actuators in many complex (see above) ways, software quality is an area of particular vulnerability for SISs. We propose research in two key directions towards improving software quality: Combining static and dynamic software analysis, and Memory safety.
Information Assurance for SISs.
While we have all been sensitized to the possible damage that can be wrought by denial of service, viral and other attacks on networks, we feel that SISs need to be even more resistant to attack. For sensor networks this translates into the need for an understanding of the vulnerabilities of the information gathering to appropriation of rogue nodes, attempts at deliberate mis-information and other modalities of attack We propose a program of research on information assurance for SISs:
4.1.1 Modeling and analysis of networked hybrid and embedded systems
Both target applications of CITRIS involve complex digital systems (computers and networks) interacting with the physical world through distributed sensors and actuators. Such a hybrid system combines the characteristics of discrete and continuous behavior. Theories and tools for modeling and analyzing hybrid systems have emerged over the past few years in control applications. Yet this research has focused mostly on developing algorithms (and impossibility results) for solving simple mixed discrete-continuous control problems. SISs are hybrid systems of a complexity that is certainly not open to precise algorithmic analysis. The focus must therefore shift to hybrid modeling techniques for capturing composition, hierarchy, and heterogeneity in a mixed discrete-continuous setting, and to approximate and stochastic techniques for system analysis and simulation.
While in classical hybrid systems theory, a single or small number of plants is modeled using differential equations, and a single or small number of controllers is modeled using state machines, such "hybrid automata" models are inadequate for networked embedded systems with a large number of sensor, processor, and actuator nodes. First, the appropriate model for a large number of nodes is continuous, not a discrete composition of individual discrete components, in the same way in which fluid dynamics and population dynamics are best studied abstractly as continuous processes, not as collections of individual molecules or creatures. Second, for large networks, unpredictable and faulty behaviors of individual nodes need to be modeled using global stochastic assumptions. This is a paradigm shift from concrete discrete behavior, which is too complex to be analyzed, to abstract continuous behavior, for which we will develop simulation and analysis techniques. At the same time, new discrete phenomena emerge on the abstract level, in the form of mode switches or phase transitions. For example, a sensor network may tolerate a certain number of faults without compromising its performance, but degrade quickly if that number is exceeded. This new view of modeling hybrid systems is accompanied by a paradigm shift from model construction (given the individual components and topology) to model extraction from simulation data, together with a paradigm shift from model verification (given a requirements specification) to model prediction (forecasting). In particular, active run-time monitoring and forecasting can be used for dynamically reconfiguring and optimizing the network.
Another area of special interest concerns the development of micro-protocols for the kind of real-time networks of embedded systems involved in SISs, for distribution services like synchronization, replication, consensus, leader election, etc. The classical solutions from distributed algorithms, as well as best-effort networking protocols, are no longer appropriate in a setting where individual misbehavior, such as individual sensor failure or package delay, is a common occurrence of low cost, but the cost of systemwide misbehavior, such as global breakdown or global reaction delay is high. This suggests the design of group communication protocols that may tolerate erratic micro-behavior in order to optimize macro-behavior and avoid undesirable global phase transitions.
4.1.2 Multi-aspect interfaces for component-based design
Existing formal design methodologies are either optimistic or pessimistic. The optimistic approach advocates strictly top-down, stepwise refinement design, with the design team in full control of the complete design. It does not allow for some parts or aspects of the design to be unknown, unpredictable, or evolving. The pessimistic approach is strictly bottom-up, component-based design, where some components may be pre-existing, and the design of each component must consider an environment that behaves in arbitrary, possibly adversarial way.
The centerpiece of our approach is the development of component interfaces that are much more expressive than traditional interfaces used in software or hardware designs. First, the interfaces we envision not only specify, on some abstract level, what a component does, but also what the component expects the environment to do. Such "assume-guarantee interfaces" allow the designer of a component to adopt an optimistic view about some aspects of the other components, as if those aspects were under the designer's control, and at the same time adopt a pessimistic view about other aspects of the other components and the environment, which may be unknown at design time or unpredictable. Second, the interfaces we envision not only specify aspects that are traditionally specified in interfaces, such as the number and types of the arguments of a procedure, but permit the specification of wide variety of different aspects, for example, that the call of the specified procedure must always be preceded by the call of another (for example, initialization) procedure. There has been considerable work on functional interface languages, little on timing and security, and virtually none on other system aspects such as resource management, performance, and reliability. This lack of multi-aspect interface formalisms has forced designers to address timing, security, performance, and reliability issues at all levels of the implementation in order to attain the desired properties for the global system.
We propose to develop a theory of composition for multi-aspect interfaces, which expose resource properties, such as real-time assumptions and guarantees. Based on such a theory, we will develop algorithms and tools for checking the consistency and compatibility of multi-aspect interfaces. The tools will allow us to evaluate our methodology by applying it to the experimental design projects within CITRIS. Multi-aspect interfaces benefit also the validation, portability, and evolvability of a system. The validation task can be decomposed into two largely independent phases: the validation that each component satisfies its interface, and the validation that the overall system requirements are met, given the component interfaces. For the latter phase, we can use the interfaces to construct simulation models that exhibit worst-case component behavior, and validate the system with respect to such simulation models. When porting the system we can check that the assumptions are met by the multi-aspect guarantees available in the new architecture.
Interfaces that Expose Real-time Behavior. Traditional API component specifications are usually based on an informal, English-based description of the functionality, the only formal information being input and output type information for function calls
This situation is radically different for real-time systems, where the quantitative differences of the underlying architectures (in terms of speed, memory, response times) play an essential role in determining the viability of the whole design, and are not masked by programming abstractions. The quantitative timing aspects of the behavior of components, however, are captured only in minimal part by the current informal approach to component specification. For example, the documentation of the APIs provided by current real-time operating systems is usually limited to their functional behavior. The real-time component of their behavior is either specified generically in separate documents, or it has to be inferred from a detailed analysis of the architecture. . By contrast, multi-aspect interfaces will permit the specification of timing assumptions and guarantees in an abstract, platform-independent way. An assume-guarantee interface specifies that the component guarantees certain behavior, under the assumption that the environment behaves correctly. To support the construction of systems derived from composing multi-aspect interfaces, we need to develop techniques for the assume-guarantee compositional reasoning about aspects that include timing, resource, and performance properties. Assume-guarantee compositional reasoning is understood for safety properties, little understood for real-time properties, and not at all studied for other aspects.
Interfaces that Expose Probabilistic Behavior. Multi-aspect interfaces will be able to capture not only deterministic guarantees, but also probabilistic properties connected to performance and reliability, such as the probability of meeting deadlines. In fact, many timeliness properties of real-time systems can be studied only in a probabilistic setting: a simple example is the message delivery delay over a non-deterministic protocol such as Ethernet. We will develop assume-guarantee techniques for reasoning compositionally about probabilistic real-time interfaces. In addition, we will develop algorithms for checking the compatibility of such interfaces. The focus on the interface level, without regard to implementation details, will ensure compositionality and a degree of abstraction that makes the application of formal tools feasible.
4.1.3 Combining static and dynamic software analysis
Our goal is to invent a new class of techniques and tools for finding and removing defects in software systems. With very few exceptions, the current tools available to software developers can be classified as either exclusively static (the analysis is done by reasoning about the program text without running the program) or exclusively dynamic (the analysis is done by executing the program). We believe there is a class of useful tools that combine static and dynamic approaches and that research in this direction is likely to be productive and to require new, basic techniques.
. For example, type checking (a static analysis) excels at reliably detecting certain classes of bugs without the need to execute the program. Software testing (executing a program on sample inputs---a dynamic analysis) is the mainstay of quality assurance departments in industry. Both approaches have inherent limitations. By their nature, static analysis tools can prove useful, but limited properties of all program executions. Dynamic analysis tools can prove very precise properties, but only of single executions.
We envision a better world, made possible by a tight coupling of static and dynamic analysis techniques. In this world, static analysis techniques allow the construction of "active" testing infrastructures that use information derived from static analysis of the program to automatically produce customized test harnesses and tests targeted at particular semantic properties. In addition, the infrastructure provides a framework for the addition of other static or dynamic analyses, such as residual analysis. Such mixed dynamic/static analysis tools are effective because the two approaches are naturally complementary and in fact mutually reinforcing in well-designed applications. Thus, the combination greatly increases the set of program properties that can be feasibly checked during software development.
Statically Assisted Testing. This is an example of a dynamic-then-static analysis. Using static analysis techniques to infer needed information from the program source, it should be possible to automate much of the process of constructing and maintaining a test infrastructure. Given an initial test suite with some coverage, how much can coverage be improved by purely static techniques? By a combination of instrumented tests and static analysis, it should be possible to perturb given tests to improve coverage. Dually, given a set of tests, how orthogonal are they? Is there a subset of the tests that give the same code coverage, and can we find that subset without a brute force solution that examines all possible subsets? Finally, given a program, a test suite, and a change to the program, use dependency analysis (a static analysis) to eliminate tests that do not need to be rerun because their result could not be affected by the change.
Residual Analysis. This is an example of a static-then-dynamic analysis. Static analysis is useful for proving conservative bounds on a program property. The idea of emitting residual code to cover cases at run-time that cannot be dealt with statically is well-understood from the fields of partial evaluation and soft (or dynamic) typing. The next step is to use the residual code to drive testing: the inserted tests show where testing effort should be focused, and the information computed by the static analysis suggests a range of test cases to try. By replacing memory safety in this discussion with any other desired safety property, we see that residual analysis is one general recipe for a class of static-then-dynamic analyses.
4.1.4 Information Assurance for SISs
Issues in lightweight authentication protocols for networked embedded systems to be addressed are new techniques for sender authentication, and scalable key distribution techniques for challenge/authentication protocols for sensor nodes that are scattered in the environment to keep track of whether they have been compromised, which leverage secure multicast work. In addition, we will work on timely propagation of revocation information such as compromised keys, expired certificates, and rekeying in the event of compromise of the nodes.
In terms of information processing for possibly compromised SISs we will study the use of traditional fault-tolerant networking techniques such as replication and partitioning of network services, redundancy of network resources and survivable network overlays (including replica creation and management). In the area of self healing of networks, we will bring to bear techniques from statistical signal processing in two different ways: when a rogue node starts broadcasting information that is widely deviant from hypotheses that are determined to be true either on the basis of past data or from a number of other (possibly uncorrupted) nodes, we will use decision networks to treat the rogue node information as an outlier and thereby discard it and at the same time propagate the hypothesis up the hierarchy of the SIS. In the event of a large scale attack on a group of nodes, we will explore the use of game-theoretic methods (against an intelligent adversary) to isolate the group of nodes that are under attack and propagate alarms up the SIS hierarchy about the need for intervention.
2. System Availability: Repair-Centric Design (Target: 2-3 pages) (Faculty: Patterson, Yelick)
In clusters of clusters that enable SISs, availability is critical. For example, after a disaster these systems must be continuously available or lives may be lost.
The prior section looks at improving the reliability of software, which is one piece of the problem. The other pieces are hardware and human operator failure. The hardware itself is quite reliable and we have effective techniques to tolerate hardware failures, and is perceived to be less of a problem than before.
What about human-induced system failures? Data from the late 1970s reveals that operator error accounted for 50-70% of failures in electronic systems, 20-53% of missile system failures, and 60-70% of aircraft failures [1]. In the mid-1980s, a study of failures in fault-tolerant Tandem systems revealed that 42% were due to system administration errors—again human error [3]. Data collected on the causes of failures in VAX systems reveals that in 1993, human operators were responsible for more than 50% of failures, and that the error rate was rising as hardware and software failures become less important [9]. A study of the telephone network (arguably one of the most fault-tolerant systems in deployed use today) between 1992 and 1994 reveals that human errors resulted in 52% of non-overload outages and were responsible for 50% of non-overload outage minutes, with about half of those due to errors made by telco personnel performing maintenance [7]. And more recently, in 1999, a Vice President at Oracle was reported as claiming that one “can have the best technology on the planet, but half the failures we analyze are human error” [8]. Thus human error is probably the biggest problem facing availability of SISs.
What can be done to improve the situation? The definition of availability is
Availability = Mean Time To Fail / (Mean Time To Fail + Mean Time to Repair)
Thus we can improve availability either by making the components more reliable and thus increasing their Mean Time to Fail, or by improving the time to recover from failure and thereby reducing the Mean Time to Repair. Although there is extensive literature and efforts on improving reliability, there is little on reducing repair time.
Thus we propose to concentrate on repair, inspired by a quote from Shimon Peres:
“If a problem has no solution, it may not be a problem, but a fact, not to be solved, but to be coped with over time”
We believe significantly improved availability can only come once failures by hardware, software, and especially people are accepted as a normal, unavoidable fact of system operation, and systems must be designed with fast and effective repair mechanisms that mitigate the long-term impact of those failures. We call this philosophy repair-centric design.
At its heart, repair-centric design addresses hardware, software, and human failures by providing rapid and effective mechanisms for detecting and recovering from them. These mechanisms should be designed to make as few assumptions about failure characteristics as possible, and they should provide means to recover from unanticipated catastrophic failures that make it past any standard fault-tolerance lines of defense.
Furthermore, a repair-centric system design has to go beyond simply providing recovery mechanisms. To truly have a repair-centric design, recovery mechanisms have to be treated as first-class parts of the system, and integrated into a framework that manages their use and guarantees their effectiveness.
This repair-centric framework needs to provide several guarantees. First, it must ensure that problems and failures are detected quickly so that they can be contained or repaired as soon as possible, and before they have propagated through the system. As part of this detection, a repair-centric system should strive to expose and repair latent errors in the system before they are activated; the kinds of “normal accidents” analyzed by Perrow [5] often occur only when many latent errors have accumulated in the system and are all activated simultaneously in a chain-reaction cascade of failures. Furthermore, repair-centric systems should provide assistance in diagnosing the root cause of problems once they have been detected, speeding repair of the correct system component.
In addition to fast failure detection, a repair-centric system must also guarantee that its repair mechanisms are trustworthy, whether they are fully automated or require human intervention; this is a particular problem today, as recovery code is difficult to test and thus is often untested or buggy. The solution is to periodically test recovery code in situ as part of normal system operation, allowing automated recovery mechanisms be exercised and verified in the production environment. When repair requires human intervention, those mechanisms should be exercised as well: the human operators should be subjected to realistic “fire-drill” simulations of failures and repair, allowing them to become familiarized with the system’s failure modes, maintenance interfaces, and recovery procedures, all in the realistic context of the production environment. Such realistic, on-the-job operator training helps human operators calibrate their mental models of the system and allows them to make mistakes and learn from them, an essential part of gaining familiarity and confidence with system repair tasks.
The last key guarantee for a repair-centric system is that it must tolerate further errors and failures during recovery and repair. In the large-scale systems that are being built today, the statistical probability of double failures is becoming non-negligible. Furthermore, with human operators involved in recovery and repair procedures, human-induced failures during these procedures are inevitable.
How can we build repair-centric systems? A full discussion is well outside the scope of this proposal, but here are a few important techniques. First, a repair-centric system inherently requires redundancy of hardware and data in the form of clustered hardware with replicated state. The system design must be partitionable to support fault containment and to provide the means of safely exercising repair mechanisms; again, physically-partitioned designs such as clustered organizations seem appropriate. To achieve the goal of quickly detecting failures, repair-centric systems should be built to incorporate extensive self-testing and checking at the component and system-wide level. In addition to traditional assertion-checking techniques, system components should verify the proper behavior of dependent components by explicitly injecting realistic test inputs and checking the resulting outputs for both correctness and performance. To aid in diagnosis, repair-systems should automatically track the health of all components, and use techniques such as dependency analysis to automatically pinpoint the root-cause of detected problems. Finally, to carry out the exercising of recovery mechanisms needed to guarantee their proper behavior, repair-centric systems should have integrated mechanisms for fault-injection to simulate failures and to trigger recovery mechanisms.
To achieve success we need to measure it: the factor of 10000 in improvement in hardware performance over the last two decades is due in part to widely accepted benchmarks to evaluate results. Although benchmarking availability will be difficult, as it involves measuring behavior of human subjects, there are many research areas of academia — including human centered systems — based on measuring human subjects. We will collaborate with experts in those areas to measure people and systems as maintenance events are inserted.
Thus the goals of this section are to 1) Develop princples of repair-centric design where errors occur due to hardware, software, and people; 2) Chataracterize failures by hardware, software, and people to develop a failure workload; 3) Develop availability benchmarks to measure systems; and 4) Demonstrate the principles by running availbility benchmarks on a SIS designed according to those principles, and contrast its behavior to traditional systems.
3. Security and Policy (Target: 1 page) (Faculty: Tygar, Wagner, Samuelson) (no refs yet!)
A central theme throughout this proposal is the use of widespread sensors to collect and deliver information and of distributed systems to respond and act upon the information presented. This presents a number of important security challenges:
(1) We need to be able to authenticate and secure messages sent from, to, and among the sensors. It is unacceptable if a hostile party is able to trigger a major alert for the disaster response application, for example. While cryptography can solve many of these problems, sensors provide a particular difficult technical challenge is increased because sensors will typically have minimal computational abilities. We have developed a family of lightweight broadcast/multicast stream authentication and signatures algorithms, TESLA and EMSS [CITATIONS 1.1] that we have implemented on Berkeley's experimental SmartDust [CITATIONS 1.2] platform. This provides for security on an 8-bit device with only 8KBytes of ROM and 512 bytes of RAM. We are also exploring access control through the ELK key distribution protocol [CITATION 1.3]. In this work, we will adapt and build security protocols for sensor class devices.
(2) The use of sensors raises significant privacy questions. How can we collect data and provide maximum assurance that it will not be misused? In many cases, aggregate information only can be provided. We will explore both technical and policy aspects of this question [CITATIONS 2.1, 2.2].
(3) Large-scale monitoring systems will need to aggregate data and distribute computation across platforms controlled by participants with diverse interests. Current approaches to security, based on perimeter security, are brittle and scale poorly: when any intruder who can bypass the firewall gains full access to the system, a single intrusion can defeat the entire system. We will seek lightweight techniques to ensure that SISs degrade gracefully even in the presence of a small number of malicious parties or intrusions. We will study two approaches to improving robustness. First, we will study algorithms and distributed data structures that are resilient even in the presence of a small fraction of maliciously chosen inputs or untrustworthy protocol participants, and we will examine techniques such as random sampling, averaging, and replication for this purpose. Second, we will study programming disciplines for reducing the risk of vulnerability in security-critical source code, and we will develop static and runtime tools for identifying violations of these "good security hygiene" guidelines. [CITATION 3]
(4) Recent legislation and policies in the area of cyberlaw, such as the Digital Millenium Copyright Act, have profound implications on the ability of outside organizations to legally test the security and responsiveness of security devices including distributed sensors [CITATIONS 4]. We will examine the consequences of these policies and highlight potential issues. When appropriate, we will also examine potential policy recommendations.
18 Algorithms (Target: ? pages) (Faculty: Papadimitriou) (Spread into other sections?)
The CITRIS effort will require a new generation of algorithmic ideas and techniques, in three rough categories: (1) Algorithms related to the applications, including visualization, supported by the proposed SISs; (2) general algorithmic problems involved in the design of the SIS architecture; and (3) algorithmic problems involved in the operation of the specific SISs proposed. A strength of the investigator team is a strong interest in basic algorithmic methods for the analysis of complex systems: In this section we briefly expand on algorithms for items (2) and (3). We emphasize that algorithms for all the items will also be developed integrally as part of the proposed research in §3 and §4.1-4.3 as well.
In the area of heterogeneous networking, we have embarked on a foundational algorithmic study of the optimization problems related to congestion control and network design in the context of the Internet [see REF1]. The ab initio design of the SISs in CITRIS will be a valuable test bed for the ideas that have emerged from that work, and an opportunity for adapting them to novel environments. The SISs to be built by CITRIS will resemble the Internet in rough scale, but will differ dramatically from it in their socio-economic nature (built and operated by entities of varying degrees of cooperation and trust, but not predominantly competitive), and in their data and traffic profiles (steady streams, very infrequent bursts, mostly non-time-critical data, deep priority hierarchies). The protocols developed for these SISs, as well as their interconnection technologies and topologies, will probably not resemble Internet protocols or technologies/topology at levels below the very highest level. Of specific interest is the development of new light weight protocols for SISs and their optimized design. The design of the SIS network architecture will influence deeply (and will be based on) network operation characteristics. There will be data compression (both lossless and lossy) at every level of the network (communication protocols at the sensor level exploiting data correlations, fundamental tradeoffs to be made between computing and communicating (with a bank balance of total energy and peak power consumption) will need to be made in the nJ/ bit for transmittal or for localized algorithms, tradeoffs of latency versus energy and power consumption will need to be made online for the networks depending on the urgency of the situation being monitored and communicated, application-dependent data combining and data mining at the server level, further combining, mining, and prioritizing at higher network levels), together with background traffic of raw data for archiving whose levels of priority reflect potential criticality. These performance issues will complement concerns of trust, security, privacy, and dependability in a genre of novel algorithmic problems of unprecedented scope and scale, combining for the first time three basic aspects: communication, analysis/processing, and storage/ protection of data.
Education and Outreach (Target: .25 pages)
In addition to an ambitious program of curriculum develeopment at Berkeley, our main outreach partner is to UC Merced (see the attached letter from Provost Designate David Ashley in Appendix B). UC Merced will be the first new American research university built in the twenty-first century in California’s great agricultural heartland. While the new campus will draw students from all over California, it has a special mission to expand participation of underrepresented students, particularly Hispanic, first generation college-going, low income and rural students from the San Joaquin Valley. These students are not well represented in technology–oriented science and engineering . UC Merced plans to open for instruction in Fall 2004 with 100 faculty, half in science and engineering fields. Our partnership will contribute to UC Merced’s ability to recruit outstanding faculty working at the cutting edge of engineering and information technology. Some targets of recruitment will be faculty who can contribute directly to the work in SISs and would hold periodic residences at Berkeley. These faculty in turn will be able to recruit outstanding graduate students on whom UC Merced’s excellence in graduate education will be based. In addition, because faculty recruitment will be phased over the next three years, UC Merced will be able to contribute to research beginning in Fall 2002. The area of energy efficiency, has special importance to UC Merced as a new university. As part of a region characterized by extremes of 100(+ heat and near-freezing temperatures, UC Merced has the opportunity to be a model for an environmentally effective design in all aspects of its building and campus operations program. Thus, beginning with the Spring 2002 groundbreaking, UC Merced will serve as a test bed for research applications in SIS for energy efficiency. Making the building of the campus a target of research will be UC Merced’s unique contribution to this proposal.
Another critical element of the partnership is development of undergraduate education at UC Merced. UC Merced faculty will collaborate with UC Berkeley on developing lower division preparation courses in a technology-based format for remote delivery. In addition, this spring, UC Merced will begin its outreach to Valley Community College students through publication of curricular pathways that will prepare students to transfer to UC Merced’s science and engineering programs. Ultimately, these courses will support undergraduate education of all UC Merced students, whether they begin their education on campus or prepare for UC Merced through a Community College articulation program
References
Arici, Y. and K. M. Mosalam, (2000) System Identification and Modeling of Bridge Systems for Assessing Current Design Procedures, Proceedings of SMIP2000 Seminar, Sept. 14, Sacramento, CA
Baise, L.G., and Glaser, S.D. (2000), Repeatability of Site Response Estimates Made Using System Identification, Bulletin of the Seismological Society of America, 90(4), pp. 993-1009.
Beck, J.L. (1978). Determining Models of Structures from Earthquake Records. Earthquake Engineering Research Laboratory 78-01. California Institute of Technology.
Beck, J.L., and Katafygiotis, L.S. (1998). Updating Models and Their Uncertainties. I: Baysian Statistical Framework, Journal of Engineering Mechanics, 124(4), p. 455.
Farrar, C.R. and Doebling, S.W., (1997) Lessons Learned from Applications of Vibration-Based Damage Identification Methods to Large Bridge Structures, Proc. of the International Workshop on Structural Health Monitoring, Stanford, CA, Sept 1997, pp. 351-370.
Farrar, C.R., Doebling, S.W., Nix, D.A., (2001) Vibration-Based Structural Damage Identification, Philosophical Transactions of the Royal Society: Mathematical, Physical & Engineering Sciences, 359(1778), pp. 131 - 149
Glaser, S.D., and Baise, L.G. (2000), System Identification Estimation of Damping and Modal Frequencies at the Lotung Site, Soil Dynamics and Earthquake Engineering, 19(6), pp. 521-531.
Lin, J.-S. and Zhang, Y. (1994). Nonlinear structural identification using extended Kalman filter. Computers and Structures, 52(4), p.757.
McConnell, K.G. (1995) Vibration Testing: theory and practice, Wiley, p. 606.
Safak, E. (1997). Propagation of Seismic Waves in Tall Buildings. Tall Buildings for the 21st Century (Proceedings of the 4th Conference on Tall Buildings in Seismic Regions), 129-154.
Smyth, A.W., Masri, S.F., Chassiakos, A.G., and Caughey, T.K. (1999). On-Line Parameter Identification of MDOF Nonlinear Hysteretic Systems, Journal of Engineering Mechanics, 125(2), p. 133.
Udwadia, F. E. (1985). Some Uniqueness Results Related to Soil and Building Structural Identification, SIAM J. Applied Math., 45(4), p. 674.
Werner, S.D., Crouse, C.B., Katafygiotis, L.S., and Beck, J.L. (1994) Use of strong motion records for model evaluation and seismic analysis of a bridge structure, Proceedings of the Fifth U.S. National Conference on Earthquake Engineering, 1, 511-520.
3GPP] .
[Braden 97] R. Braden, L. Zhang, S. Berson, S. Herzog and S. Jamin, “ReSerVation Protocol (RSVP) Version 1 Functional Specification,” Internet RFC 2205, IETF Network Working Group, September 1997. //merit.edu/~ipma/tools/lookingglass.html.
[Chuah 00] C. Chuah, L. Subramanian, A. D. Joseph, R. H. Katz, “QoS Provisioning Using A Clearing House Architecture,” 8th International Workshop on Quality of Service (IWQOS 2000), Pittsburgh, PA, (June 2000).
[Duffeld99] N. Duffeld, P. Goyal, A. Greenberg, P. Mishra, K. K. Ramakrishnan, J. E. Van der Merwe, “A Flexible Model for Resource Management in Virtual Private Networks," Proc. of ACM Sigcomm, pp. 95-108, (September 1999).
[Gribble01] S. D. Gribble, M. Welsh, R. von Behren, E. A. Brewer, D. Culler, N. Borisov, S. Czerwinski, R. Gummadi, J. Hill, A. Joseph, R. H. Katz, Z. M. Mao, S. Ross, B. Zhao, “The Ninja Architecture for Robust Internet-Scale Systems and Services,” Journal of Computer Networks, Special Issue on Pervasive Computing, to appear.
[Kubi00] J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, B. Zhao, “OceanStore: An Architecture for Global-Scale Persistent Storage,” Proceedings of the Ninth international Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), November 2000.
September 1999.
[Mao 01] Z. Mao, W. So, R. H. Katz, “Network Support for Mobile Multimedia Using a Self-Adaptive Distributed Proxy,” ACM NOSSDAV 2001, New York, (June 2001).
[Microsoft 01] Microsoft Corporation, .Net Home Page, .
[Stiller 99] B. Stiller, T. Braun, M. Gunter and B. Plattner, “The CATI project: charging and accounting technology for the Internet,” Proc. of 4th European Conference: Multimedia Applications, Services and Techniques, pp. 281-96, May 1999.
[Sun 01] Sun Corporation, Java Home Page, .
[Verma 99] D. Verma, Supporting Service Level Agreements in IP Networks, Macmillan Publishing Company, New York, 1999.
[Zhuang 01] S. Zhuang, B. Zhao, A. Joseph, R. H. Katz, J. Kubiatowicz, “Bayeux: An Architecture for Wide-Area, Fault-Tolerant Data Dissemination Protocol,” ACM NOSSDAV 2001, New York, (June 2001).
[3GPP] .
[Chuah 00] C. Chuah, L. Subramanian, A. D. Joseph, R. H. Katz, “QoS Provisioning Using A Clearing House Architecture,” 8th International Workshop on Quality of Service (IWQOS 2000), Pittsburgh, PA, (June 2000).
[Mao 01] Z. Mao, W. So, R. H. Katz, “Network Support for Mobile Multimedia Using a Self-Adaptive Distributed Proxy,” ACM NOSSDAV 2001, New York, (June 2001).
[Microsoft 01] Microsoft Corporation, .Net Home Page, .
[Raman 00] B. Raman, R. H. Katz, A. Joseph, “Providing Extensible Personal Mobility and Service Mobility in an Integrated Communication Network,” 3rd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA2000), Monterey, CA, (December 2000).
[Sun 01] Sun Corporation, Java Home Page, .
[Zhuang 01] S. Zhuang, B. Zhao, A. Joseph, R. H. Katz, J. Kubiatowicz, “Bayeux: An Architecture for Wide-Area, Fault-Tolerant Data Dissemination Protocol,” ACM NOSSDAV 2001, New York, (June 2001).
[AF00] Mehmet Altinel, Michael J. Franklin. Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the International Conference on Very Large Data Bases, Cairo, September 2000.
[AH00] Ron Avnur, Joseph M. Hellerstein. Eddies: Continuously Adaptive Query Processing, Procedings of the ACM SIGMOD Conference, Philadelphia, PA, June 2000,
[CFG00] Ugur Cetintemel, Michael J. Franklin, and C. Lee Giles. Self-Adaptive User Profiles for Large-Scale Data Delivery, Proceedings of the International Conference on Data Engineering, San Diego, CA, February, 2000, pp 622-633
[CFZ01] Mitch Cherniack, Michael J. Franklin, Stan Zdonik. Expressing User Profiles for Data Recharging, accepted for publication, IEEE Personal Communications, April 2001 (to appear).
[HACO+99] Joseph M. Hellerstein Ron Avnur, Andy Chou, Chris Olston, Vijayshankar Raman, Tali Roth, Christian Hidber, Peter J.Haas. Interactive Data Analysis with CONTROL, IEEE Computer 32(8), August, 1999, pp. 51-59.
[HFCD+00] Joseph M. Hellerstein, Michael J. Franklin, Sirish Chandrasekaran, Amol Deshpande, Kris Hildrum, Sam Madden, Vijayshankar Raman, Mehul Shah. Adaptive Query Processing: Technology in Evolution, IEEE Data Engineering Bulletin, June 2000, pp 7-18.
[UFA98] Tolga Urhan, Michael J. Franklin, Laurent Amsaleg. Cost Based Query Scrambling for Initial Delays,Procedings of the ACM SIGMOD Conference, Seattle, WA, June 1998, pp. 130-141.
[Bertram00a] Bertram, M., Barnes, J.C., Hamann, B., Joy, K.I., Pottmann, H. and Wushour, D. (2000), Piecewise optimal triangulation for the approximation of scattered data in the plane, Computer Aided Geometric Design 17(8), ELSEVIER, pp. 767-787.
[Bertram00b] Bertram, M., Duchaineau, M.A., Hamann, B. and Joy, K.I. (2000), Bicubic subdivision-surface wavelets for large-scale isosurface representation and visualization, in: Ertl, T., Hamann, B. and Varshney, A., eds., Visualization 2000, IEEE Computer Society Press, Los Alamitos, California, pp. 389-396.
[Bertram00c] Bertram, M., Duchaineau, M.A., Hamann, B. and Joy, K.I. (2000), Wavelets on planar tesselations, in: Arabnia, H.R., Coudoux, F.-X., Mun, Y., Power, G.P., Sarfraz, M. and Zhu, Q., eds., Proc. The 2000 International Conference on Imaging Science, Systems, and Technology (CISST 2000), Computer Science Research, Education, and Applications Press (CSREA), Athens, Georgia, pp. 619-625.
[Bonnell00] Bonnell, K.S., Schikore, D.R., Joy, K.I., Duchaineau, M.A. and Hamann, B. (2000), Constructing material interfaces from data sets with volume-fraction information, in: Ertl, T., Hamann, B. and Varshney, A., eds., Visualization 2000, IEEE Computer Society Press, Los Alamitos, California, pp. 367-372.
[Bremer01] Bremer, P.-T., Hamann, B., Kreylos, O. and Wolter, F.-E. (2001), Simplification of closed triangulated surfaces using simulated annealing, in: Lyche, T. and Schumaker, L.L., eds., Mathematical Methods in CAGD: Oslo 2000, Vanderbilt University Press, Nashville, Tennessee, pp. 45-54.
[Gieng98] Gieng, T.S., Hamann, B., Joy, K.I., Schussman, G.L. and Trotts, I.J. (1998), Constructing hierarchies for triangle meshes, IEEE Transactions on Visualization and Computer Graphics 4(2), pp. 145-161.
[Gregorski00] Gregorski, B.F., Hamann, B. and Joy, K.I. (2000), Reconstruction of B-spline surfaces from scattered data points, in: Magnenat-Thalmann, N. and Thalmann, D., eds., Proceedings of Computer Graphics International 2000, pp. 163-170.
[Hamann99a] Hamann, B., Jordan, B.W. and Wiley, D.F. (1999), On a construction of a hierarchy of best linear spline approximations using repeated bisection, IEEE Transactions on Visualization and Computer Graphics 5(1/2), pp. 30-46, p. 190 (errata).
[Hamann99b] Hamann, B., Kreylos, O., Monno, G. and Uva, A.E. (1999), Optimal linear spline approximation of digitized models, in: Banissi, E., Khosrowshahi, F., Sarfraz, M., Tatham, E. and Ursyn, A., eds., Proc. "1999 IEEE International Conference on Information Visualization (IV '99) - Computer Aided Geometric Design Symposium," IEEE Computer Society Press, Los Alamitos, California, pp. 244-249.
[Heckel99a] Heckel, B., Uva, A.E. and Hamann, B. (1999), Cluster-based generation of hierarchical surface models, in: Hagen, H., Nielson, G.M. and Post, F., eds., Proc. Scientific Visualization - Dagstuhl '97, second printing, IEEE Computer Society Press, Los Alamitos, California, pp. 113-122.
[Heckel99b] Heckel, B., Weber, G.H., Hamann, B. and Joy, K.I. (1999), Construction of vector field hierarchies, in: Ebert, D.S., Gross, M. and Hamann, B., eds., Visualization '99, IEEE Computer Society Press, Los Alamitos, California, pp. 19-25.
[Kreylos99] Kreylos, O. and Hamann, B. (1999), On simulated annealing and the construction of linear spline approximations for scattered data, in: Groeller, E., Loeffelmann, H. and Ribarsky, W., eds., Data Visualization '99 (Proc. "VisSym '99"), Springer-Verlag, Vienna, Austria, pp. 189-198.
[Kreylos00] Kreylos, O., Ma, K.-L. and Hamann, B. (2000), A multi-resolution interactive previewer for volumetric data on arbitrary meshes, in: Outhyoung, M. and Shih, Z.-C., eds., Proc. 2000 International Computer Symposium – Workshop on Computer Graphics and Virtual Reality, Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi, Taiwan, R.O.C., pp. 74-81.
[Kuester00] Kuester, F., Duchaineau, M.A., Hamann, B., Joy, K.I. and Ma, K. L. (2000), The DesignersWorkbench: towards real-time immersive modeling, in: Merritt, J.O., Benton, S.A., Woods, A.J. and Bolas, M.T., eds., Stereoscopic Displays and Virtual Reality Systems VII, Proc. SPIE Vol. 3957, SPIE – The International Society for Optical Engineering, Bellingham, Washington, pp. 464-472.
[LaMar99] LaMar, E.C., Hamann, B. and Joy, K.I. (1999), Multiresolution techniques for interactive texture-based volume visualization, in: Ebert, D.S., Gross, M. and Hamann, B., eds., Visualization '99, IEEE Computer Society Press, Los Alamitos, California, pp. 355-361.
[Scheuermann00] Scheuermann, G., Hamann, B., Joy, K.I. and Kollmann, W. (2000), Visualizing local vector field topology, Journal of Electronic Imaging 9(4), special section on visualization and data analysis, SPIE - The International Society for Optical Engineering, pp. 356-367.
[Schussman00] Schussman, S.E., Bertram, M., Hamann, B. and Joy, K.I. (2000), Hierarchical data representations based on planar Voronoi diagrams, in: de Leeuw, W.C., van Liere, R., eds., Data Visualization 2000 (Proc. "VisSym '00"), Springer-Verlag, Vienna, Austria, pp. 63-72.
[Trotts99] Trotts, I.J., Hamann, B. and Joy, K.I. (1999), Simplification of tetrahedral meshes with error bounds, IEEE Transactions on Visualization and Computer Graphics 5(3), pp. 224-237.
1] J. M. Christensen and J. M. Howard. Field Experience in Maintenance. Human Detection and Diagnosis of System Failures: Proceedings of the NATO Symposium on Human Detection and Diagnosis of System Failures, J. Rasmussen and W. Rouse (Eds.). New York: Plenum Press, 1981, 111–133.
2] S. Fisher. E-business redefines infrastructure needs. InfoWorld, 7 January 2000. Available from .
3] J. Gray. Why Do Computers Stop and What Can Be Done About It? Symposium on Reliability in Distributed Software and Database Systems, 3–12, 1986.
4] J. Hamilton. Fault Avoidance vs. Fault Tolerance: Testing Doesn’t Scale. High Performance Transaction Systems (HPTS) Workshop, Asilomar, CA, 1999.
5] C. Perrow. Normal Accidents: Living with High-Risk Technologies. Princeton, NJ: Princeton Press, 1999.
6] B. H. Kantowitz and R. D. Sorkin. Human Factors: Understanding People-System Relationships. New York: Wiley, 1983.
7] D. R. Kuhn. Sources of Failure in the Public Switched Telephone Network. IEEE Computer 30(4), April 1997.
8] J. Menn. Prevention of Online Crashes is No Easy Fix. Los Angeles Times, 2 December 1999, C-1.
9] B. Murphy and T. Gent. Measuring System and Software Reliability using an Automated Data Collection Process. Quality and Reliability Engineering International, 11:341–353, 1995.
[Newman 00] Newman, M.W. and J.A. Landay. Sitemaps, Storyboards, and Specifications: A Sketch of Web Site Design Practice as Manifested Through Artifacts. In Proceedings of ACM Conference on Designing Interactive Systems. New York City. pp. 263-274, August 2000.
[Elliott 00] Elliott, A. and Hearst, M. How Large Should a Digital Desk Be?Qualitative Results of a Comparative Study in the Proceedings of CHI'00, Conference Companion, The Hague, Netherlands, 2000.
[Hong 01] Hong, J.I. and J.A. Landay, An Infrastructure Approach to Context-Aware Computing. Human-Computer Interaction, 2001. 16(2).
[Hearst 99] Hearst, M., User Interfaces and Visualization, in Modern Information Retrieval, Baeza-Yates and Ribeiro-Neto (Eds), Addison-Wesley Longman, 1999.
[Glaser 99] Glaser, D. and Hearst, M. Space Series: Simultaneous display of spatial and temporal data, IEEE Symposium on Information Visualization, October 1999.
[Yee 01] Yee, P., Dhamija, R., Fischer, D., Hearst, M., Animated Exploration of Graphs with Radial Layout, Submitted for publication, 2001.
[Olston 98] Olston, C., Woodruff, A., Aiken, A., Chu, M., Ercegovac, V., Lin, M., Spalding, M., Stonebraker, M. DataSplash, SIGMOD 1998, Seattle, Washington, June 1998.
[Avnur 98] Avnur, R., Hellerstein, J., Lo, B., Olston, C., Raman, B., Raman, V., Roth, T., Wylie, K. CONTROL: Continuous Output and Navigation Technology with Refinement On-Line, SIGMOD 1998, Seattle, Washington, June 1998.
CITATIONS 1.1
A. Perrig, R. Canetti, J. D. Tygar, D. Song. "Efficient Authentication and Signing of Multicast Streams over Lossy Channels". In Proceedings of the 2000 IEEE Symposium on Security and Privacy, May 2000, pages 56 - 73.
A. Perrig, R. Canetti, D. Song, J. D. Tygar. "Efficient and Secure Source Authentication for Multicast". In Proceedings of the Internet Society Network and Distributed System Security Symposium, February 2001.
CITATIONS 1.2
J. M. Kahn, R. H. Katz and K. S. J. Pister. "Mobile Networking for Smart Dust". ACM/IEEE Intl. Conf. on Mobile Computing and Networking (MobiCom 99), Seattle, WA, August 17-19, 1999.
CITATIONS 1.3
A. Perrig, D. Song, J. D. Tygar. "ELK: A New Protocol for Efficient Large-Group Key Distribution". To appear in Proceedings of the 2001 IEEE Symposium on Security and Privacy, May 2001.
CITATIONS 2.1
National Research Council Committee on Information Systems Trustworthiness. Trust in Cyberspace. National Academy Press, 1999.
J. D. Tygar, A. Whitten. "Why Isn't the Internet Secure Yet?" In ASLIB Proceedings, Volume 52, Number 3, March 2000, pages 93-97.
L. J. Camp, J. D. Tygar. "Protecting privacy while preserving access to data". In The Information Society, Volume 10, Number 1, January 1994, pages 59-71.
CITATIONS 2.2
[Pam Samuelson may provide additional citations]
CITATIONS 3
[David Wagner may provide additional citations]
CITATIONS 4
[Pam Samuelson may provide additional ciations]
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- financial internal controls for accounting
- controls for manual material handling
- advantages and disadvantages of technology at school
- wireless soundbar and speakers
- list of impacted majors at uc berkeley
- instrumentation and controls books pdf
- instrumentation and controls training course
- free instrumentation and controls training
- arts and crafts for kids at home
- wireless terms and conditions acceptance
- at t wireless terms and conditions
- wireless video and audio camera