Buildings, viewed as cyber-physical systems, become smart by deploying Building Management Systems (BMS). They should be aware about the state and environment of the building. This is achieved by developing a sensing system that senses different interesting factors of the building, called as “facets of sensing.” Depending on the application, different facets need to be sensed at various locations. Existing approaches for sensing these facets consist of deploying sensors at all the places so they can be sensed directly. But installing numerous sensors often aggravate the issues of user inconvenience, cost of installation and maintenance, and generation of e-waste. This article proposes how intelligently using the existing information can help to estimate the facets in cyber-physical systems like buildings, thereby reducing the sensors to be deployed. In this article, an optimization framework has been developed, which optimally deploys sensors in a building such that it satisfies BMS requirements with minimum number of sensors. The proposed solution is applied to real-world scenarios with cyber-physical systems. The results indicate that the proposed optimization framework is able to reduce the number of sensors by 59% and 49% when compared to the baseline and heuristic approach, respectively.

Power shortage is a serious issue especially in developing nations. Such power deficits are traditionally handled through rolling blackouts - a service area is divided into subareas, each of which is denied power during a designated time in the day. Today, smart grids provide the opportunity of avoiding complete blackouts, converting them to brownouts which allow selective provisioning of power supply to support essential loads while curtailing supply to less critical loads. We formulate the brownout based power distribution problem as aninteger linear programming (ILP)and show that solution strategies such asconventional dynamic programming (DP)impose substantial overheads. So, we propose thestreamlined DP-based priority level allocator (SDPA)which utilizes the discrete nature of power demands of each subarea and generates the overall optimal solution far quicker by focusing on a lower number of non-dominating partial DP-solutions.SDPAis found to be about 9 to 33 times faster thanDPand applicable to real-time brown-out based power distribution in moderate sized grids. However, evenSDPAmay fail to meet the real-time requirements of dynamic power imbalance mitigation in very large grids. So, a fast yet effective power adjustment approach namely,Proportionally Balanced Priority level Allocator (PBPA), has been designed and implemented. Experimental results show that although solutions provided byPBPAcould be less effective by upto 12 percent compared to optimal dynamic programming based schemes, being about 4 orders of magnitude faster, it can be deployed for real time allocations of power.

Ubiquitous sensing enabled by Wireless Sensor Network(WSN) technologies offers the ability to measure, infer and understand environmental parameters and respond to changes. In this paper, we describe our Internet of Things(IoT)-based intelligent solution designed to reduce the energy consumption in existing buildings without affecting the thermal comfort of the users. We have designed IoT nodes which can be used for sensing necessary parameters in any environment. Based on the measured values they send appropriate control commands to the appliances such as lights, fans or ACs, making the infrastructure smart, which helps us achieve our goal of reducing the energy consumption. We have deployed our IoT nodes in four classrooms in our academic building to make them smart.

The popularity of rooftop solar for homes is rapidly growing. However, accurately forecasting solar generation is critical to fully exploiting the benefits of locally generated solar energy. In this article, we present two machine-learning techniques to predict solar power from publicly available weather forecasts. We use these techniques to develop SolarCast, a cloud-based web service that automatically generates models that provide customized site-specific predictions of solar generation. SolarCast utilizes a “black box” approach that requires only (1) a site’s geographic location and (2) a minimal amount of historical generation data. Since we intend SolarCast for small rooftop deployments, it does not require detailed site- and panel-specific information, which owners may not know, but instead automatically learns these parameters for each site. We evaluate the accuracy of SolarCast’s different algorithms on two publicly available datasets, each containing over 100 rooftop deployments with a variety of attributes (e.g., climate, tilt, orientation, etc.). We show that SolarCast learns a more accurate model using much less data (∼1 month) than prior SVM-based approaches, which require ∼3 months of data. SolarCast also provides a programmatic API, enabling developers to integrate its predictions into energy efficiency applications. Finally, we present two case studies of using SolarCast to demonstrate how real-world applications can leverage its predictions. We first evaluate a “sunny” load scheduler, which schedules a dryer’s energy usage to maximally align with a home’s solar generation. We then evaluate a smart solar-powered charging station, which can optimally charge the maximum number of electric vehicles (EVs) on a given day. Our results indicate that a representative home is capable of reducing its grid demand up to 40% by providing a modest amount of flexibility (of ∼5 hours) in the dryer’s start time with opportunistic load scheduling. Further, our charging station uses SolarCast to provide EV owners the amount of energy they can expect to receive from solar energy sources.

Smart-grid applications have widely varying data needs as well as bandwidth and latency requirements. The usual approach to accumulating the available data (e.g., from Phasor Measurement Units) at a centralized site and executing all the applications there leads to large network latencies. This article proposes techniques where data packets are prioritized and disseminated based on applications’ data needs and semantics. In particular, these techniques systematically exploit in-network processing capability and filter data in the dissemination network. This filtered data is assigned higher priority compared to the raw unfiltered data—helping meet QoS requirements of various applications. Performance evaluation of our distributed techniques over a testbed designed for the Indian electric grid demonstrates that processing latency for various smart grid applications reduces by at least 50% for large PMU data sizes, compared to the traditional centralized approach.

XML and JSON have become the default formats to exchange the information for web application or within enterprises. Keyword Search over XML data has been motivated by the need to relieve users from writing difficult XQueries since otherwise users are required to know the complex XML schema. In existing XML keyword search techniques the XML nodes returned for a keyword query are the Lowest Common Ancestor (LCA) nodes for the query keywords. In this paper, we argue that the LCA based techniques still require users to be well versed with the XML schema and also the data to be able to obtain meaningful query results. To address these shortcomings, we present a novel system, Generic Keyword Search (GKS), for a given keyword query Q, instead of identifying (and returning information) only from LCA nodes, GKS returns ‘meaningful’ information from any XML node, which contains a subset of keywords in the search query Q. GKS response includes LCA nodes, if any, that would have been returned by LCA based techniques. GKS is also able to find highly relevant keywords and XML schema elements, deeper analytical insights called DI in the XML data in the context of the user query. DI enables users to navigate the XML data and to refine their queries even if they are not familiar with the data and the schema. Our experiments on real data sets show that GKS is able to return highly relevant responses to keyword queries efficiently.

Saving energy without causing discomfort and without demanding human intervention is the need of the day. It is important to develop sensor systems which not only satisfy user requirements, but also take energy consumption into consideration. In this demo, we present the sensing subsystems of a Smart Academic Environment, based upon the core concept of 'Observability' [1] which -- while satisfying user needs -- helps to reduce the number of sensors required.

Maintaining the freshness of real-time data is one of the crucial design issues in cyber-physical systems (CPS). Past studies have focused on designing update algorithms to minimize the workload imposed by a fixed set of update tasks while ensuring the temporal validity of data. In this paper, we revisit this problem in dynamic cyber-physical systems (DCPS) which may exhibit multi-modal behavior. Any solution to this problem must recognize that: (1) different update algorithms may be needed in different modes according to the workload in each mode, and (2) temporal validity of data must be maintained not only in each mode but also during the mode switch. To strike a balance between data freshness and system schedulability, we propose a utilization-based scheduling selection (UBSS) strategy. We first introduce two synchronous mode switch algorithms, named search-based switch (SBS) and adjustment-based switch (ABS) to search for the proper switch point online and execute all update tasks in the new mode synchronously. SBS checks for temporal validity at the beginning time slot of each idle period in the schedule, while ABS relaxes this restriction through schedule adjustment. To support immediate mode switch, we propose an asynchronous switch algorithm named instant switch (IS) to reduce the switch delay. IS schedules outstanding jobs from the old mode together with the jobs in the new mode using the least-available-laxity-first scheduling policy. Our experimental results demonstrate the effectiveness of these three algorithms. They also show that UBSS strategy can significantly outperform a single fixed update algorithm in terms of maintaining better data freshness while incurring only limited online switch overhead.

Classical XML keyword search based on the Lowest Common Ancestor (LCA) framework requires users to be well versed with data and semantic relationships between the query keywords to extract meaningful response, restricting its applicability. GKS (Generic Keyword Search), on the other hand, allows users to browse and navigate XML data without such constraints. GKS enables discovery of deeper insights (DI) in the XML data, found in the context of the search results. Such insights not only expose patterns hidden in the search results but also help users tune their queries, thus enabling the navigation of complex XML repositories with ease. We further show how, for a search query, different insights can be discovered from the data by varying a single parameter.

Data delivered over the internet is increasingly being used for providing dynamic and personalized user experiences. To achieve this, queries are executed over fast changing data from distributed sources. As these queries require data from multiple sources, these queries are executed at an intermediate proxy or data aggregator. Typically, users of these queries are not interested in all the data updates. Query results may be associated with an imprecision bound or threshold which can be used to limit the number of refresh messages. These queries can be categorized based on the types of results required: in an entity based query the user is just interested in knowing the ids of the data items (or entities) satisfying certain selection condition; in a value based query the user is interested in the value of some aggregation over distributed data items; and in a threshold query the user wants to know whether a Boolean condition, expressed as a threshold over an aggregation of data items, is true. We methodically present techniques for executing all these categories of continuous aggregation queries over distributed data so that the number of message exchanges between data sources, aggregators, and users is minimized. The value of individual data items can be uncertain with an associated probability. A data aggregator can execute the query either by getting all the required data or by sending appropriate sub-queries to the distributed data sources. For getting the data, the aggregator can use either push or pull based mechanisms. Each of these methods has different ways of minimizing the number of message exchanges. We present various algorithms for the same.

Although the deferrable scheduling algorithm for fixed priority transactions ( DS-FP) has been shown to provide a better performance compared with the More-Less (ML) method, there is still a lack of any comprehensive studies on the necessary and sufficient conditions for the schedulability of DS-FP. In this paper, we first analyze the necessary and sufficient schedulability conditions for DS-FP, and then propose a schedulability test algorithm for DS-FP by exploiting the fact that there always exists a repeating pattern in a DS-FP schedule. To resolve the limitation of fixed priority scheduling in DS-FP, we then extend the deferrable scheduling to a dynamic priority scheduling algorithm called DS-EDF by applying the earliest deadline first (EDF) policy to schedule update jobs. We also propose a schedulability test for DS-EDF and compare its performance with DS-FP and ML through extensive simulation experiments. The results show that the schedulability tests are effective. Although the schedulability of DS-EDF is lower than DS-FP and the repeating patterns in DS-EDF schedules are longer than those in DS-FP due to the use of dynamic priority scheduling, the performance of DS-EDF is better than both DS-FP and ML in terms of CPU utilization and impact on lower priority application transactions.

While it is essential to exploit in-network processing in wireless sensor networks in order to save bandwidth and energy, we are constrained by the limited storage available in off-the-shelf sensor devices. NAND flash memory has great potential for extending storage capacity for sensor applications. Since each sensor platform is typically equipped with limited main memory and sensor data, as well as the fact that queries are temporal, existing flash index or file systems for general portable devices are not suitable for sensor networks. We propose Time-Log Tree (TL-Tree), a novel unbalanced and cascaded structure, that takes advantage of available flash capacity while making use of the time-series property as a primary feature for optimizing both memory and energy constraints. Extensive experiments show TL-Tree's ability to utilize both flash capacity and temporal locality to support sensor data processing. Compared to other schemes, it achieves much better access and energy savings for different kinds of random and temporal range queries. In addition, TL-Tree can also be easily extended to support value-based queries. We have developed a hardware board that includes a raw 128MB NAND flash chip on MicaZ mote. We have also implemented a flash driver and the TL-Tree to demonstrate the practicality of this idea.

A substantial fraction of the energy demand of buildings comes from air-conditioners (ACs), refrigerators, etc., which do not need human interaction for their continuous operations. So long as desirable temperature levels, which we refer to as thermal comfort-bands, are maintained by such background loads, users will not be concerned about when they perform their assigned functions. i.e., when they consume the energy required to function. This paper addresses the problem of maintaining thermal comfort-bands associated with background loads under Peak energy consumption constraint. Based on our empirical observations pertaining to energy consumption profiles of thermal comfort-band maintaining ACs, a) we present a feasibility criterion for maintaining the thermal comfort-band of a given set of background loads under constraints on the peak available power and (b) we propose TCBM, a new algorithm for scheduling such background loads under peak power constraint. In addition to limiting peak power demand, the TCBM algorithm avoids undesirable switching (ON and OFF) of electrical appliances to improve efficiency of the equipment and reduce failures. Results from simulation and real-life implementation demonstrate that our algorithm is superior to the existing work on background load scheduling. We also show how TCBM can adapt to changes in ambient parameters and provide the basis for efficient demand-response systems.

Summary form only given: Smart grids have been heralded as the key enabler of cleaner, cheaper and more reliable energy. They incorporate diverse energy sources, advanced monitoring, demand-side management and the ability to “self heal”. The success of smart grids lies in the development of effective solutions for a) Demand-supply management incorporating intermittent, renewable, energy sources; b) Monitoring and sensing to understand energy generation and consumption patterns; and c) Distributed information management and control strategies. The talk will cover these topics and show how timely data analytics plays a crucial role in addressing these problems.

Continuous aggregation queries over dynamic data are used for real time decision making and timely business intelligence. In this paper we consider queries where a client wants to be notified if the ratio of two aggregates over distributed data crosses a specified threshold. Consider these scenarios: a mechanism designed to defend against distributed denial of service attacks may be triggered when the fraction of packets arriving to a subnet is more than 5% of the total packets; or a distributed store chain withdraws its discount on luxury goods when sales of luxury goods constitute more than 20% of the overall sales. The challenge in executing such ratio threshold queries (RTQs) lies in incurring the minimal amount of communication necessary for propagation of updates from data sources to the aggregator node where the client query is executed. We address this challenge by proposing schemes for converting the client ratio threshold condition into conditions on individual distributed data sources. Whenever the condition associated with a source is violated, the source pushes its data values to the aggregator, which in turn pulls data values from other sources to determine whether the client threshold condition is indeed violated. We present algorithms to minimize the number of source condition violations (i.e., the number of pushes) while ensuring that no violation of the client threshold condition is missed. Further, in case of a source condition violation, we propose efficient selective pulling algorithms for intelligently choosing additional sources whose data should be pulled by the aggregator. Using performance evaluation on synthetic and real traces of data updates we show that our algorithms result in up to an order of magnitude less number of messages compared to existing approaches in the literature.

We present the Caicos system that supports continuous infidelity bounded queries over a data stream, where each data item (of the stream) belongs to multiple categories. Caicos is made up of four primitives: Keywords, Queries, Data items, and Categories. A Category is a virtual entity consisting of all those data items that belong to it. The membership of a data item to a category is decided by evaluating a Boolean predicate (associated with each category) over the data item. Each data item and query in turn are associated with multiple keywords. Given a keyword query, unlike conventional unstructured data querying techniques that return the top-(K) documents, Caicos returns the top-(K) categories with infidelity less than the user specified infidelity bound. Caicos is designed to continuously track the evolving information present in a highly dynamic data stream. It, hence, computes the relevance of a category to the continuous keyword query using the data items occurring in the stream in the recent past (i.e., within the current "window"). To efficiently provide up-to-date answers to the continuous queries, Caicos needs to maintain the required metadata accurately. This requires addressing two subproblems: 1) Identifying the "right" metadata that needs to be updated for providing accurate results and 2) updating the metadata in an efficient manner. We show that the problem of identifying the right metadata can be further broken down into two subparts. We model the first subpart as an inequality constrained minimization problem and propose an innovative iterative algorithm for the same. The second subpart requires us to build an efficient dynamic programming-based algorithm, which helps us to find the right metadata that needs to be updated. Updating the metadata on multiple processors is a scheduling problem whose complexity is exponential in the length of the input. An approximate multiprocessor scheduling algorithm is, hence, proposed. Experimental evaluation of Caicos using real-world dynamic data shows that Caicos is able to provide fidelity close to 100 percent using 45 percent less resources than the techniques proposed in the literature. This ability of Caicos to work accurately and efficiently even in scenarios with high data arrival rates makes it suitable for data intensive application domains.

Maintaining sensor data validity while exercising timely control is crucial in real-time sensing and control systems. The goal of scheduling algorithms deployed in such systems is to maintain the validity of real-time sensor data so as to maximize the schedulability of update transactions with minimum update workload so that control actions occur on time. In this paper, we first propose a dynamic scheduling algorithm, called Deferrable Scheduling with Least Actual Laxity First (DS-LALF). DS-LALF is designed by extending the deferrable scheduling algorithm, DS-FP which is designed for fixed priority systems. We develop a schedulability test algorithm for DS-LALF based on pattern analysis and a pattern search algorithm to find the shortest and earliest pattern in the schedule. Then, based on DS-LALF, a co-scheduling algorithm called Co-LALF-to schedule update transactions and control transactions in a real-time sensing and control system together-is developed 1) to meet the deadlines of all the control transactions and 2) to maximize the quality of data (QoD) utilized by the control transactions. Co-LALFschedules the jobs in the ascending order of their actual laxities and defers the release times of update jobs as long as the corresponding sensor data are maintained within the required quality. Experimental results show that DS-LALF incurs lower update workload compared with DS-FP and ML, and its schedulability is close to DS-FP but is much better than ML and DS-EDF. The experimental results also show that Co-LALF is effective in improving the overall performance by ensuring better QoD for the real-time data while meeting the deadline constraints of all the control transactions.

With the increasing popularity of Web 2.0 streams, people become overwhelmed by the available information. This is partly countered by tagging blog posts and tweets, so that users can filter messages according to their tags. However, this is insufficient for detecting newly emerging topics that are not reflected by a single tag but are rather expressed by unusual tag combinations. This paper presents enBlogue, an approach for automatically detecting such emergent topics. EnBlogue uses a time-sliding window to compute statistics about tags and tag-pairs. These statistics are then used to identify unusual shifts in correlations, most of the time caused by real-world events. We analyze the strength of these shifts and measure the degree of unpredictability they include, used to rank tag-pairs expressing emergent topics. Additionally, this "indicator of surprise" is carried over to subsequent time points, as user interests do not abruptly vanish from one moment to the other. To avoid monitoring all tag-pairs we can also select a subset of tags, e. g., the most popular or volatile of them, to be used as seed-tags for subsequent pair-wise correlation computations. The system is fully implemented and publicly available on the Web, processing live Twitter data. We present experimental studies based on real world datasets demonstrating both the prediction quality by means of a user study and the efficiency of enBlogue.

Use of Programmable Controllers (PLC) in safety-critical applications is gaining importance as a pre-qualified development platform to reduce Verification and Validation (V &V) effort. It has been observed, in practice, that most of the safety-critical functions are fairly simple and is achieved by only a small fraction of a large safety-critical software. This motivates the development of a partitioned operating environment for PLC, so that less critical components of the large safety-critical software can be partitioned from those, which are actually performing safety-critical functions. It will facilitate less rigorous V &V for less critical modules to get necessary approval for safety-critical system from regulatory authorities. This work addresses some issues in a Partitioned-PLC development towards improved schedulability bound, yet offering simplicity in implementation.

Due to their real time nature, microblog streams are a rich source of dynamic information, for example, about emerging events . Existing techniques for discovering such events from a microblog stream in real time (such as Twitter trending topics), have several lacunae when used for discovering emerging events; extant graph based event detection techniques are not practical in microblog settings due to their complexity; and conventional techniques, which have been developed for blogs, web-pages, etc., involving the use of keyword search, are only useful for finding information about known events. Hence, in this paper, we present techniques to discover events that are unraveling in microblog message streams in real time so that such events can be reported as soon as they occur. We model the problem as discovering dense clusters in highly dynamic graphs. Despite many recent advances in graph analysis, ours is the first technique to identify dense clusters in massive and highly dynamic graphs in real time. Given the characteristics of microblog streams, in order to find clusters without missing any events, we propose and exploit a novel graph property which we call short-cycle property . Our algorithms find these clusters efficiently in spite of rapid changes to the microblog streams. Further we present a novel ranking function to identify the important events. Besides proving the correctness of our algorithms we show their practical utility by evaluating them using real world microblog data. These demonstrate our technique's ability to discover, with high precision and recall, emerging events in high intensity data streams in real time. Many recent web applications create data which can be represented as massive dynamic graphs. Our technique can be easily extended to discover, in real time, interesting patterns in such graphs.

Continuous queries are used to monitor changes to time varying data and to provide results useful for online decision making. Typically a user desires to obtain the value of some aggregation function over distributed data items, for example, to know value of portfolio for a client; or the AVG of temperatures sensed by a set of sensors. In these queries a client specifies a coherency requirement as part of the query. We present a low-cost, scalable technique to answer continuous aggregation queries using a network of aggregators of dynamic data items. In such a network of data aggregators, each data aggregator serves a set of data items at specific coherencies. Just as various fragments of a dynamic webpage are served by one or more nodes of a content distribution network, our technique involves decomposing a client query into subqueries and executing subqueries on judiciously chosen data aggregators with their individual subquery incoherency bounds. We provide a technique for getting the optimal set of subqueries with their incoherency bounds which satisfies client query's coherency requirement with least number of refresh messages sent from aggregators to the client. For estimating the number of refresh messages, we build a query cost model which can be used to estimate the number of messages required to satisfy the client specified incoherency bound. Performance results using real-world traces show that our cost-based query planning leads to queries being executed using less than one third the number of messages required by existing schemes.

Emergent topics are newly arising themes in news, blogs, or tweets, often implied by interesting and unexpected correlations of tags or entities. We present the enBlogue system for emergent topic detection. The name enBlogue reflects the analogy with emerging trends in fashion often referred to as en Vogue. EnBlogue continuously monitors Web 2.0 streams and keeps track of sudden changes in tag correlations which can be adjusted using personalization to reflect particular user interests. We demonstrate enBlogue with several real-time monitoring scenarios as well as with time lapse on archived data.

We examine the problem of tracking dynamic boundaries occurring in natural phenomena using a network of range sensors. Two main challenges of the boundary tracking problem are accurate boundary estimation from noisy observations and continuous tracking of the boundary. We propose Dynamic Boundary Tracking (DBTR), an algorithm that combines the spatial estimation and temporal estimation techniques. The regression-based spatial estimation technique determines discrete points on the boundary and estimates a confidence band around the entire boundary. In addition, a Kalman Filter-based temporal estimation technique tracks changes in the boundary and aperiodically updates the spatial estimate to meet accuracy requirements. DBTR provides a low energy solution compared to similar periodic update techniques to track boundaries without requiring prior knowledge about the dynamics. Experimental results demonstrate the effectiveness of our algorithm; estimated confidence bands indicate a loss of coverage of less than 2 to 5 percent for a variety of boundaries with different spatial characteristics.

In this paper we consider triggers over distributed data from various sources such as: ¿Notify when sale of luxury goods constitute more than 20% of the overall sales¿. In such queries client desires to be notified whenever the ratio of two aggregates, over distributed data, crosses the specified threshold. The challenge lies in being able to execute the queries with the minimal amount of communication necessary for update propagation. We address the challenge by proposing schemes for converting the client threshold condition into conditions on individual distributed data sources such that (1) violation of the client threshold occurs only if one or more source conditions are violated (zero false negative), and (2) the number of source violations when client threshold is not violated is small (minimize false positives). Using performance evaluation we show that our algorithms result in up to an order of magnitude less number of false positives compared to the approaches in the literature.

This paper examines the proposed framework for evaluating the impact of the intervention of mobile-based services on socio-economic development of Indian rural areas. Framework suitability has been studied using case study method with pilot test data. Existing literature shows multiple ways of studying mobile impact through different frameworks. The need for uniform framework is the felt need as various user-centric mobile services launched across rural markets. India becomes a field-testing ground for most of the multinational firms who want to test their innovative business models. This framework provides a testing method for socioeconomic development impact on rural areas. This study adopted socio economic criteria (SEC) used by Indian marketers as basis for sample selection. The pilot study clearly shown that field is ready to test the proposed framework.

Consider an information repository whose content is categorized. A data item (in the repository) can belong to multiple categories and new data is continuously added to the system. In this paper, we describe a system, CS*, which takes a keyword query and returns the relevant top-K categories. In contrast, traditional keyword search returns the top-K documents (i.e., data items) relevant to a user query. The need to dynamically categorize new data and also update the meta-data required for fast responses to user queries poses interesting challenges. The brute force approach of updating the meta-data by comparing each new data item with all the categories is impractical due to (i) the large cost involved in finding the categories associated with a data item and (ii) the high rate of arrival of new data items. We show that a sampling based approach which provides statistical guarantees on the reported results is also impracticable. We hence develop the CS* approach whose effectiveness results from its ability to focus on a strategically chosen subset of categories on the one hand and a subset of new data on the other. Given a query, CS* finds the top-K categories with high accuracy even in time-constrained situations. An experimental evaluation of the CS* system using real world data shows that it can easily achieve accuracy in excess of 90%, whereas other approaches demand at least 57% more resources (i.e., processing power), for providing similar results. Our experimental results also show that, contrary to expectations, if the rate of arrival of data items doubles, whereas CS* continues to provide high accuracy without a significant increase in resources, other approaches require more than double the number of resources.

Stream grids are wide-area grid computing environments that are fed by a set of stream data sources. Queries arrive at the grid from users and applications external to the system. The kind of queries considered in this work are long-running continuous (LRC) queries, that we also term as "open-world" queries. These queries are neither short-lived nor infinitely long lived. They live long enough to make the prospect of multi-query optimization meaningful. But queries may also terminate at any time, requiring re-optimization of the query plans. The queries are "open" from the grid perspective as the grid cannot control or predict: (1) arrival of a query with time, location, required data and, (2) query revocations. Query optimization in such an environment has two major challenges: (a) optimizing in a multi-query environment and (b) continuous optimization due to new query arrivals and revocations. As generating a globally optimal query plan is an intractable problem, this work explores the idea of emergent optimization, where globally optimal query plans emerge as a result of local autonomous decisions taken by the grid nodes. Drawing concepts from evolutionary game theory, grid nodes are modeled as autonomous agents that seek to maximize a self-interest function using one of a set of different strategies. Grid nodes change strategies in response to variations in query arrival and revocation patterns. Changing of strategies is also autonomously decided by each grid node based on how its strategy is faring with respect to other strategies in the grid.

Presents the introductory welcome message from the conference proceedings.

Applications that monitor functions over rapidly and unpredictably changing data, express their needs as continuous queries. Our focus is on a rich class of queries, expressed as polynomials over multiple data items. Given a set of polynomial queries at a coordinator C, and a user-specified accuracy bound (tolerable imprecision) for each query, we address the problem of assigning data accuracy bounds or filters to the source of each data item. Assigning data accuracy bounds for non-linear queries poses special challenges. Unlike linear queries, data accuracy bounds for non-linear queries depend on the current values of data items and hence need to be recomputed frequently. So, we seek an assignment such that a) if the value of each data item at C is within its data accuracy bound then the value of each query is also within its accuracy bound, b) the number of data refreshes sent by sources to C to meet the query accuracy bounds, is as low as possible, and c) the number of times the data accuracy bounds need to be recomputed is as low as possible. In this paper, we couple novel ideas with existing optimization techniques to derive such an assignment. Specifically, we make the following contributions: (i) Propose a novel technique that significantly reduces the number of times data accuracy bounds must be recomputed; (ii) Show that a small increase in the number of data refreshes can lead to a large reduction in the number of recomputations; we introduce this as a tradeoff in our approach; (iii) Give principled heuristics for addressing negative coefficient polynomial queries where no known optimization techniques can be used; we also prove that under many practically encountered conditions our heuristics can be close to optimal; and (iv) Present a detailed experimental evaluation demonstrating the efficacy of our techniques in handling large number of polynomial queries.

This paper focuses on the use of mobile sensors to estimate contours in a field. In particular, we focus on strategies to estimate the contour with minimum latency and maximum precision. We propose a novel algorithm, ACE (adaptive contour estimation), that (a) estimates and exploits information regarding the gradients in the field to move towards the contour and (b) uses a spread component to surround the contour in order to optimize latency. While it is possible for sensors to spread as they approach the contour, it is crucial to judiciously determine when and how much to spread. Spreading too early or too much may result in increasing the latency or affecting the precision. ACE dynamically makes this decision using local sensor measurements, history of measurements as well as collaboration between sensors while adapting to different types of deployment, distance from the contour and shapes of the contour. We demonstrate that ACE, in the absence of energy constraints precisely determines the contour with a lower latency than when only gradients are used for movement or when the sensors spread out right from the start of estimation. Additionally, we show that ACE significantly improves precision of contour estimation in the presence of energy constraints. We also demonstrate a proof of concept implementation on a mobile robot testbed.

Automakers are trying to make vehicles more intelligent and safe by embedding processors which can be used to implement ldquoby-wirerdquo applications for taking smart decisions on the road or assisting the driver in doing the same. Given this proliferation, there is a need to minimize the computing power required without affecting the performance and safety of the applications. The latter is especially important since these by-wire applications are distributed and real-time in nature and involve deadline bound computations on critical data gathered from the environment. These applications have stringent requirements on the freshness of data items and completion time of the tasks. Our work studies one such safety-related automotive application namely, automatic merge control (AMC) which ensures safe vehicle maneuver in the region where two or more roads intersect.As our contributions, we (i) propose two merge algorithms for amc: head of the lane (HoL) and all feasible sequences (AFS) (ii) demonstrate how DSRC-based wireless communication protocol can be leveraged for the development of AMC (iii) present a real-time approach towards designing AMC by integrating mode-change and real-time repository concepts for reducing the processing power requirements and (iv) provide a scheduling strategy to meet AMC taskspsila timing requirements. Simulations and implementation on robotic vehicular platforms demonstrate the advantages of using our approach for constructing merge-by-wire systems.

Given a sensor network and aggregate queries over the values sensed by subsets of nodes in the network, how do we ensure that high quality results are served for the maximum possible time? The issues underlying this question relate to the fidelity of query results and lifetime of the network. To maximize both, we propose a novel technique called asynchronous in-network prediction incorporating two computationally efficient methods for in-network prediction of partial aggregate values. These values are propagated via a tree whose construction is cognizant of (a) the coherency requirements associated with the queries, (b) the remaining energy at the sensors, and (c) the communication and message processing delays. Finally, we exploit in-network filtering and in-network aggregation to reduce the energy consumption of the nodes in the network. Experimental results over real world data support our claim that, for aggregate queries with associated coherency requirements, a prediction-based, asynchronous scheme provides higher quality results for a longer amount of time than a synchronous scheme. Also, whereas aggregate dissemination techniques proposed so far for sensor networks appear to have to trade-off quality of data for energy efficiency, we demonstrate that this is not always necessary.

On-line decision making often involves query processing over time-varying data which arrives in the form of data streams from distributed locations. In such environments typically, a user application is interested in the value of some function defined over the data items. For example, the traffic management system can make control decisions based on the observed traffic at major intersections; stock investors can manage their investments based on the value of their portfolios. In this paper we present a system that supports pull based data refresh and query processing techniques where such queries access data from multiple distributed sources. Key challenges in supporting such Continuous Multi-Data Incoherency Bounded Queries lie in minimizing network and source overheads, without loss of fidelity in the query responses provided to users. We address these challenges by using mathematically sound approaches based on Gradient Descent and Constraint Optimization which allow us to adapt the refresh frequencies of the dynamically changing data and adjust the quality of service provided to different users.

Continuous queries are used to monitor changes to time varying data and to provide results useful for online decision making. Typically a user desires to obtain the value of some aggregation function over distributed data items, for example, to know (a) the average of temperatures sensed by a set of sensors (b) the value of index of mid-cap stocks. In these queries a client specifies a coherency requirement as part of the query. In this paper we present a low-cost, scalable technique to answer continuous aggregation queries using a content distribution network of dynamic data items. In such a network of data aggregators, each data aggregator serves a set of data items at specific coherencies. Just as various fragments of a dynamic web-page are served by one or more nodes of a content distribution network, our technique involves decomposing a client query into sub-queries and executing sub-queries on judiciously chosen data aggregators with their individual sub-query incoherency bounds. We provide a technique of getting the optimal query plan (i.e., set of sub-queries and their chosen data aggregators) which satisfies client query.s coherency requirement with least cost, measured in terms of the number of refresh messages sent from aggregators to the client. For estimating query execution cost, we build a continuous query cost model which can be used to estimate the number of messages required to satisfy the client specified incoherency bound. Performance results using real-world traces show that our cost based query planning leads to queries being executed using less than one third the number of messages required by existing schemes.

With the explosive growth and spread of Internet, web access from mobile and rural users has become significant. But these users face problems of low bandwidth and intermittent Internet connectivity. To make the benefits of the Internet reach the common man in developing countries, accessibility and availability of the information has to be improved. aAQUA is an online multilingual, multimedia agricultural portal for disseminating information from and to rural communities. Considering resource constrained rural environments, we have designed and implemented an offline solution which provides an online experience to users in disconnected mode. Our solution is based on heterogeneous database synchronization which involves only a small synchronization payload ensuring an efficient use of available bandwidth. Offline aAQUA has been deployed in the field and systematic studies of our solution show that user experience has improved tremendously not only in disconnected mode but also in connected mode.

In mobile environments, transmitting information relevant to an event along with notification of the event has been proven to be an effective means of providing revenue enhancing services. For example, a relevant advertisement can be displayed just before event notification; for instance, a product promotion by Beckham can be shown just before the notification of a goal scored by him. Challenges in achieving real-time search and delivery of information relevant to events as they occur include: (i) predicting the next event so that the appropriate information can be kept ready; (ii) finding information relevant to the context and content of the event; (iii) searching for and bringing the potentially needed information closer to the user location; and (iv) disseminating and displaying relevant information just before the actual event is notified to the user. In this paper, we propose a real-time information delivery system based on an event's context and content. The key features of our system are: (i) representing domains with event-based scenarios using statecharts; (ii) using a novel combination of history information and state transitions to predict events; and (iii) real-time delivery of information relevant to an event by prefetching and caching information based on the events predicted to occur in the near future. To illustrate our approach, we focus on the delivery of advertisements relevant to notified events as a specific case of delivery of information relevant to the events. Using an experimental setup, we measured the effectiveness of our approach as compared to a context-unaware approach to event prediction. Experiments demonstrate that our approach has a superior performance, resulting in: (i) better prediction accuracy; (ii) the delivery of the most relevant information most of the time; and (iii) an effective cache management in mobile devices.

Modern Web-based application infrastructures are based on clustered multitiered architectures, where request distribution occurs in two sequential stages: over a cluster of Web servers and over a cluster of application servers. Much work has focused on strategies for distributing requests across a Web server cluster in order to improve the overall throughput across the cluster. The strategies applied at the application layer are the same as those at the Web server layer because it is assumed that they transfer directly. In this paper, we argue that the problem of distributing requests across an application server cluster is fundamentally different from the Web server request distribution problem due to core differences in request processing in Web and application servers. We devise an approach for distributing requests across a cluster of application servers such that the overall system throughput is enhanced, and load across the application servers is balanced.

aAQUA is an online multilingual, multimedia agricultural portal for disseminating information from and to the grassroots of the Indian agricultural community. aAQUA simultaneously addresses two major challenges in farmer outreach programs - geographic reach and customized delivery. It answers farmers queries based on the location, season, crop and other information provided by farmers. aAQUA makes use of novel database systems and information retrieval techniques like intelligent caching, offline access with intermittent synchronization, semantic-based search, etc. Agricultural content repositories (digital library), Agri-price information (Bhav Puchiye), farmer schemes and various operations support databases (aAQUA-QoS) have also emerged from the experience of aAQUA deployments. aAQUA's large scale deployment provides avenues for researchers to contribute in the areas of knowledge management, cross-lingual information retrieval, and providing accessible content for rural populations. Apart from agriculture, aAQUA can be configured and customized for expert advice over mobile networks and the Internet in education, Healthcare and other domains of interest to a developing population. This paper will showcase the utility of various component databases built into aAQUA to enhance the QoS delivered to rural populations

We examine the problem of determining boundaries occurring in natural phenomena using sensor networks. Sensor nodes remotely collect data about various points on the boundary. From this data, we estimate the boundary along with the confidence intervals using a regression relationship among sensor locations and the distances to the boundary. The confidence intervals are guaranteed to be narrower than a specified maximum width. Our distributed boundary estimation strategy uses a hierarchical structure of clusters of sensor nodes and requires 20-50% less messages as compared to a centralized scheme. The computed intervals show desired coverage of the true boundary points. Further, motivated by the practical need to estimate the boundary with a minimum number of sensors, we develop an adaptive approach for turning sensors on and off. The number of ON sensors in this scheme is only about 15% more than what a practical Oracle needs, to evaluate the boundary and confidence intervals around it. Our algorithms are also evaluated using data from real sensors on a testbed

The number of computer-controlled functions in an automobile is increasing at a rapid rate and so is the number of microprocessors implementing and controlling these functionalities. Therefore, there is a need to minimize the computing power provided without affecting the performance and safety of the applications. The latter is especially important since intelligent automotive applications deal with critical data and involve deadline bound computations on data gathered from the automobiles’ environment. These applications have stringent requirements on the freshness of data items and completion time of the tasks. Our work studies one such safety-critical application, namely Adaptive Cruise Control (ACC). We take a task+data centric approach for designing and As our contributions we have (i) identified the data and task characteristics of ACC and shown how to map them on a real-world (robotic) platform, (ii) facilitated a realtime approach towards designing ACC by the application of mode-change and real-time data repository concepts for reducing CPU capacity requirements and (iii) provided the scheduling strategies to meet the timing requirements of the tasks. Experiments demonstrate that the CPU capacity requirement can be reduced without compromising the real-time guarantees for safety-critical applications.

A real-time database is composed of real-time objects whose values remain valid only within their validity intervals. Each object in the database models a real world entity. The freshness of these objects is maintained by update transactions that sample the real world entities. The literature proposes various ways to derive a schedule of transactions that preserves the freshness (also known as absolute consistency) of these objects. But these approaches do not take care of the mutual consistency of the objects, i.e., whether together they represent a logical state of the system. We investigate the problem of checking whether, given an update transaction schedule, a periodic query would be able to read mutually consistent values. We propose solutions for both single- and multiple-query cases in the presence of non-preemptable query executions. Specifically, we first investigate formulas that give the maximal value of mutual gaps among a set of data read at a certain point in time. (A mutual gap for two object values read from the database refers to the difference between the times at which the two objects were updated.) We then propose design approaches to (1) decide the period and relative deadline of a query so that it would guarantee mutual consistency; (2) decide if a given set of queries with relative deadlines and periods can guarantee mutual consistency. Finally, we suggest ways of reducing the complexity of our proposed approaches for both harmonic periods and general cases

aAQUA is an online multilingual, multimedia Agricultural portal for disseminating information from and to rural communities. It answers farmers' queries based on the location, season, crop and other information provided by farmers. aAQUA makes use of novel database systems and information retrieval techniques like intelligent caching, offline access with intermittent synchronization, semantic-based search, etc. aAQUA's large scale deployment provides avenues for researchers to contribute in the areas of knowledge management, cross-lingual information retrieval, and providing accessible content for rural populations. Apart from agriculture, aAQUA can be configured and customized for expert advice in education, healthcare and other domains of interest to a developing population. This demonstration showcases the utility of various component DB/IR technologies built into aAQUA to enhance the QoS delivered to rural populations.

Modern application infrastructures are based on clustered, multi-tiered architectures, where request distribution occurs in two sequential stages: over a cluster of Web servers, and over a cluster of application servers. Much work has focused on strategies for distributing requests across a Web server cluster in order to improve overall throughput across the cluster. The strategies applied at the application layer are the same as those at the Web server layer, because it is assumed that they transfer directly. In this paper, we argue that the problem of distributing requests across an application server cluster is fundamentally different from the Web server request distribution problem, due to core differences in request processing in Web and application servers. We devise an approach for distributing requests across a cluster of application servers such that overall system throughput is enhanced, and load across the application servers is balanced. We compare the performance of our approach-with widely used industrial and recently proposed techniques from the literature experimentally in terms of throughput and response time performance, as well as resource utilization. Our experimental results show a significant improvement of up to nearly 80% in both throughput and response time, with a very low additional cost in terms of CPU overheads, 0.1% to 1.5%, on the Web server, and virtually no impact on CPU overheads on the application server

Lightweight computing devices are becoming ubiquitous and an increasing number of applications are being developed for these devices. Many of these applications deal with significant amounts of data and involve complex joins and aggregate operations, which necessitate a local database management system on the device. This is a challenge as these devices are constrained by limited stable storage and main memory. Hence new storage models that reduce storage costs are needed and a storage scheme should be selected based on data characteristics, nature of queries, and updates. Also, query execution plan should be chosen depending on the amount of available memory and the underlying storage scheme; memory should be optimally allocated among the database operators involved in the query. To achieve these goals, we utilize a novel storage model, ID based storage, which reduces storage costs considerably. We present an exact algorithm for allocating memory among the database operators. Because of its high complexity, we also propose a heuristic solution based on the benefit of an operator per unit memory allocation.

Consider a team of robots equipped with sensors that collaborate with one another to achieve a common goal. Sensors on robots produce periodic updates that must be transmitted to other robots and processed in real-time to enable such collaboration. Since the robots communicate with one another over an ad-hoc wireless network, we consider the problem of providing timeliness guarantees for multihop message transmissions in such a network. We derive the effective deadline and the latest start time for per-hop message transmissions from the validity intervals of the sensor data and the constraints imposed by the consuming task at the destination. Our technique schedules messages by carefully exploiting spatial channel reuse for each per-hop transmission to avoid MAC layer collisions, so that deadline misses are minimized. Extensive simulations show the effectiveness of our channel reuse-based SLF (smallest latest-start-time first) technique when compared to a simple per-hop SLF technique, especially at moderate to high channel utilization or when the probability of collisions is high.

In data publishing, the owner delegates the role of satisfy-ing user queries to a third-party publisher. As the publisher may be untrusted or susceptible to attacks, it could produce incorrect query results. In this paper, we introduce a scheme for users to verify that their query results are complete (i.e., no qualifying tuples are omitted) and authentic (i.e., all the result values originated from the owner). The scheme sup-ports range selection on key and non-key attributes, project as well as join queries on relational databases. Moreover, the proposed scheme complies with access control policies, is computationally secure, and can be implemented efficiently. 1.

Continuous queries are used to monitor changes to time varying data and to provide results useful for online decision making. Typically a user desires to obtain the value of some function over distributed data items, for example, to determine when and whether (a) the traffic entering a highway from multiple feed roads will result in congestion in a thoroughfare or (b) the value of a stock portfolio exceeds a threshold. Using the standard Web infrastructure for these applications will increase the reach of the underlying information. But, since these queries involve data from multiple sources, with sources supporting standard HTTP (pull-based) interfaces, special query processing techniques are needed. Also, these applications often have the flexibility to tolerate some incoherency, i.e., some differences between the results reported to the user and that produced from the virtual database made up of the distributed data sources.In this paper, we develop and evaluate client-pull-based techniques for refreshing data so that the results of the queries over distributed data can be correctly reported, conforming to the limited incoherency acceptable to the users.We model as well as estimate the dynamics of the data items using a probabilistic approach based on Markov Chains. Depending on the dynamics of data we adapt the data refresh times to deliver query results with the desired coherency. The commonality of data needs of multiple queries is exploited to further reduce refresh overheads. Effectiveness of our approach is demonstrated using live sources of dynamic data: the number of refreshes it requires is (a) an order of magnitude less than what we would need if every potential update is pulled from the sources, and (b) comparable to the number of messages needed by an ideal algorithm, one that knows how to optimally refresh the data from distributed data sources. Our evaluations also bring out a very practical and attractive tradeoff property of pull based approaches, e.g., a small increase in tolerable incoherency leads to a large decrease in message overheads.

Computation platforms have extended to small intelligent devices like cellphones, sensors, smartcards, PDAs, etc. As new functionalities and features are being added to these devices, increasing number of applications are being developed, many of them dealing with significant amounts of data leading to the need of embedded database support on these devices [1]. The queries go beyond simple Select-Project-Join queries but still have to be locally executed on the device [4]. Most of the modern day cellphones are being equipped with increasing memory which means more data centric applications are being developed for them. Sensor networks are also proliferating and these collect data from the environment and subject them to various queries. Most of these queries need to be executed on the device itself to reduce communication costs. Applications for PDAs execute complicated join and aggregate queries on the device resident data. Thus, there is an increasing need to facilitate the execution of complex queries locally on a variety of lightweight computing devices. However, scaling down the database footprint poses challenges since these lightweight devices come with very limited computing resources. While the amount of main memory and stable storage available in such devices is relatively small, the devices are not uniformly endowed with resources. For example, the computing capability and main memory of a cellphone differs from that of a PDA. It is essential that the available resources be utilized optimally for a database system that is developed for such devices. The already limited stable storage has to accommodate the operating system as well as the database system code, which means even less storage is available to store the data. Storage Models designed for such database systems should reduce storage cost to a minimum to be able to store more data. Limited stable storage usually precludes the creation and use of any additional index structures, hence the storage models should try to incorporate some index information in the data model itself. Ideally, index structures which can speed up query processing at no additional storage cost should be maintained. Different storage models have different storage and update costs. The selection of the best storage model for a data attribute in a relation depends on the size of the relation, selectivity and length of the attribute, frequency of updates, and the nature of queries. As far as the choice of query processing techniques is concerned, RAM is perhaps the most critical resource in these devices. Existing approaches use minimum memory algorithms for every operator. This can lead to poor performance for complex queries involving several joins and aggregates. Query execution time for complex

We consider a class of wireless sensor applications - such as mobile robotics - that impose timeliness constraints. We assume that these applications are built using commodity 802.11 wireless networks and focus on the problem of providing qualitatively-better QoS during network transmission of sensor data. Our techniques are designed to explicitly avoid network collisions and minimize the completion time to transmit a set of sensor messages. We argue that this problem is NP-complete and present three heuristics, based on edge coloring, to achieve these goals. Our simulations results show that the minimum weight color heuristic is robust to increases in communication density and yields results that are close to the optimal solution.

Often, data used in online decision making (for example, in determining how to react to changes in process behavior, traffic flow control, etc.) is dynamic in nature and hence the timeliness of the data delivered to the decision making process becomes very important. The delivered data must conform to certain time or value based application specific consistency requirements. The design of mechanisms for such data delivery is challenging given that dynamic data changes rapidly and unpredictably, the latter making it very hard to use simple prediction techniques. To address these challenges we develop mechanisms to obtain timely and consistency-preserving updates for dynamic data by pulling data from the source at strategically chosen points in time, providing quality of service (QoS) guarantees. Motivated by the need for practical system design, but using formal analytical techniques, we offer a systematic approach based on control-theoretic principles. We present a stochastic controller based on the linear quadratic Gaussian (LQG) technique as a means for deciding when to next refresh data from a source. A simple enhancement of the LQG algorithm allows us to provide QoS guarantees. Using real-world traces of real-time data we show the superior performance of our feedback-driven control-theoretic approach by comparing with a previously proposed adaptive refresh technique, a pattern matching technique, and a proportional controller with dynamically changing tuning criteria.

In this paper, we discuss various techniques for the efficient organization of a coherency preserving dynamic data dissemination network. The network consists of sources of dynamically changing data, repositories to serve this data, and clients. Given the coherency properties of the data available at various repositories, we suggest methods to intelligently choose a repository to serve a new client request. The goal is to support as many clients as possible, from the given network. Secondly, we propose strategies to decide what data should reside on the repositories, given the data coherency needs of the clients. We model the problem of selection of repositories for serving each of the clients as a linear optimization problem, and derive its objective function and constraints. In view of the complexity and infeasibility of using this solution in practical scenarios, we also suggest a heuristic solution. Experimental evaluation, using real world data, demonstrates that the fidelity achieved by clients using the heuristic algorithm is close to that achieved using linear optimization. To improve the fidelity further through better load sharing between repositories, we propose an adaptive algorithm to adjust the resource provisions of repositories according to their recent response times. It is often advantageous to reorganize the data at the repositories according to the needs of clients. To this end, we propose two strategies based on reducing the communication and computational overheads. We evaluate and compare the two strategies, analytically, using the expected response time for an update at repositories, and by simulation, using the loss of fidelity at clients, as our performance measure. The results suggest that a considerable improvement infidelity can be achieved by judicious reorganization.

No abstract available.

Typically, temporal validity of real-time data is maintained by periodic update transactions. We examine the problem of period and deadline assignment for these update transactions such that 1) these transactions can be guaranteed to complete by their deadlines and 2) the imposed CPU workload is minimized. To this end, we propose a novel approach, named the More-Less approach. By applying this approach, updates occur with a period which is more than the period obtained through traditional approaches, but with a deadline which is less than the traditional period. We show that the More-Less approach is better than existing approaches in terms of schedulability and the imposed load. We examine the issue of determining the assignment order in which transactions must be considered for period and deadline assignment so that the resulting CPU workloads can be minimized. To this end, the More-Less approach is first examined in a restricted case where the shortest validity first (SVF) order is shown to be an optimal solution. We then relax some of the restrictions and show that SVF is an approximate solution which results in CPU workloads that are close to the optimal solution. Our analysis and experiments show that the More-Less approach is an effective design approach that can provide better schedulability and reduce update transaction CPU workload while guaranteeing data validity constraints.

The focus of our work is to design and build a dynamic data distribution system that is coherence-preserving, i.e. the delivered data must preserve associated coherence requirements (the user-specified bound on tolerable imprecision) and resilient to failures. To this end, we consider a system in which a set of repositories cooperate with each other and the sources, forming a peer-to-peer network. In this system, necessary changes are pushed to the users so that they are automatically informed, about changes of interest. We present techniques 1) to determine when to push an update from one repository to another for coherence maintenance, 2) to construct an efficient dissemination tree for propagating changes from sources to cooperating repositories, and 3) to make the system resilient to failures. An experimental evaluation using real world traces of dynamically changing data demonstrates that 1) careful dissemination of updates through a network of cooperating repositories can substantially lower the cost of coherence maintenance, 2) unless designed carefully, even push-based systems experience considerable loss in fidelity due to message delays and processing costs, 3) the computational and communication cost of achieving resiliency is made to be low, and 4) surprisingly, adding resiliency actually improve fidelity even in the absence of failures.

As Internet traffic continues to grow and websites become increasingly complex, performance and scalability are major issues for websites. Websites are increasingly relying on dynamic content generation applications to provide website visitors with dynamic, interactive, and personalized experiences. However, dynamic content generation comes at a cost---each request requires computation as well as communication across multiple components.To address these issues, various dynamic content caching approaches have been proposed. Proxy-based caching approaches store content at various locations outside the site infrastructure and can improve website performance by reducing content generation delays, firewall processing delays, and bandwidth requirements. However, existing proxy-based caching approaches either (a) cache at the page level, which does not guarantee that correct pages are served and provides very limited reusability, or (b) cache at the fragment level, which is associated with several design-level and runtime scalability issues. To address these issues, several back-end caching approaches have been proposed, including query result caching and fragment level caching. While back-end approaches guarantee the correctness of results and offer the advantages of fine-grained caching, they neither address firewall delays nor reduce bandwidth requirements.In this article, we present an approach and an implementation of a dynamic proxy caching technique which combines the benefits of both proxy-based and back-end caching approaches, yet does not suffer from their above-mentioned limitations. Our dynamic proxy caching technique allows granular, proxy-based caching in highly dynamic scenarios, accessible outside the site infrastructure. We present two possible configurations for our dynamic proxy caching technique: (1) a reverse proxy configuration, and (2) a forward proxy configuration. Analysis of the performance of our approach indicates that it is capable of providing significant reductions in bandwidth. We have deployed our proposed dynamic proxy caching technique at a major financial institution. The results of this implementation indicate that our technique is capable of providing up to 3x reductions in bandwidth and response times in real-world dynamic Web applications when compared to existing caching solutions.

Multiple, independent robot platforms promise significant advantage with respect to robustness and flexibility. However, coordination between otherwise independent robots requires the exchange of information; either implicitly (as in gestural communication), or explicitly (as in message passing in a communication network.) In either case, control processes resident on all coordinated peers must participate in the collective behavior. This paper evaluates the potential to scale such a coupled control framework to many participating individuals, where scalability is evaluated in terms of the schedulability of coupled, distributed control processes. We examine how schedulability affects the scalability of a robot system, and discuss an algorithm used for off-line schedulability analysis of a distributed task model. We present a distributed coordinated search task and analyze the schedulability of the designed task structure. We are able to analyze communication delays in the system that put upper bounds on the size of the robot teams. We show that hierarchical methods can be used to overcome the scalability problem. We propose that schedulability analysis should be an integrated part of a multi-robot team design process.

Often, data used in online decision making (for example, in determining how to react to changes in process behavior, traffic flow control, etc.) is dynamic in nature and hence the timeliness of the data delivered to the decision making process becomes very important. The delivered data must conform to certain time or value based application specific inconsistency bounds. A system designed to disseminate dynamic data can exploit user-specified coherency requirements by fetching and disseminating only those changes that are of interest to users and ignoring immediate changes. But, the design of mechanisms for such data delivery is challenging given that dynamic data changes rapidly and unpredictably, the latter making it very hard to use simple prediction techniques. In this paper, we address these challenges. Specifically, we develop mechanisms to obtain timely and consistency-preserving updates for dynamic data by pulling data from the source at strategically chosen points in time. Motivated by the need for practical system design, but using formal analytical techniques, we offer a systematic approach based on control-theoretic principles. Our solution is also unique from a control-theoretic perspective due to the presence of inherent nonlinear system components and the dependence between the sampled time and sampled value. A proportional controller with dynamically changing tuning criteria is used in this work as a means of deciding when to next refresh data from the source. Using real world traces of real-time data we show the superior performance of our feedback-driven control-theoretic approach by comparing with (i) a previously proposed adaptive refresh technique and (ii) a new pattern matching technique.

Continuous queries are queries for which responses given to users must be continuously updated, as the sources of interest get updated. Such queries occur, for instance, during on-line decision making, e.g., traffic flow control, weather monitoring, etc. The problem of keeping the responses current reduces to the problem of deciding how often to visit a source to determine if and how it has been modified so that a user response can be updated accordingly. On the surface, this seems to be similar to the crawling problem since crawlers attempt to keep indexes up-to-date as users pose search queries. We show that this is not the case, both due to the inherent differences between the nature of the two problems as well as the performance metric. We also develop and evaluate a multiphase solution to the problem. Some of the important phases are: The monitoring phase, in which changes, to an initially identified set of relevant pages, are tracked. From the observed change characteristics of these pages, a probabilistic model of their change behaviour is formulated and weights are assigned to pages to denote their importance for the current queries. During the next phase, the Resource Allocation phase, based on these statistics, resources, needed to continuously probe these pages for changes, are allocated. Given these resource allocations, the scheduling phase produces an optimal achievable schedule for the probings. An experimental evaluation of our approach compared to prior approaches for crawling dynamic web pages leads to some interesting observations pertaining to the differences between the two problem of crawling—to build an index—and the problem of change tracking— to respond to continuous queries. 1.

We argue that cache consistency mechanisms designed for stand-alone proxies do not scale to the large number of proxies in a content distribution network and are not flexible enough to allow consistency guarantees to be tailored to object needs. To meet the twin challenges of scalability and flexibility, we introduce the notion of cooperative consistency along with a mechanism, called cooperative leases, to achieve it. By supporting /spl Delta/-consistency semantics and by using a single lease for multiple proxies, cooperative leases allow the notion of leases to be applied in a flexible, scalable manner to CDNs. Further, the approach employs application-level multicast to propagate server notifications to proxies in a scalable manner. We implement our approach in the Apache Web server and the Squid proxy cache and demonstrate its efficacy using a detailed experimental evaluation. Our results show a factor of 2.5 reduction in server message overhead and a 20 percent reduction in server state space overhead when compared to original leases albeit at an increased interproxy communication overhead.

With the expansion of Web sites to include business functions, a user interfaces with e-businesses through an interactive and multistep process, which is often time-consuming. For mobile users accessing the Web over digital cellular networks, the failure of the wireless link, a frequent occurrence, can result in the loss of work accomplished prior to the disruption. This work must then be repeated upon subsequent reconnection - often at significant cost in time and computation. This "disconnection-reconnection-repeat work" cycle may cause mobile clients to incur substantial monetary as well as resource (such as battery power) costs. In this paper, we propose a protocol for "recovering" a user to an appropriate recent interaction state after such a failure. The objective is to minimize the amount of work that needs to be redone upon restart after failure. Whereas classical database recovery focuses on recovering the system, i.e., all transactions, our work considers the problem of recovering a particular user interaction with the system. This recovery problem encompasses several interesting subproblems: (1) modeling user interaction in a way that is useful for recovery, (2) characterizing a user's "recovery state", (3) determining the state to which a user should be recovered, and (4) defining a recovery mechanism. We describe the user interaction with one or more Web sites using intuitive and familiar concepts from database transactions. We call this interaction an Internet transaction (iTX), distinguish this notion from extant transaction models, and develop a model for it, as well as for a user's state on a Web site. Based on the twin foundations of our iTX and state models, we finally describe an effective protocol for recovering users to valid states in Internet interactions.

Closed-loop control systems are dynamic systems subject to perturbations. One of the main concerns of the control is to design controllers to correct or limit the deviation that transient perturbations cause in the controlled system response. The smaller and shorter the deviation, the better the achieved performance. However, such controllers have been traditionally implemented using fixed timing constraints (periods and deadlines). This precludes controllers to execute dynamically, accordingly to the system dynamics, which may lead to sub-optimal implementations: although higher execution rates may be preferable when reacting to perturbations in order to minimize the response deviations, they imply wastage of resources when the system is in equilibrium. In this paper we argue and demonstrate that the responsibility of maximizing the performance of closed-loop systems relies on both the controller designer and the scheduler. We show that the dynamic optimization of the quality of the controlled system response calls for (a) flexible control task timing constraints that deliver effective control performance; flexible constraints allow us to achieve faster reaction by adaptively choosing the controller sampling rate and completion time upon transient perturbations, (b) a quality-of-control (QoC) metric; it associates with each control task timing a quantitative value expressing control performance (in terms of the closed-loop system error), and (c) new scheduling approaches; their goal is to quickly react to perturbations by dynamically scheduling tasks based on the chosen control task execution parameters to maximize the QoC. This combination offers the possibility of taking scheduling decisions based on the control information for each control task invocation, rather than using fixed timing constraints with constant periods and deadlines.

As Internet traffic continues to grow and web sites become increasingly complex, performance and scalability are major issues for web sites. Web sites are increasingly relying on dynamic content generation applications to provide web site visitors with dynamic, interactive, and personalized experiences. However, dynamic content generation comes at a cost --- each request requires computation as well as communication across multiple components.To address these issues, various dynamic content caching approaches have been proposed. Proxy-based caching approaches store content at various locations outside the site infrastructure and can improve Web site performance by reducing content generation delays, firewall processing delays, and bandwidth requirements. However, existing proxy-based caching approaches either (a) cache at the page level, which does not guarantee that correct pages are served and provides very limited reusability, or (b) cache at the fragment level, which requires the use of pre-defined page layouts. To address these issues, several back end caching approaches have been proposed, including query result caching and fragment level caching. While back end approaches guarantee the correctness of results and offer the advantages of fine-grained caching, they neither address firewall delays nor reduce bandwidth requirements.In this paper, we present an approach and an implementation of a dynamic proxy caching technique which combines the benefits of both proxy-based and back end caching approaches, yet does not suffer from their above-mentioned limitations. Our dynamic proxy caching technique allows granular, proxy-based caching where both the content and layout can be dynamic. Our analysis of the performance of our approach indicates that it is capable of providing significant reductions in bandwidth. We have also deployed our proposed dynamic proxy caching technique at a major financial institution. The results of this implementation indicate that our technique is capable of providing order-of-magnitude reductions in bandwidth and response times in real-world dynamic Web applications.

Advances in computing and communication technologies have resulted in a wide variety of networked mobile devices that access data over the Internet. We argue that servers by themselves may not be able to handle this diversity in client characteristics and intermediate proxies should be employed to handle the mismatch between server-supplied data and client capabilities. Since existing proxies are primarily designed to handle traditional wired hosts, such proxy architectures will need to be enhanced to handle mobile devices. We propose such an enhanced proxy architecture that is capable of handling the heterogeneity in client needs - specifically the variations in client bandwidth and display capabilities. Our architecture combines transcoding (which is used to match the fidelity of the requested object to client capabilities) and caching (which is used to reduce the latency for accessing popular objects). Our proxies can intelligently adapt to prevailing system conditions using learning techniques to intelligently decide whether to transcode locally or fetch an appropriate version from the server. Our experimental results indicate that such strategies produce significant improvements in client response times. Further we find that even simple learning techniques can lead to significant performance improvements.

In this paper, we argue that cache consistency mechanisms designed for stand-alone proxies do not scale to the large number of proxies in a content distribution network and are not flexible enough to allow consistency guarantees to be tailored to object needs. To meet the twin challenges of scalability and flexibility, we introduce the notion of cooperative consistency along with a mechanism, called cooperative leases, to achieve it. By supporting Δ-consistency semantics and by using a single lease for multiple proxies, cooperative leases allows the notion of leases to be applied in a flexible, scalable manner to CDNs. Further, the approach employs application-level multicast to propagate server notifications to proxies in a scalable manner. We implement our approach in the Apache web server and the Squid proxy cache and demonstrate its efficacy using a detailed experimental evaluation. Our results show a factor of 2.5 reduction in server message overhead and a 20% reduction in server state space overhead when compared to original leases albeit at an increased inter-proxy communication overhead.

In this paper, we examine the potential benefits of Web proxy caches in improving the effective capacity of servers and networks. Since networks and servers are typically provisioned based on a high percentile of the load, we focus on the effects of proxy caching on the tail of the load distribution. We find that, unlike their substantial impact on the average load, proxies have a diminished impact on the tail of the load distribution. The exact reduction in the tail and the corresponding capacity savings depend on the nature of the workload and the percentile of the load distribution chosen for provisioning networks and servers-the higher the percentile, the smaller the savings. For workloads considered in this study, compared with over a 50% reduction in the average load, the savings in network and server capacity was only 20%-35% for the 99th percentile of the load distribution. We also find that while proxies can be somewhat useful in smoothing out some of the burstiness in Web workloads; the resulting workload continues, however, to exhibit substantial burstiness and a heavy-tailed nature. We identify one-time requests for large objects to be the limiting factor that diminishes the impact of proxies on the tail of load distribution. We conclude that, while proxies are immensely useful to users due to the reduction in the average response time, they are less effective in improving the capacities of networks and servers.

An important issue in the dissemination of time-varying Web data such as sports scores and stock prices is the maintenance of temporal coherency. In the case of servers adhering to the HTTP protocol, clients need to frequently pull the data based on the dynamics of the data and a user's coherency requirements. In contrast, servers that possess push capability maintain state information pertaining to clients and push only those changes that are of interest to a user. These two canonical techniques have complementary properties with respect to the level of temporal coherency maintained, communication overheads, state space overheads, and loss of coherency due to (server) failures. In this paper, we show how to combine push and pull-based techniques to achieve the best features of both approaches. Our combined technique tailors the dissemination of data from servers to clients based on 1) the capabilities and load at servers and proxies and 2) clients' coherency requirements. Our experimental results demonstrate that such adaptive data dissemination is essential to meet diverse temporal coherency requirements, to be resilient to failures, and for the efficient and scalable utilization of server and network resources.

Mobile systems increasingly are being used for production-grade data-centered applications which require system support for transactional properties. For mobile applications, transactions can hide, to some extent, the infrastructure intrinsic to mobile systems, such as disconnection from the network, dozing, and storage limitations. In this paper, we introduce a framework to understand, specify, and reason about recovery support for transactional functionality, based on the notion of guarantees (promises one subsystem makes to another) and protocols (prescriptions for correct behavior). We apply our framework to a simple mobile system scenario, yielding an abstract specification that exposes the role of each component in achieving specific transactional semantics support, such as the redo-ability of committed updates that might be lost due to a failure; it also reveals unstated assumptions necessary for the correctness of recovery support. We also show how to reason about alternative ways of obtaining the desired transactional support and the requirements on the components to support recovery and transactions.

On-line analytical processing (OLAP) refers to the technologies that allow users to efficiently retrieve data from the data warehouse for decision-support purposes. Data warehouses tend to be extremely large, it is quite possible for a data warehouse to be hundreds of gigabytes to terabytes in size (Chauduri and Dayal, 1997). Queries tend to be complex and ad hoc, often requiring computationally expensive operations such as joins and aggregation. Given this, we are interested in developing strategies for improving query processing in data warehouses by exploring the applicability of parallel processing techniques. In particular, we exploit the natural partitionability of a star schema and render it even more efficient by applying DataIndexes-a storage structure that serves both as an index as well as data and lends itself naturally to vertical partitioning of the data. DataIndexes are derived from the various special purpose access mechanisms currently supported in commercial OLAP products. Specifically, we propose a declustering strategy which incorporates both task and data partitioning and present the Parallel Star Join (PSJ) Algorithm, which provides a means to perform a star join in parallel using efficient operations involving only rowsets and projection columns. We compare the performance of the PSJ Algorithm with two parallel query processing strategies. The first is a parallel join strategy utilizing the Bitmap Join Index (BJI), arguably the state-of-the-art OLAP join structure in use today. For the second strategy we choose a well-known parallel join algorithm, namely the pipelined hash algorithm. To assist in the performance comparison, we first develop a cost model of the disk access and transmission costs for all three approaches.

In this paper, issues involved in the design of a real-time database which maintains data temporal consistency are discussed. The concept of data-deadline is introduced and time cognizant transaction scheduling policies are proposed. Informally, data-deadline is a deadline assigned to a transaction due to the temporal constraints of the data accessed by the transaction. Further, two time cognizant forced wait policies which improve performance significantly by forcing a transaction to delay further execution until a new version of sensor data becomes available are proposed. A way to exploit temporal data similarity to improve performance is also proposed. Finally, these policies are evaluated through detailed simulation experiments. The simulation results show that taking advantage of temporal data semantics in transaction scheduling can significantly improve the performance of user transactions in realtime database systems. In particular, it is demonstrated that under the forced wait policy, the performance can be improved significantly. Further improvements result by exploiting data similarity.

Existing Web proxy caches employ cache consistency mechanisms to ensure that locally cached data is consistent with that at the server. We argue that techniques for maintaining consistency of individual objects are not sufficient; a proxy should employ additional mechanisms to ensure that related Web objects are mutually consistent with one another. We formally define the notion of mutual consistency and the semantics provided by a mutual consistency mechanism to end users. We then present techniques for maintaining mutual consistency in the temporal and value domains. A novel aspect of our techniques is that they can adapt to the variations in the rate of change of the source data, resulting in judicious use of proxy and network resources. We evaluate our approaches using real-world Web traces and show that: (i) careful tuning can result in substantial savings in the network overhead incurred without any substantial loss in fidelity, of the consistency guarantees, and (ii) the incremental cost of providing mutual consistency guarantees over mechanisms to provide individual consistency guarantees is small.

In this paper, we first identify the potential violations of control assumptions inherent in standard real-time scheduling approaches (because of the presence of jitters) that causes, degradation in control performance and may even lead to instability. We then develop practical approaches founded on control theory to deal with these violations. Our approach is based on the notion of compensations wherein controller parameters are adjusted at runtime for the presence of jitters. Through time and memory overhead analysis, and by elaborating on the implementation details, we characterize when offline and on-line compensations are feasible. Our experimental results confirm that our approach does compensate for the degraded control performance when EDF and FPS algorithms are used for scheduling the control tasks. Our compensation approach provides us another advantage that leads to better schedulability of control tasks. This derives from the potential to derive more flexible timing constraints, beyond periods and deadlines necessary to apply EDF and FPS. Overall, our approach provides guarantees offline that the control system will be stable at runtime-if temporal requirements are met at runtime-even when actual execution patterns are not known beforehand. With our approach, we can address the problems due to (a) sampling jitters, (b) varying delays between sampling and actuation, or (c) both-not addressable using traditional EDF and FPS based scheduling, or by previous real-time and control integration approaches.

Web sites allow the collection of vast amounts of navigational data -- clickstreams of user traversals through the site. These massive data stores offer the tantalizing possibility of uncovering interesting patterns within the dataset. For e-businesses, always looking for an edge in the hyper-competitive online marketplace, this possibility is of particular interest. Of significant particular interest to e-businesses is the discovery of Critical Edge Sequences (CES), which denote frequently traversed subpaths in the catalog. CESs can be used to improve site performance and site management, increase the effectiveness of advertising on the site, and gather additional knowledge of customer interest patterns on the site.Using traditional graph-based and web mining strategies to find CESs could turn out to be expensive in both space and time. In this paper, we propose a method to compute the most popular paths bewteen node pairs in a catalog, which are then used to discover CESs. Our method is both space-efficient and accurate, providing a vast reduction in the storage requirement with a minimum impact on accuracy. This algorithm, executed off-line in batch mode, is also practical with respect to running time. As a variant of single-source shortest-path, it runs in log linear time.

No abstract available.

No abstract available.

Materialized views have been found to be very effective at speeding up queries, and are increasingly being supported by commercial databases and data warehouse systems. However, whereas the amount of data entering a warehouse and the number of materialized views are rapidly increasing, the time window available for maintaining materialized views is shrinking. These trends necessitate efficient techniques for the maintenance of materialized views.

Article Share on Adaptive push-pull: disseminating dynamic web data Authors: Pavan Deolasee Department of Computer Science and Engineering., Indian Institute of Technology, Bombay, Mumbai, India 400076 Department of Computer Science and Engineering., Indian Institute of Technology, Bombay, Mumbai, India 400076View Profile , Amol Katkar Department of Computer Science and Engineering., Indian Institute of Technology Bombay, Mumbai, India 400076 Department of Computer Science and Engineering., Indian Institute of Technology Bombay, Mumbai, India 400076View Profile , Ankur Panchbudhe Department of Computer Science and Engineering., Indian Institute of Technology Bombay, Mumbai, India 400076 Department of Computer Science and Engineering., Indian Institute of Technology Bombay, Mumbai, India 400076View Profile , Krithi Ramamritham Department of Computer Science, University of Massachusetts, Amherst, MA Department of Computer Science, University of Massachusetts, Amherst, MAView Profile , Prashant Shenoy Department of Computer Science, University of Massachusetts, Amherst, MA Department of Computer Science, University of Massachusetts, Amherst, MAView Profile Authors Info & Claims WWW '01: Proceedings of the 10th international conference on World Wide WebMay 2001Pages 265–274https://doi.org/10.1145/371920.372066Published:01 April 2001Publication History 88citation1,366DownloadsMetricsTotal Citations88Total Downloads1,366Last 12 Months25Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Presents CReMeS (CORBA-compliant Reflective Memory-based Service), a CORBA-compliant design and implementation of a new real-time (RT) communication service. The CReMeS architecture is based on MidART's RT-CRM (Real-Time Channel-based Reflective Memory), which supports the separation of QoS specification between data producers and consumers and employs a user-level scheduling scheme for communicating RT tasks. Although RT-CRM provides a predictable and scalable asynchronous communication infrastructure for applications, it is not a standard middleware. To make its service widely available, we developed CReMeS by adapting RT-CRM for CORBA environments. As a result, CReMeS provides efficient, predictable and scalable communication between information producers and consumers. Since CReMeS provides a CORBA interface to applications and demands no changes to the ORB layer and the language mapping layer, it can run on non-RT off-the-shelf ORBs and enables applications on these ORBs to have scalable and end-to-end predictable asynchronous communication facility. In addition, an application designer can select whether to use an out-of-band channel or the ORB GIOP (General Inter-ORB Protocol)/IIOP (Internet Inter-ORB Protocol) for data communication. This permits a tradeoff between performance, predictability and reliability. Our architecture achieves better performance and predictability than a RT implementation of the CORBA Event Service when the out-of-band channel is employed for data communication; it delivers better predictability with comparable performance when the ORB GIOP/IIOP is used.

One-phase commit protocols substantially reduce the overheads of transaction commit processing, making them attractive for incorporation in distributed real-time databases. A major obstacle, however is that these protocols significantly increase the occurrence of priority inversions. This arises from the cohorts of each distributed transaction being in a prepared state for extended periods of time, during which their data locks cannot be pre-empted. We present a new one-phase real-time commit protocol, called PEP (short for PROMPT-EP, where PROMPT = "Permits Reading Of Modified Prepared-data for Timeliness", which is a real-time commit protocol, and EP = "Early Prepare", which is a one-phase commit protocol). PEP addresses the above-mentioned problem by suitably utilizing our previously proposed prepared data-borrowing technique. A simulation-based evaluation of PEP for real-time applications with firm deadlines demonstrates that, for a variety of environments, it substantially reduces the number of killed transactions as compared to its multi-phase counterparts. In fact, PEP often provides better performance than even an equivalent centralized system.

Online personalization is of great interest to e-companies. Virtually all personalization technologies are based on the idea of storing as much historical customer session data as possible, and then querying the data store as customers navigate through a web site. The holy grail of on-line personalization is an environment where fine-grained, detailed historical session data can be queried based on current online navigation patterns to formulate real-time responses. Unfortunately, as more consumers become e-shoppers, the user load and the amount of historical data continue to increase, causing scalability-related problems for almost all current personalization technologies. This paper chronicles the development of a real-time interaction management engine through the integration of historical data and on-line visitation patterns of e-commerce site visitors. This paper describes the scientific underpinnings of the system, as well as the architecture and a performance evaluation....

In this paper, we examine the potential benefits of web proxy caches in improving the effective capacity of servers and networks. Since networks and servers are typically provisioned based on a high percentile of the load, we focus on the effects of proxy caching on the tail of the load distribution. We find that, unlike their substantial impact on the average load, proxies have a diminished impact on the tail of the load distribution. The exact reduction in the tail and the corresponding capacity savings depend on the percentile of the load distribution chosen for provisioning networks and servers—the higher the percentile, the smaller the savings. In particular, compared to over a 50% reduction in the average load, the savings in network and server capacity is only 20-35% for the 99th percentile of the load distribution. We also find that while proxies can be somewhat useful in smoothing out some of the burstiness in web workloads; the resulting workload continues, however, to exhibit substantial burstiness and a heavy-tailed nature. We identify large objects with poor locality to be the limiting factor that diminishes the impact of proxies on the tail of load distribution. We conclude that, while proxies are immensely useful to users due to the reduction in the average response time, they are less effective in improving the capacities of networks and servers.

We investigate the performance implications of providing transaction atomicity for firm-deadline real-time applications, operating on distributed data. Using a detailed simulation model, the real-time performance of a representative set of classical transaction commit protocols is evaluated. The experimental results show that data distribution has a significant influence on real-time performance and that the choice of commit protocol clearly affects the magnitude of this influence. We also propose and evaluate a new commit protocol, PROMPT (Permits Reading Of Modified Prepared-data for Timeliness), that is specifically designed for the real-time domain. PROMPT allows transactions to "optimistically" borrow, in a controlled manner, the updated data of transactions currently in their commit phase. This controlled borrowing reduces the data inaccessibility and the priority inversion that is inherent in distributed real-time commit processing. A simulation-based evaluation shows PROMPT to be highly successful, as compared to the classical commit protocols, in minimizing the number of missed transaction deadlines. In fact, its performance is close to the best on-line performance that could be achieved using the optimistic lending approach. Further, it is easy to implement and incorporate in current database system software. Finally, PROMPT is compared against an alternative priority inheritance-based approach to addressing priority inversion during commit processing. The results indicate that priority inheritance does not provide tangible performance benefits.

The proliferation of new data-intensive applications in asymmetric communication environments has led to an increasing interest in the development of push-based techniques, in which the information is broadcast to a large population of clients in order to achieve the most efficient use of the limited server and communication resources. Nevertheless, none of the existing schemes integrates all the characteristics needed to perform effectively in a real-world, dynamic time-critical asymmetric communication environment. In this paper we present and evaluate an adaptive data dissemination model and the associated online scheduling algorithms. These improve the functionality and performance of current broadcast models, maximizing the total number of satisfied users in asymmetric communication environments with dynamic client profiles and time requirements (e.g., mobile systems).

Typically, temporal validity of real-time data is maintained by periodic update transactions. In this paper we examine the problem of period and deadline assignment for these update transactions such that (1) these transactions can be guaranteed to complete by their deadlines and (2) the imposed workload is minimized. To this end, we propose a novel approach, named More-Less principle. By applying this principle, updates occur with a period which is more than the period obtained through traditional approaches but with a deadline which is less than the traditional period. We show that the More-Less principle is better than existing approaches in terms of schedulability and the imposed load. We examine the issue of determining the assignment order in which transactions must be considered for period and deadline assignment so that the resulting workloads can be minimized. To this end, the More-Less principle is first examined in a restricted case where the Shortest Validity First (SVF) order is shown to be an optimal solution. We then relax some of the restrictions and show that SVF is an approximate solution which results in workloads that are close to the optimal solution. Our analysis and experiments show that the More-Less principle is an effective design principle that can provide better schedulability and reduce update transaction workload while guaranteeing data validity constraints.

A crucial consideration in environments where data is broadcast to clients is the low bandwidth available for clients to communicate with servers. Advanced applications in such environments do need to read data that is mutually consistent as well as current. However, given the asymmetric communication capabilities and the needs of clients in mobile environments, traditional serializability-based approaches are too restrictive, unnecessary, and impractical. We thus propose the use of a weaker correctness criterion called update consistency and outline mechanisms based on this criterion that ensure (1) the mutual consistency of data maintained by the server and read by clients, and (2) the currency of data read by clients. Using these mechanisms, clients can obtain data that is current and mutually consistent “off the air”, i.e., without contacting the server to, say, obtain locks. Experimental results show a substantial reduction in response times as compared to existing (serializability-based) approaches. A further attractive feature of the approach is that if caching is possible at a client, weaker forms of currency can be obtained while still satisfying the mutual consistency of data.

VER time, the discipline of computing systems has evolved and expanded in a multifaceted manner to cover many distinct and (sometimes) disparate streams. These encompass themes in system architecture, performance modeling, real-time, and fault tolerance, among several others. Many of these areas (fortunately or unfortunately?) have evolved separately and become established as discrete fields, although the overall design of computers and applications still, and inherently, involves their synergistic association. To open a topic of debate: This synergism is often lacking or, if present, not particularly acknowledged as coming from the pertinent area and, at times, reinvented. Among the offshoots of the broad discipline of computing systems, fault tolerance and real-time, in particular, are increasingly being viewed as areas with potential for synergy. The concept of fault tolerance is expanding in scope to address the broader area of dependability: reliability, performability, availability, safety, the consideration of temporal properties in defining “correct” services towards the goal of reliably delivering desired services at specified times. Similarly, the real-time community is increasingly incorporating notions of dependability within its definitions of provision of timely services. Realistically, the entire range of current system designs is reaching a complexity level that necessitates joint consideration of fault tolerance and real-time features, regardless of which gets primary emphasis. Examples abound: communication networks, transaction processing, and flight, industrial, medical, or automotive control all clearly require consideration of both dependability and timeliness. It is of interest to note that the two communities tackle largely overlapping sets of problems which can be broadly stated as: “assured delivery of correctly executed services” and constraints, i.e., “resource management, guarantees, and efficiency.” Interestingly, the fields of fault tolerance and real-time address these problems with different perspectives and aim at optimizing different sets of objectives within the same problems. For example, the fault tolerance emphasis involves reliability of the mechanisms providing for delivery of correctly executed services; the real-time community puts the emphasis on guaranteeing delivery of services in a timely manner. Similarly, resource management issues are addressed as redundancy management issues, versus issues of efficient use of uniprocessor/multiprocessors for task allocation from the realtime systems perspective. It is actually quite a long list of issues that get addressed differently by the fault-tolerant and real-time viewpoints. Moreover, the two fields rely on very similar fundamentals and techniques from engineering, mathematics, and theory. Indeed, at times this fosters a very healthy development of ideas and solutions from varied perspectives; often enough, it involves reinventing the wheel. Both the disciplines of fault tolerance and real-time have matured, with their individual seminal contributions, development of terminology, and conceptual basis. Perhaps this maturity now fosters a better chance in understanding complementary issues which have, over time, been developed with different perspectives, emphasis, and presentation. However, as they do tackle the common problem of “assured delivery of correctly executed services,” it is the intent of this special issue to address and encourage the integration of these two (perceived?) diverse areas toward a cohesive formulation of dependable real-time service and systems. In many ways, the notion and popularity of the term “Quality of Service (QoS)” already represents the juxtaposition of many fault-tolerant and real-time services. This special issue on dependable real-time systems endeavors to develop the area of systems with composite attributes of real-time and dependability within a common framework. The thrust is on understanding system models, identifying issues and concepts used across both communities for design and analysis, and elucidating the context and relevance of concepts synergistically across the areas of dependability and real time. The flavor of this special issue is both theoretical and experimental in scope to expand the underlying principles of the areas of both dependability and real-time. We paraphrase some topics from the call for papers which we believe depict some of the areas where there is significant work needed to link the fields of dependability and real-time. These include (in part):

The spring scheduling coprocessor is a novel very large scale integration (VLSI) accelerator for multiprocessor real-time systems. The coprocessor can be used for static as well as online scheduling. Many different policies and their combinations can be used (e.g., earliest deadline first, highest value first, or resource-oriented policies such as earliest available time first). In this paper, we describe a coprocessor architecture, a CMOS implementation, an implementation of the host/coprocessor interface and a study of the overall performance improvement. We show that the current VLSI chip speeds up the main portion of the scheduling operation by over three orders of magnitude. We also present an overall system improvement analysis by accounting for the operating system overheads and identify the next set of bottlenecks to improve. The scheduling coprocessor includes several novel VLSI features. It is implemented as a parallel architecture for scheduling that is parameterized for different numbers of tasks, numbers of resources, and internal wordlengths. The architecture was implemented using a single-phase clocking style in several novel ways. The 328 000 transistor custom 2-/spl mu/m VLSI accelerator running with a 100-MHz clock, combined with careful hardware/software co-design results in a considerable performance improvement, thus removing a major bottleneck in real-time systems.

Workflow management systems (WFMSs) coordinate the execution of applications distributed over networks. In WFMSs, data inconsistencies can arise due to: the interaction between steps of concurrent threads within a workflow (intra-workflow coordination); the interaction between steps of concurrent workflows (inter-workflow coordination); and the presence of failures. Since these problems have not received adequate attention, this paper focuses on developing the necessary concepts and infrastructure to handle them. First, to deal with inter- and intra-workflow coordination requirements we have identified a set of high level building blocks. Secondly, to handle failures we propose a novel and pragmatic approach called opportunistic compensation and re-execution that allows a workflow designer to customize workflow recovery from correctness as well as performance perspectives. Thirdly based on these concepts we have designed a workflow specification language that expresses new requirements for workflow executions and implemented a run-time system for managing workflow executions while satisfying the new requirements. These ideas are geared towards improving the modeling and correctness properties offered by WFMSs and making them more robust and flexible.

In electronic commerce applications such as stock trading, there is a need to consult sources available on the web for informed decision making. Because information such as stock prices keep changing, the web sources must be queried continually to maintain temporal coherency of the collected data, thereby avoiding decisions based on stale information. However because network infrastructure has failed to keep pace with ever growing web traffic, the frequency of contacting web servers must be kept to a minimum. This paper presents adaptive approaches for the maintenance of temporal coherency of data gathered from web sources. Specifically, it introduces mechanisms to obtain timely updates from web sources, based on the dynamics of the data and the users' need for temporal accuracy by judiciously, combining push and pull technologies and by using virtual data warehouses to disseminate data within acceptable tolerance to clients. A virtual warehouse maintains temporal coherence, within the tolerance specified, by tracking the amount of change in the web sources, pulling the data from the sources at opportune times, and pushing them to the clients according to their temporal coherence requirements. The performance of these mechanisms is studied using real stock price traces. One of the attractive features of these mechanisms is that it does not require changes to either the web servers or to the HTTP protocol.

Transaction delegation, as introduced in ACTA, allows a transaction to transfer responsibility for the operations that it has performed on an object to another transaction. Delegation can be used to broaden the visibility of the delegatee, and to tailor the recovery properties of a transaction model. Delegation has been shown to be useful in synthesizing advanced transaction models. With an efficient implementation of delegation it becomes practicable to realize various advanced transaction models whose requirements are specified at a high level language instead of the current expensive practice of building them from scratch. The authors identify the issues in efficiently supporting delegation and hence advanced transaction models, and illustrate this with our solution in ARIES, an industrial-quality system that uses UNDO/REDO recovery. Since delegation is tantamount to rewriting history, a naive implementation can entail frequent, costly log accesses, and can result in complicated recovery protocols. The algorithm achieves the effect of rewriting history without rewriting the log, resulting in an implementation that realizes the semantics of delegation at minimal additional overhead and incurs no overhead when delegation is not used. The work indicates that it is feasible to build efficient and robust, general-purpose machinery for advanced transaction models. It is also a step towards making recovery a first-class concept within advanced transaction models.

Static redundancy allocation is inappropriate in hard real-time systems that operate in variable and dynamic environments, (e.g., radar tracking, avionics). Adaptive fault tolerance (AFT) can assure adequate reliability of critical modules, under temporal and resource constraints, by allocating just as much redundancy to less critical modules as can be afforded thus gracefully reducing their resource requirement. We propose a mechanism for supporting adaptive fault tolerance in a real-time system. Adaptation is achieved by choosing a suitable redundancy strategy for a dynamically arriving computation to assure required reliability and to maximize the potential for fault tolerance while ensuring that deadlines are met. The proposed approach is evaluated using a real-life workload simulating radar tracking software in AWACS early warning aircraft. The results demonstrate that our technique outperforms static fault tolerance strategies in terms of tasks meeting their timing constraints. Further, we show that the gain in this timing-centric performance metric does not reduce the fault tolerance of the executing task below a predefined minimum level. Overall, the evaluation indicates that the proposed ideas result in a system that dynamically provides QoS guarantees along the fault-tolerance dimension.

In (Gupta et al., 1996), we proposed a new commit protocol, OPT, specially designed for use in distributed firm-deadline real-time database systems. OPT allows transactions to optimistically borrow uncommitted prepared data in a controlled manner. This controlled borrowing reduces the data inaccessibility and the priority inversion that is inherent in real-time commit processing. Experimental evaluations showed the new OPT protocol to be highly successful, as compared to the classical distributed commit protocols, in minimizing the number of missed transaction deadlines. In this paper, we extend and improve upon this prior work in the following ways. First, we consider parallel distributed transactions whereas the previous study was restricted to sequential transactions. Second, we evaluate the extent to which OPT's real-time performance is adversely affected by those cases where its optimism turns out to be misplaced. This is achieved by comparing OPT's performance with that of Shadow-OPT, a protocol that augments OPT with the shadow transaction approach and ensures that the right decision about access to uncommitted data is always eventually made. In all of our experiments, which considered a wide range of workloads and system configurations, the difference between OPT and Shadow-OPT never exceeded ten percent. Moreover, the difference was reduced to less than two percent when OPT was enhanced with a simple healthy lenders heuristic. Finally, we compare the performance of OPT to that of an alternative priority, inheritance-based approach to addressing priority inversion during commit processing.

A significant body of literature is available on distributed transaction commit protocols. Surprisingly, however, the relative merits of these protocols have not been studied with respect to their quantitative impact on transaction processing performance. In this paper, using a detailed simulation model of a distributed database system, we profile the transaction throughput performance of a representative set of commit protocols. A new commit protocol, OPT, that allows transactions to “optimistically” borrow uncommitted data in a controlled manner is also proposed and evaluated. The new protocol is easy to implement and incorporate in current systems, and can coexist with most other optimizations proposed earlier. For example, OPT can be combined with current industry standard protocols such as Presumed Commit and Presumed Abort.

We investigate the performance implications of supporting transaction atomicity in a distributed real-time database system. Using a detailed simulation model of a firm-deadline distributed real-time database system, we profile the real-time performance of a representative set of commit protocols. A new commit protocol that is designed for the real-time domain and allows transactions to "optimistically" read uncommitted data is also proposed and evaluated. The experimental results show that data distribution has a significant influence on the real-time performance and that the choice of commit protocol clearly affects the magnitude of this influence. Among the protocols evaluated, the new optimistic commit protocol provides the best performance for a variety of workloads and system configurations.

An integrated platform which is capable of meeting the requirements of both traditional real-time control processing and multimedia processing has enormous potential for accommodating various kinds of new applications. However, except for the simplest of situations, few, if any, research or commercial systems successfully provide architectural and OS mechanisms which can efficiently support both hard real-time computation and multimedia soft real-time computation. The authors propose a multimedia server execution on multiprocessor real-time operating systems to provide different classes of guarantee to support both types of processing. The multimedia server supports multiple periodic multimedia streams with a capability for graceful QoS degradation during system overload. They (i) develop several multimedia server scheduling algorithms, (ii) evaluate the performance of these algorithms, and (iii) discuss realistic system implementation issues on the SGI IRIX/REACT/PRO operating system.

In this paper, issues involved in the design of a real-time database which maintains data temporal consistency are discussed. The concept of data-deadline is introduced and time cognizant non-waiting transaction scheduling policies are proposed. Further, two time cognizant forced wait policies which improve performance significantly by forcing a transaction to delay further execution until a new version of sensor data becomes available are proposed. A way to exploit temporal data similarity to improve performance is also proposed. Finally, these policies are evaluated through detailed simulation experiments. The simulation results show that taking advantage of temporal data semantics in transaction scheduling can significantly improve the performance of user transactions in real-time database systems. In particular, it is demonstrated that under the forced wait policy, the performance can be improved significantly. Further improvements result by exploiting data similarity.

To properly handle concurrent accesses to documents by updates and queries in information retrieval (IR) systems, efforts are on to integrate IR features with database management system (DBMS) features. However, initial research has revealed that DBMS features optimized for traditional databases, display degraded performance while handling text databases. Since efficiency is critical in IR systems, infrastructural extensions are necessary for several DBMS features, transaction support being one of them. This paper focuses on developing efficient transaction support for IR systems where updates and queries arrive dynamically, by exploiting the data characteristics of the indexes as well as of the queries and updates that access the indexes. Results of performance tests on a prototype system demonstrate the superior performance of our algorithms. Keywords: Concurrency Control, Recovery, Transaction Management, Index Management, Information Retrieval, Optimization, Performance, Digital L...

A real-time database system is a database system in which transactions have explicit timing constraints such as deadlines. Apart from satisfying the database consistency constraints, transaction executions must also satisfy these timing constraints. The goal of transaction and query processing in real-time databases is to maximise the number of successful transactions in the system. This paper reports on the design, development and performance evaluation of RT-Genesis, a real-time database management system resulting from modifying an existing commercial DBMS, Genesis. RT-Genesis is a relational database management system that accommodates SQL queries and transactions having time constraints. It features time-cognizant algorithms for scheduling, concurrency control and buffer management. The system has been tested and the performance of the different algorithms compared in isolation as well as in combination with different classes of SQL workloads. In addition, a two-phased approach to transaction execution has also been implemented with the goal of exploiting access invariance to improve predictability. This work demonstrates the feasibility of converting non-real-time DBMSs into real-time DBMSs for firm deadline transactions. Besides reporting on how this was achieved and on the performance of the incorporated algorithms, lessons learned from this experience are also discussed.

Significant performance advantages can be gained by implementing a database system on a cache-coherent shared memory multiprocessor. However, problems arise when failures occur. A single node (where a node refers to a processor/memory pair) crash may require a reboot of the entire shared memory system. Fortunately, shared memory multiprocessors that isolate individual node failures are currently being developed. Even with these, because of the side effects of the cache coherency protocol, a transaction executing strictly on a single node may become dependent on the validity of the memory of many nodes thereby inducing unnecessary transaction aborts. This happens when database objects, such as records, and database support structures, such as index structures and shared lock tables, are stored in shared memory. In this paper, we propose crash recovery protocols for shared memory database systems which avoid the unnecessary transaction aborts induced by the failure dependencies that occu...

Many real-time systems have both performance requirements and reliability requirements. Performance is usually measured in terms of the value in completing tasks on time. Reliability is evaluated by hardware and software failure models. In many situations, there are trade-offs between task performance and task reliability. Thus, a mathematical assessment of performance-reliability trade-offs is necessary to evaluate the performance of real-time fault-tolerance systems. Assuming that the reliability of task execution is achieved through task replication, we present an approach that mathematically determines the replication factor for tasks. Our approach is novel in that it is a task schedule based analysis rather than a state based analysis as found in other models. Because we use a task schedule based analysis, we can provide a fast method to determine optimal redundancy levels, we are not limited to hardware reliability given by constant failure rate functions as in most other models, and we hypothesize that we can more naturally integrate with online real-time scheduling than when state based techniques are used. In this work, the goal is to maximize the total performance index, which is a performance-related reliability measurement. We present a technique based on a continuous task model and show how it very closely approximates discrete models and tasks with varying characteristics.>

Epsilon serializability (ESR) is a generalization of classic serializability (SR). In this paper, we provide a precise characterization of ESR when queries that may view inconsistent data run concurrently with consistent update transactions. Our first goal is to understand the behavior of queries in the presence of conflicts and to show how ESR in fact is a generalization of SR. So, using the ACTA framework, we formally express the intertransaction conflicts that are recognized by ESR and through that define ESR, analogous to the manner in which conflict-based serializability is defined. Secondly, expressions are derived for the amount of inconsistency (in a data item) viewed by a query and its effects on the results of a query. These inconsistencies arise from concurrent updates allowed by ESR. Thirdly, in order to maintain the inconsistencies within bounds associated with each query, the expressions are used to determine the preconditions that operations have to satisfy. The results of a query, and the errors in it, depend on what a query does with the (possibly inconsistent) data viewed by it. One of the important byproducts of this work is the identification of different types of queries which lend themselves to an analysis of the effects of data inconsistency on the results of the query.

This paper discusses a static algorithm for allocating and scheduling components of periodic tasks across sites in distributed systems. Besides dealing with the periodicity constraints, (which have been the sole concern of many previous algorithms), this algorithm handles precedence, communication, as well as replication requirements of subtasks of the tasks. The algorithm determines the allocation of subtasks of periodic tasks to sites, the scheduled start times of subtasks allocated to a site, and the schedule for communication along the communication channel(s). Simulation results show that the heuristics and search techniques incorporated in the algorithm are very effective.>

Extended transaction models in databases were motivated by the needs of complex applications such as CAD and software engineering. Transactions in such applications have diverse needs, for example, they may be long lived and they may need to cooperate. We describe ASSET, a system for supporting extended transactions. ASSET consists of a set of transaction primitives that allow users to define custom transaction semantics to match the needs of specific applications. We show how the transaction primitives can be used to specify a variety of transaction models, including nested transactions, split transactions, and sagas. Application-specific transaction models with relaxed correctness criteria, and computations involving workflows, can also be specified using the primitives. We describe the implementation of the ASSET primitives in the context of the Ode database.

This paper summarizes the state of the real-time field in the areas of scheduling and operating system kernels. Given the vast amount of work that has been done by both the operations research and computer science communities in the scheduling area, we discuss four paradigms underlying the scheduling approaches and present several exemplars of each. The four paradigms are: static table-driven scheduling, static priority preemptive scheduling, dynamic planning-based scheduling, and dynamic best effort scheduling. In the operating system context, we argue that most of the proprietary commercial kernels as well as real-time extensions to time-sharing operating system kernels do not fit the needs of predictable realtime systems. We discuss several research kernels that are currently being built to explicitly meet the needs of real-time applications.>

ACTA is a comprehensive transaction framework that facilitates the formal description of properties of extended transaction models. Specifically, using ACTA, one can specify and reason about (1) the effects of transactions on objects and (2) the interactions between transactions. This article presents ACTA as a tool for the synthesis of extended transaction models , one which supports the development and analysis of new extended transaction models in a systematic manner. Here, this is demonstrated by deriving new transaction definitions (1) by modifying the specifications of existing transaction models, (2) by combining the specifications of existing models, and (3) by starting from first principles. To exemplify the first, new models are synthesized from atomic transactions and join transactions . To illustrate the second, we synthesize a model that combines aspect of the nested - and split-transaction models. We demonstrate the latter by deriving the specification of an open-nested-transaction model from high-level requirements.

We present a novel co-processor for multiprocessor scheduling in the Spring real-time operating system. Since most dynamic scheduling problems are NP-complete, we use a heuristic algorithm which uses a smart searching scheme to find a feasible schedule for a set of specified tasks and hard deadlines. A parallel VLSI architecture for scheduling is developed that can be scaled for different numbers of tasks, numbers of resources, internal wordlengths, and future IC technologies. The scheduling architecture is implemented in a 0.8/spl mu/ CMOS technology and uses an advanced clocking scheme to allow further scaling to future technologies. With an internal clock rate of 100 MHz, a speed increase of two orders of magnitude is expected for scheduling tasks, thus removing a major bottleneck in real-time systems.>

The notion of hierarchical inconsistency bounds that allows inconsistency to be specified at different granularities-with transactions being at the top of the hierarchy, objects at the bottom, and groups in between-is introduced. The mechanisms needed to control the inconsistency so that it lies within the specified bounds are described. The performance improvement due to epsilon serializability (ESR) is evaluated. Two important observations are made. First, the thrashing point shifts to a higher multiprogramming level when transaction inconsistency bounds are increased. Second, for a particular multiprogramming level and a particular transaction inconsistency bound, the throughput does not increase with increasing object inconsistency bounds but peaks at some intermediate value.>

We present a novel VLSI co-processor for real-time multiprocessor scheduling. The co-processor can be used for sophisticated static scheduling as well as for online scheduling using many different algorithms such as earliest deadline first, highest value first, or the Spring scheduling algorithm. When such an algorithm is used online it is important to assess the performance impact of the interface of the co-processor to the host system, in this case, the Spring kernel. We focus on the interface and its implications for overall scheduling performance. We show that the current VLSI chip speeds up the main portion of the scheduling operation by over three orders of magnitude and speeds up the overall scheduling operation 30 fold. The parallel VLSI architecture for scheduling is briefly presented. This architecture can be scaled for different numbers of tasks, resources, and internal word lengths. The implementation uses an advanced clocking scheme to allow further scaling using future IC technologies.>

Most real-time scheduling algorithms schedule tasks with regard to their worst case computation times. Resources reclaiming refers to the problem of utilizing the resources left unused by a task when it executes in less than its worst case computation time, or when a task is deleted from the current schedule. Dynamic resource reclaiming algorithms that are effective, avoid any run time anomalies, and have bounded overhead costs that are independent of the number of tasks in the schedule are presented. Each task is assumed to have a worst case computation time, a deadline, and a set of resource requirements. The algorithms utilize the information given in a multiprocessor task schedule and perform online local optimization. The effectiveness of the algorithms is demonstrated through simulation studies.>

The authors analyze the performance of a heuristic algorithm, H/sub k/, which tries to keep at least k processors busy, if possible. H/sub k/ combines the features of two known heuristic scheduling algorithms: list scheduling and the H scheduling algorithm. The authors analyze its schedule length bound for both uniform tasks, i.e. tasks with the same computation time, and nonuniform tasks, i.e. tasks with arbitrary computation times. When k=2, the time complexity of H is the same as the complexity of the H scheduling algorithm and list scheduling, which is O(n/sup 2/r), where n is the number of tasks and r is the number of resources. Whereas the H scheduling algorithm has a poor schedule length bound but performs very well in finding feasible schedules, and list scheduling does not perform well in finding feasible schedules but has a good bound, the results show that H/sub 2/ has both a good schedule length bound and performs well in finding feasible schedules.>

The concurrency of transactions executing on atomic data types can be enhanced through the use of semantic information about operations defined on these types. Hitherto, commutativity of operations has been exploited to provide enchanced concurrency while avoiding cascading aborts. We have identified a property known as recoverability which can be used to decrease the delay involved in processing noncommuting operations while still avoiding cascading aborts. When an invoked operation is recoverable with respect to an uncommitted operation, the invoked operation can be executed by forcing a commit dependency between the invoked operation and the uncommitted operation; the transaction invoking the operation will not have to wait for the uncommitted operation to abort or commit. Further, this commit dependency only affects the order in which the operations should commit, if both commit; if either operation aborts, the other can still commit thus avoiding cascading aborts. To ensure the serializability of transactions, we force the recoverability relationship between transactions to be acyclic. Simulation studies, based on the model presented by Agrawal et al. [1], indicate that using recoverability, the turnaround time of transactions can be reduced. Further, our studies show enchancement in concurrency even when resource constraints are taken into consideration. The magnitude of enchancement is dependent on the resource contention; the lower the resource contention, the higher the improvement.

The authors investigate solutions to the priority inversion problem in a real-time database where two-phase locking is employed for concurrency control. They examine two basic schemes for addressing the priority inversion problem, one based on priority inheritance and the other based on priority abort. The authors also study a new scheme, called conditional priority inheritance, which attempts to capitalize on the advantage of each of the two basic schemes. The performance studies, conducted on a real-time database testbed, indicated that the basic priority inheritance protocol is inappropriate for solving the priority inversion problem in real-time database systems. The authors also show that the conditional priority inheritance scheme and the priority abort scheme perform well for a wide range of system workloads.>

article Extracting concurrency from objects: a methodology Share on Authors: Panos K. Chrysanthis Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile , S. Raghuram Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile , Krithi Ramamritham Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile Authors Info & Claims ACM SIGMOD RecordVolume 20Issue 2June 1991 pp 108–117https://doi.org/10.1145/119995.115803Online:01 April 1991Publication History 28citation326DownloadsMetricsTotal Citations28Total Downloads326Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A static algorithm for allocating and scheduling components of complex periodic tasks across sites in distributed systems is discussed. Besides dealing with the periodicity constraints (which have been the sole concern of many previous algorithms), this algorithm handles precedence, communication, and fault-tolerance requirements of subtasks of the tasks. The algorithm determines the allocation of subtasks of periodic tasks to sites, the scheduled start times of subtasks allocated to a site, and the schedule for communication along the communication channel(s). Experimental evaluation of the algorithm shows that the heuristics and search techniques incorporated in the algorithm are extremely effective. Specifically, they show that, if a task set can be feasibly allocated and scheduled, the algorithm is highly likely to find it without any backtracking during the search.>

Resource reclaiming refers to the problem of utilizing the resources left unused by a task when it executes in less than its worst-case computation time, or when a task is deleted from the current schedule. In dynamic real-time multiprocessor environments, resource reclaiming can be used to improve the average performance. Dynamic resource reclaiming algorithms must be effective in reclaiming unused time and also avoiding any anomalies. The authors present resource reclaiming algorithms with these properties. These algorithms are designed to have time complexity independent of the number of tasks in a schedule. The effectiveness of the algorithms is demonstrated through simulation studies. The algorithms have also been implemented in the Spring Kernel.>

The authors use the modal primitive recursive (MPR) arithmetic to facilitate definition, composition, and reasoning about the very large-scale finite state machines that represent substantive real-time systems. The MPR arithmetic provides a language of integer-valued functions which allow for compact and intuitive specification of state machines without enumeration of state sets or transition functions. The MPR arithmetic proof system is intended to be as close as possible to the proof system of classical algebra. The expressive range of the language extends from detailed description of multilevel concurrent algorithms to abstract properties of liveness and safety in a style similar to that of the temporal logics. The behavior of a real-time priority queue or communication pipeline is specified with MPR as an example, and the correctness of an implementation is verified.>

For next generation information systems, concurrency control mechanisms are required to handle high level abstract operations and to meet high throughput demands. The currently available single level concurrency control mechanisms for reads and writes are inadequate for future complex information systems. In this paper, we will present a new multilevel concurrency protocol that uses a semantics-based notion of conflict, which is weaker than commutativity, called recoverability. Further, operations are scheduled according to relative conflict, a conflict notion based on the structure of operations.Performance evaluation via extensive simulation studies show that with our multilevel concurrency control protocol, the performance improvement is significant when compared to that of a single level two-phase locking based concurrency control scheme or to that of a multilevel concurrency control scheme based on commutativity alone. Further, simulation studies show that our new multilevel concurrency control protocol performs better even with resource contention.

Recently, a number of extensions to the traditional transaction model have been proposed to support new information-intensive applications such as CAD/CAM and software development. However, these extended models capture only a subset of interactions that can be found in such applications, and represent only some of the points within the spectrum of interactions possible in competitive and cooperative environments.

The authors propose and study a window protocol suitable for transmitting time-constrained messages in a multiaccess network. The protocol differs from traditional window protocols in that it explicitly takes time constraints into account. The window is formed on the basis of the latest time to send a message (LS). A major advantage of the window protocol is that a newly arriving message is immediately considered for transmission if its LS is less than that of all pending messages in the system. As a result, the protocol closely approximates the optimal minimum-laxity-first policy. A performance evaluation through simulation shows that the protocol performs well in a wide range of environments, including under overloaded conditions.>

Efficient scheduling algorithms based on heuristic functions are developed for scheduling a set of tasks on a multiprocessor system. The tasks are characterized by worst-case computation times, deadlines, and resources requirements. Starting with an empty partial schedule, each step of the search extends the current partial schedule by including one of the tasks yet to be scheduled. The heuristic functions used in the algorithm actively direct the search for a feasible schedule, i.e. they help choose the task that extends the current partial schedule. Two scheduling algorithms are evaluated by simulation. To extend the current partial schedule, one of the algorithms considers, at each step of the search, all the tasks that are yet to be scheduled as candidates. The second focuses its attention on a small subset of tasks with the shortest deadlines. The second algorithm is shown to be very effective when the maximum allowable scheduling overhead is fixed. This algorithm is hence appropriate for dynamic scheduling in real-time systems.>

Results are presented of empirical evaluations carried out on the RT-CARAT testbed. This testbed was used evaluating a set of integrated protocols that support real-time transactions. A basic locking scheme for concurrency control was used to develop and evaluate several algorithms for handling CPU scheduling, data-conflict resolution, deadlock resolution, transaction wakeup, and transaction restart. The performance data indicate that the CPU scheduling algorithm is the most significant of all the algorithms in improving the performance of real-time transactions, conflict-resolution protocols which directly address deadlines and criticality can have a substantial impact on performance compared to protocols that ignore such information, both criticality and deadline distributions strongly affect transaction performance, and overheads such as locking and message communication are nonnegligible and cannot be ignored in real-time transaction analysis. It is believed that these empirical results represent the first experimental results for real-time transactions on a testbed system.>

A set of four heuristic algorithms is presented to schedule tasks that have headlines and resource requirements in a distributed system. When a task arrives at a node, the local scheduler at that node attempts to guarantee that the task will complete execution on that node before its deadline. If the attempt fails, the scheduling components on individual nodes cooperate to determine which other node in the system has sufficient resource surplus to guarantee the task. Simulation studies are performed to compare the performance of these algorithms with respect to each other as well to two baselines. The first baseline is the noncooperative algorithm where a task that cannot be guaranteed locally is not sent to any other node. The second is an (ideal) algorithm that behaves exactly like the bidding algorithm but incurs no communication overheads. The simulation studies examine how communication delay, task laxity, load differences on the nodes, and task computation times affect the performance of the algorithms. The results show that distributed scheduling is effective even in a hard real-time environment and that the relative performance of these algorithms is a function of the system state.>

A novel window protocol for transmitting time-constrained messages in a multiaccess network is proposed that explicitly takes time constraints into account. The window is formed on the basis of latest time to send a message (LS). A newly arriving message is immediately considered for transmission if its LS is less than those of the all pending messages in the system. As a result, the protocol closely approximates the optimal minimum-laxity-first policy. A performance evaluation by simulation shows that the protocol performs well in a wide range of environments, even under overloaded conditions.>

Two task-scheduling algorithms for distributed hard real-time computer systems are presented. Both algorithms are based on a heuristic approach and explicitly account for both the deadlines and criticality of tasks when making scheduling decisions. In analyzing the algorithms, a performance metric called the weighted guarantee ratio is defined. It reflects both the percentage of tasks that make their deadlines and their relative worth to the system. The performance is analyzed by simulating the behavior of the algorithms as well as that of several other pertinent baseline algorithms under a wide range of system conditions including a nonhomogeneous task arrival rate. The results show that the algorithms outperform all the baseline algorithms except for the ideal but impractical centralized baseline and in many cases perform close to the ideal.>

A method is discussed for synchronizing operations on objects when the operations are invoked by transactions. The technique, which is motivated by a desire to make use of possible concurrency in accessing objects, takes into consideration the granularity at which operations affect an object. A dynamic method is presented for determining the compatibility of an invoked operation with respect to operations in progress. In making decisions, it utilizes the state of the object, the semantics of the uncommitted operations, the actual parameters of the invoked operation, and the effect of the operations on the objects. One of the attractive features of this technique is that a single framework can be used to deal with the problem of synchronizing access to simple objects as well as compound objects, i.e. objects in which some components are themselves objects.>

The concurrency of transactions executing on atomic data types can be enhanced through the use of semantic information about operations defined on these types. Hitherto, commutativity of operations has been exploited to provide enhanced concurrency while avoiding cascading aborts. We have identified a property known as recoverability which can be used to decrease the delay involved in processing non-commuting operations while still avoiding cascading aborts. When an invoked operation is recoverable with respect to an uncommitted operation, the invoked operation can be executed by forcing a commit-dependency between the invoked operation and the uncommitted operation; the transaction invoking the operation will not have to wait for the uncommitted operation to abort or commit. Further, this commit dependency only affects the order in which the operations should commit, if both commit; if either operation aborts, the other can still commit thus avoiding cascading aborts. To ensure the serializability of transactions, we force the recoverability relationship between transactions to be acyclic.

We consider the problem of scheduling a set of n preemptable tasks in a system having r resources. Each task has an arbitrary, but known, worst case processing time and a deadline, and may request simultaneous use of a number of resources. A resource can be used either in shared mode or exclusive mode. In this paper, we develop and evaluate algorithms for determining whether or not a set of preemptive tasks is schedulable in such a real-time system, and if so, determining a schedule for it. This scheduling problem is known to be computationally intensive. In many real-time application environments, tasks are scheduled dynamically, and hence the scheduling algorithms used must have low run-time costs. To keep run-time costs low, we propose the use of suboptimal but practical algorithms that employ computationally simple heuristics. The computational complexity of our algorithms for scheduling n tasks in a system having r resources is O(rn2), which is very much lower than that of known optimal algorithms. We report on the results of simulation studies performed on such heuristic preemptive scheduling algorithms and the sensitivity of the performance of the algorithms with respect to various scheduling parameters. These studies show that due to the complexity of the problem, straightforward heuristics do not perform satisfactorily. However, an algorithm that uses combinations of such heuristics in conjunction with limited backtracks works very well.

We study virtual time CSMA protocols for hard real time communication systems, i, e., systems where messages have explicit deadlines. In this class of CSMA protocols, each node maintains two clocks; a real time clock and a virtual time clock. Whenever a node finds the channel to be idle, it resets its virtual clock. The virtual clock then runs at a higher rate than the real clock. A node transmits a waiting message when the time on the virtual clock is equal to some parameter of the message. Using different message parameters in conjunction with the virtual clock, different transmission policies can be implemented. In particular, use of message arrival time, message length, message laxity, and message deadline implements FCFS, Minimum-Length-First, Minimum-Laxity-First, and Minimum-Deadline-First transmission policies, respectively.

This paper describes a heuristic approach for solving the problem of dynamically scheduling tasks in a real-time system where tasks have deadlines and general resource requirements. The crux of our approach lies in the heuristic function used to select the task to be scheduled next. The heuristic function is composed of three weighted factors. These factors explicitly consider information about real-time constraints of tasks and their utilization of resources. Simulation studies show that the weights for the various factors in the heuristic function have to be fine-tuned in order to obtain a degree of success in the range of 75-88 percent of that obtained via exhaustive search. However, modifying the approach to use limited backtracking improves the degree of success substantially to as high as 99.5 percent. This improvement is observed even when the initial set of weights are not tailored for a particular set of tasks. Simulation studies also show that in most cases the schedule determined by the heuristic algorithm is optimal or close to optimal.

Gutenberg is a port-based operating system being designed to study protection issues in distributed systems. All shared resources are viewed as protected objects and hence can be assessed only via specific operations defined on them. Processes communicate and access objects through the use of ports. Each port is associated with an abstract data type operation and can be created by a process only if the process has the capability to execute the operation on the type. Thus, a port represents the privilege of the port's client process to request a service. Capabilities to create ports for requesting operations are contained in a capability directory, which is navigated by processes to gain these capabilities. Privilege transfer is a means of providing servers access to the resources they need to perform their services. In Gutenberg, privilege transfer is accomplished by allowing access to subdirectories of the capability directory and by passing capabilities, including port access capabilities, to processes via ports. It should be possible to revoke transferred privileges when breaches of trust are detected or suspected, when a period of time has passed beyond which the distributor of a privilege does not want the privilege shared, or when an error has been detected.

An interprocess communication facility provided by the kernel of the Gutenberg experimental operating system is presented. In Gutenberg all interprocess communication is via channels (ports) that are typed by the service which can be requested on them. Ports are created by reference to their service without using the identifier of the process providing the service, a technique the authors refer to as functional addressing. By using functional addressing, interprocess transfer of port use privileges and a new concept of cooperation class, arbitrary process interconnection topologies can be achieved without any explicit use of process identifiers by processes. Examples of object sharing with abstract data type managers and data-driven protocols of database query execution are presented to illustrate the methods of constructing systems of cooperation processes using the Gutenberg system.

Most systems which are required to operate under severe real-time constraints assume that all tasks and their characteristics are known a priori. Scheduling of such tasks can be done statistically. Further, scheduling algorithms operating under such conditions are usually limited to multiprocessor configurations. The authors present a scheduling algorithm which works dynamically and on loosely coupled distributed systems for tasks with hard real-time constraints; i.e., the tasks must meet their deadlines. It uses a scheduling component local to every node and a distributed scheduling scheme which is specifically suited to hard real-time constraints and other timing considerations. Periodic tasks, nonperiodic tasks, scheduling overheads, communication overheads due to scheduling and preemption are all accounted for in the algorithm. Simulation studies are used to evaluate the performance of the algorithm.

A distributed system is viewed as a set of objects and processes utilizing the objects. If a shared object, known as a resource, is accessed concurrently, some mechanism is necessary to control use of the resource in order to satisfy the consistency and fairness requirements associated with the resource. These mechanisms are termed resource controllers.

The formalism of temporal logic has been suggested to be an appropriate tool for expressing the semantics of concurrent programs. This paper is concerned with the application of temporal logic to the specification of factors affecting the synchronization of concurrent processes. Towards this end, we first introduce a model for synchronization and axiomatize its behavior. SYSL, a very high-level language for specifying synchronization properties, is then described. It is designed using the primitives of temporal logic and features constructs to express properties that affect synchronization in a fairly natural and modular fashion. Since the statements in the language have intuitive interpretations, specifications are humanly readable. In addition, since they possess appropriate formal semantics, unambiguous specifications result.