Attack graphs provide a way to model multiple attack vectors and multi-step attacks in a holistic manner that a malicious actor could use to compromise a system. Traditional methods of generating attack graphs involve expert knowledge, manual curation, and computational algorithms that might not cover the entire threat landscape due to the ever-evolving nature of vulnerabilities and exploits. This paper explores the approach of leveraging large language models (LLMs), such as GPT4, to automate the generation of attack graphs by intelligently chaining CVEs based on their preconditions and effects. It also shows how to utilize LLMs to create attack graphs from threat reports.

In connected autonomous vehicles (CAVs), the driving safety can be greatly deteriorated, in the presence of occlusions which are adverse to CAVs' perception of region-of-interest (RoI). Collaborative perception on the basis the information sharing of occlusions among CAVs, in a real-time and accurate manner, provides a means of the occlusion-free RoI perception for safe driving. In this paper, we propose a novel framework ofCollaborativeOcclusion-freePerception (COFP) in CAVs, to regain the real-time and accurate occlusion awareness. The innovative COFP targets two goals: well-balanced computation resource allocation, as well as fast and high-quality RoI information fusion. Specifically, the resource allocation problem, with the objective of minimizing CAVs' completion delay, is formulated as a multi-player continuous potential game and solved by a better response dynamics (BRD) algorithm. The RoI information fusion, with the objective of maximizing the overall object depiction quality, is formulated as a combinatorial optimization problem, and solved by a modified discrete salp swarm (MDSSA) algorithm. Experimental results show that the proposed COFP with 5GHz computing power can achieve full occlusion awareness for CAVs with 69.61% completion time reduction and 19.03% fusion quality improvement, compared to the existing methods.

We consider the problem of task offloading and resource allocation in mobile edge computing (MEC). To maintain satisfactory quality of experience (QoE) of end-users, mobile devices (MDs) may offload their tasks to edge servers based on the allocated computation (e.g., CPU/GPU cycles and storage) and wireless resources (e.g., bandwidth). However, these resources could not be effectively utilized unless an encouraging resource allocation scheme can be proposed. What’s worse, task offloading incurs additional MEC energy consumption, which inevitably violate the long-term MEC energy budget. Considering these two challenges, we propose an online joint offloading and resource allocation (JORA) framework under the long-term MEC energy constraint, aiming at guaranteeing the end-users’ QoE. To achieve this, we leverage Lyapunov optimization to exploit the optimality of the long-term QoE maximization problem. By constructing an energy deficit queue to guide energy consumption, the problem can be solved in a real-time manner. On this basis, we propose online JORA methods in both centralized and distributed manners. Furthermore, we prove that our proposed methods enable the achievement of the close-to-optimal performance while satisfying the long-term MEC energy constraint. In addition, we conduct extensive simulations and the results show superiority in performance over other methods.

Cloud-based Natural Language Understanding (NLU) services are becoming more popular with the development of artificial intelligence. More applications are integrated with cloud-based NLU services to enhance the way people communicate with machines. However, with NLU services provided by different companies powered by unrevealed AI technology, how to choose the best one is a problem for developers. Existing tools that can provide guidance to developers and make recommendations based on their needs are severely limited. This article comprehensively evaluates multiple state-of-the-art NLU services, and the results indicate that there is no absolute winner for different usage requirements. Motivated by this observation, we provide several insights and propose NLUBroker , a Quality of Experience-driven (QoE-driven) broker system, to select the proper service according to the environment. NLUBroker senses the client and service status and leverages a solution to the multi-armed bandit problem to conduct online learning, aiming to achieve maximum expected QoE. The performance of NLUBroker is evaluated in both simulation and real-world environments, and the evaluation results demonstrate that NLUBroker is an efficient solution for selecting NLU services. It is adaptive to changes in the environment, outperforms three baseline methods we evaluated and improves overall QoE up to 1.5× for the evaluated state-of-the-art NLU services.

The spatial-temporal locality has been observed in various scenarios for conversational services with either voice or text requests. Given the current cloud-based processing mechanism, integrating such a service with caching is a promising way to improve responsiveness, reduce in-network transmission, and avoid computational redundancy. Goes beyond precise redundancy and fuzzy redundancy, semantic redundancy adapts to the diversity in command expression, and is considered as a practical solution for conversational services. In this paper, we introduce a hierarchical cache design inspired by semantic redundancy for conversational services. We propose a scalable edge system ChatCache to incorporate the hierarchical cache design and serve single or multiple users. We discussed the cache efficiency with different similarity match policies, and evaluate the responsiveness and scalability of ChatCache on heterogeneous edge platforms. On most of the evaluated platforms, ChatCache reduces user-perceived latency by more than 91.7% for voice requests, more than 81.6% for text requests. The throughput of ChatCache reaches 42.6 throughput tps for voice requests, and 64.4 tps for text requests, which is comparable with mainstream cloud cognitive services. The promising evaluation results show the capability of ChatCache in reducing the user-perceived latency and computation redundancy with high response accuracy for conversational services.

This paper presents a transparent Container Network Memory storage device, coined as CNetMem, aiming to address the open problem of unpredictable performance degradation of containers when the working set of an application no longer fits in container memory. First, CNetMem will enable application tenants running in a container to park their working set memory/file to a faster network memory storage by organizing a group of remote memory nodes as remote memory donors. This allows CNetMem to take advantage of remote idle memory on a cluster before resorting to a slow local I/O subsystem like local disk without any modification of host OS or application. Second, CNetMem provides a hybrid batching technique to remove or alleviate performance bottlenecks in the I/O performance critical path for remote memory read/write with replication or disk backup for fault tolerance. Third, CNetMem introduces a rank-based node selection algorithm to find the optimal node for placing remote memory blocks across cluster. This helps CNetMem to reduce the performance impact due to remote memory eviction. Extensive experiments are conducted on three big data applications and four machine learning workloads. The results show that CNetMem achieves up to 172× throughput improvements compared to vanilla Linux and up to 5.9× completion time improvements over existing approaches in big data and ML workload.

An efficient approach to managing big data workloads is to enable applications to work directly with huge pages. This can effectively avoid or reduce the memory fragmentation problem due to high frequent memory allocation and deallocation and significantly minimize the performance degradation of big data applications. This paper presents XPage, a huge page memory management framework, with three novel features. First, XPage by design can provide automated huge page managements with transparency to both OS and applications. Second, Xpage represents a memory management redesign that brings performance and memory saving to memory intensive applications by supporting dynamic huge page memory management without resorting to splitting huge pages for memory fragmentation. Third but not the least, XPage can efficiently minimize the internal fragmentation without impacting performance of applications. We conduct extensive experiments to evaluate the effectiveness of XPage in minimizing internal memory fragmentation in the presence of dynamic memory intensive big data workloads, by comparing XPage with vanilla Linux using 4KB base page and Linux with 2MB huge page.

Federated learning(FL) is an emerging distributed learning paradigm with default client privacy because clients can keep sensitive data on their devices and only share local training parameter updates with the federated server. However, recent studies reveal that gradient leakages in FL may compromise the privacy of client training data. This paper presents a gradient leakage resilient approach to privacy-preserving federated learning with per training example-based client differential privacy, coined as Fed-CDP. It makes three original contributions. First, we identify three types of client gradient leakage threats in federated learning even with encrypted client-server communications. We articulate when and why the conventional server coordinated differential privacy approach, coined as Fed-SDP, is insufficient to protect the privacy of the training data. Second, we introduce Fed-CDP, the per example-based client differential privacy algorithm, and provide a formal analysis of Fed-CDP with the (∊,δ) differential privacy guarantee, and a formal comparison between Fed-CDP and Fed-SDP in terms of privacy accounting. Third, we formally analyze the privacy-utility tradeoff for providing differential privacy guarantee by Fed-CDP and present a dynamic decay noise-injection policy to further improve the accuracy and resiliency of Fed-CDP. We evaluate and compare Fed-CDP and Fed-CDP(decay) with Fed-SDP in terms of differential privacy guarantee and gradient leakage resilience over five benchmark datasets. The results show that the Fed-CDP approach outperforms conventional Fed-SDP in terms of resilience to client gradient leakages while offering competitive accuracy performance in federated learning.

Data quality assessment is an essential process of any data analysis process including machine learning. The process is time-consuming as it involves multiple independent data quality checks that are performed iteratively at scale on evolving data resulting from exploratory data analysis (EDA). Existing solutions that provide computational optimizations for data quality assessment often separate the data structure from its data quality which then requires efforts from users to explicitly maintain state-like information. They demand a certain level of distributed system knowledge to ensure high-level pipeline optimizations from data analysts who should instead be focusing on analyzing the data. We, therefore, propose data-quality-aware dataframes, a data quality management system embedded as part of a data analyst's familiar data structure, such as a Python dataframe. The framework automatically detects changes in datasets' metadata and exploits the context of each of the quality checks to provide efficient data quality assessment on ever-changing data. We demonstrate in our experiment that our approach can reduce the overall data quality evaluation runtime by 40-80% in both local and distributed setups with less than 10% increase in memory usage.

Partitioning is effective in avoiding expensive shuffling operations. However, it remains a significant challenge to automate this process for Big Data analytics workloads that extensively use user defined functions (UDFs), where sub-computations are hard to be reused for partitionings compared to relational applications. In addition, functional dependency that is widely utilized for partitioning selection is often unavailable in the unstructured data that is ubiquitous in UDF-centric analytics. We propose the Lachesis system, which represents UDF-centric workloads as workflows of analyzable and reusable sub-computations. Lachesis further adopts a deep reinforcement learning model to infer which sub-computations should be used to partition the underlying data. This analysis is then applied to automatically optimize the storage of the data across applications to improve the performance and users' productivity.

Time series value forecasting using machine learning models utilizing time series features has recently got good attention of Time series analytics community. This paper proposes an automated feature learning mechanisms to filter out most useful features from hundreds of available features for time series prediction problems. The paper further proposes a novel mechanism to dynamically filter features that are most suitable for the given input time series data. With such mechanisms we create pipeline consisting of most useful features for given input data and increases the performance of the prediction model. Our proposed mechanism first, groups well known features for time series analysis, generates and assigns the features importance score using multiple scoring configurations. Once scores are assigned, features are filtered using a threshold that is derived using reference feature score and Critical Difference diagram. The filtered features are subsequently analyzed based on the characteristics of the input dataset. We show using experimental results that our approach of input data based dynamic feature selection improves the overall performance of machine learning models compared to the case where dynamic feature extraction is not applied prior to modeling.

Data Quality (DQ) has been one of the key focuses as Data Analytics and Artificial Intelligence (AI) fields continue to grow. Yet, data quality analysis has mostly been a disjointed, ad-hoc, and cumbersome process in the overall data analysis workflow. There have been ongoing attempts to formalize this process, but the solutions that have come out are not universally applicable. Most of the proposed solutions try to address the problem of data quality from a limited perspective and suc-cessfully address only a subset of all challenges. These solutions fail to translate to other domains due to a lack of structure. In this paper, we present DQLearn, a toolkit for structured data quality learning. We start by presenting the core principle on which we build our library and introduce the four components that provide a solid base to address the needs of the data quality problem. Then, we showcase our automation structure - "Workflows", and the two optimization techniques equipped with it, that help the users to structure their learning problem very easily. Next, we discuss four important scenarios of the DQ Workflows in the overall life-cycle. Finally, we demonstrate the utility of the proposed toolkit with public datasets and show benchmark results from optimization experiments.

This paper proposes a verifiable imputation process and an enabling tool for univariate time series. Common ad-hoc and case-specific imputation are not enough to ensure high quality and effective imputation. We adopt the similar verification logic of supervised learning. We use artificial missing sampling as the test set to estimate a set of imputers' performances and use the estimated performances to select the best imputer. To ensure the correctness of selection, we analyze the impact of various factors on estimation accuracy. Those factors are missing rate, size of artificial missing data and patterns, selected imputers, and noise level. We propose a two-step verifiable imputation process to integrate all of the steps. With this process, we can always leverage the most suitable imputer to achieve a high quality of imputation without tedious and error-prone data cleaning efforts. We implement the tool as a Python package, with many imputers with their unique capabilities and a API. We automate the imputation through a standard process, which returns imputed results and detailed rationales of selection along with quality metrics.

Voice assistant systems are becoming immersive in our daily lives nowadays. However, current voice assistant systems rely on the cloud for command understanding and fulfillment, resulting in unstable performance and unnecessary frequent network transmission. In this paper, we introduce CHA, an edge-based caching framework for voice assistant systems, and especially for smart homes where resource-restricted edge devices can be deployed. Located between the voice assistant device and the cloud, CHA introduces a layered architecture with modular design in each layer. By introducing an understanding module and adaptive learning, CHA understands the user's intent with high accuracy. By maintaining a cache, CHA reduces the interaction with the cloud and provides fast and stable responses in a smart home. Targeting on resource-constrained edge devices, CHA uses joint classification and model pruning on a pre-trained language model to achieve performance and system efficiency. We compare CHA to the status quo solution of voice assistant systems and show that CHA benefits voice assistant systems. We evaluate CHA on three edge devices that differ in hardware configuration and demonstrate its ability to meet the latency and accuracy demands with efficient resource utilization. Our evaluation shows that compared to the current solution for voice assistant systems, CHA can provide at least 70% speedup in responses for frequently asked voice commands with less than 13% CPU consumption, and less than 9% memory consumption when running on a Raspberry Pi.

For years, vehicle trajectory data have increasingly been important for a wide range of applications, from driver behavior investigation/classification, travel time/distance estimation, and routing in vehicular networks, to vehicle energy/emission evaluation. This article presents TrajData, the first systematic solution to reliable vehicle trajectory data collection, with only reliance on commercial-off-the-shelf (COTS) onboard unit (OBU) devices that utilize lightweight GPS modules and low-cost onboard diagnostics (OBD) readers. In the practical use of trajectory collection, GPS outages inevitably occur in urban environments thereby leading to large trajectory errors as well as missing vehicle location data. To resolve this, we propose a novel data-fusion-enabled deep learning approach with the purpose of achieving reliable vehicle trajectory collection in various urban road conditions. Specifically, we leverage motion information retrieved from OBD readers in TrajData to help reconstruct the trajectory data during GPS outages. By investigating the changes of direction angle from the OBD readings, we can identify different types of road sections. Furthermore, we integrate the neural arithmetic logic units (NALUs) into our trajectory reconstruction model to tame the challenges when GPS outages take place in various road sections. Experimental results from realistic data have demonstrated the effectiveness and reliability of the proposed method. In the road test, TrajData achieves an average position error below 15-m around a 60-s GPS outage, even in complex road sections, i.e., continuous turns and driving with accelerations/decelerations resulting in frequent changes of direction and speed.

Learning Rate (LR) is an important hyper-parameter to tune for effective training of deep neural networks (DNNs). Even for the baseline of a constant learning rate, it is non-trivial to choose a good constant value for training a DNN. Dynamic learning rates involve multi-step tuning of LR values at various stages of the training process and offer high accuracy and fast convergence. However, they are much harder to tune. In this paper, we present a comprehensive study of 13 learning rate functions and their associated LR policies by examining their range parameters, step parameters, and value update parameters. We propose a set of metrics for evaluating and selecting LR policies, including the classification confidence, variance, cost, and robustness, and implement them in LRBench, an LR benchmarking system. LRBench can assist end-users and DNN developers to select good LR policies and avoid bad LR policies for training their DNNs. We tested LRBench on Caffe, an open source deep learning framework, to showcase the tuning optimization of LR policies. Evaluated through extensive experiments, we attempt to demystify the tuning of LR policies by identifying good LR policies with effective LR value ranges and step sizes for LR update schedules.

This paper presents a data analytics system which determines optimal analytics algorithms by selectively testing a wide range of different algorithms and optimizing parameters using Transformer-Estimator Graphs. Our system is applicable to situations in which multiple clients need to perform calculations on the same data sets. Our system allows clients to cooperate in performing analytics calculations by sharing results and avoiding redundant calculations. Computations may be distributed across multiple nodes, including both client and server nodes. We provide multiple options for dealing with changes to data sets depending upon the data consistency requirements of applications. Another key contribution of our work is the Transformer-Estimator Graph, a system for specifying a wide variety of options to use for machine learning modeling and prediction. We show how Transformer-Estimator Graphs can be used for analyzing time series data. A key feature that we provide for making our system easy to use is solution templates which are customized to problems in specific domains.

Storage and memory systems for modern data analytics are heavily layered, managing shared persistent data, cached data, and nonshared execution data in separate systems such as a distributed file system like HDFS, an in-memory file system like Alluxio, and a computation framework like Spark. Such layering introduces significant performance and management costs. In this paper we propose a single system called Pangea that can manage all data---both intermediate and long-lived data, and their buffer/caching, data placement optimization, and failure recovery---all in one monolithic distributed storage system, without any layering. We present a detailed performance evaluation of Pangea and show that its performance compares favorably with several widely used layered systems such as Spark.

Data stores and cloud services are typically accessed using a client-server paradigm wherein the client runs as part of an application process which is trying to access the data store or cloud service. This paper presents the design and implementation of enhanced clients for improving both the functionality and performance of applications accessing data stores or cloud services. Our enhanced clients can improve performance via multiple types of caches, encrypt data for providing confidentiality before sending information to a server, and compress data for reducing the size of data transfers. Our clients can perform data analysis to allow applications to more effectively use cloud services. They also provide both synchronous and asynchronous interfaces. An asynchronous interface allows an application program to access a data store or cloud service and continue execution before receiving a response which can significantly improve performance. We present a Universal Data Store Manager (UDSM) which allows an application to access multiple different data stores and provides a common interface to each data store. The UDSM also can monitor the performance of different data stores. A workload generator allows users to easily determine and compare the performance of different data stores. We also present NLU-SA, an application for performing natural language understanding and sentiment analysis on text documents. NLU-SA is implemented on top of our enhanced clients and integrates text analysis with Web searching. We present results from NLU-SA on sentiment on the Web towards major companies and countries. We also present a performance analysis of our enhanced clients.

Cloud computing has made the resources needed to execute large-scale in-memory distributed computations widely available. Specialized programming models, e.g., MapReduce, have emerged to offer transparent fault tolerance and fault recovery for specific computational patterns, but they sacrifice generality. In contrast, the Resilient X10 programming language adds failure containment and failure awareness to a general purpose, distributed programming language. A Resilient X10 application spans over a number of places. Its formal semantics precisely specify how it continues executing after a place failure. Thanks to failure awareness, the X10 programmer can in principle build redundancy into an application to recover from failures. In practice, however, correctness is elusive, as redundancy and recovery are often complex programming tasks. This article further develops Resilient X10 to shift the focus from failure awareness to failure recovery, from both a theoretical and a practical standpoint. We rigorously define the distinction between recoverable and catastrophic failures. We revisit the happens-before invariance principle and its implementation. We shift most of the burden of redundancy and recovery from the programmer to the runtime system and standard library. We make it easy to protect critical data from failure using resilient stores and harness elasticity—dynamic place creation—to persist not just the data but also its spatial distribution. We demonstrate the flexibility and practical usefulness of Resilient X10 by building several representative high-performance in-memory parallel application kernels and frameworks. These codes are 10× to 25× larger than previous Resilient X10 benchmarks. For each application kernel, the average runtime overhead of resiliency is less than 7%. By comparing application kernels written in the Resilient X10 and Spark programming models, we demonstrate that Resilient X10’s more general programming model can enable significantly better application performance for resilient in-memory distributed computations.

This paper presents a cloud-based system for health care applications. Our system has advanced features for preserving privacy which are essential for health care applications that deal with confidential data. We describe some of the bioinformatics applications which our system is designed for. Performance is significantly enhanced by caching, and enhanced clients for performing part of the computations are a key component of our system. Cloud, due to its pay-as-you-go pricing and API based deployment model, has become widely used for delivering and maintaining infrastructure technology for businesses. However, there are significant challenges with using the cloud for applications with strict privacy and compliance requirements; health care applications fall in this domain. This paper describes an architecture and solutions for handling these types of applications.

The identification of drug-target interactions (DTIs) is a key task in drug discovery, where drugs are chemical compounds and targets are proteins. Traditional DTI prediction methods are either time consuming (simulation-based methods) or heavily dependent on domain expertise (similarity-based and feature-based methods). In this work, we propose an end-to-end neural network model that predicts DTIs directly from low level representations. In addition to making predictions, our model provides biological interpretation using two-way attention mechanism. Instead of using simplified settings where a dataset is evaluated as a whole, we designed an evaluation dataset from BindingDB following more realistic settings where predictions of unobserved examples (proteins and drugs) have to be made. We experimentally compared our model with matrix factorization, similarity-based methods, and a previous deep learning approach. Overall, the results show that our model outperforms other approaches without requiring domain knowledge and feature engineering. In a case study, we illustrated the ability of our approach to provide biological insights to interpret the predictions.

Summary Distributed key‐value stores have become indispensable for large‐scale cluster applications. Many cloud services have deployed in‐memory data grids for their enterprise infrastructures and support multi‐tenancy services. However, most services do not offer fine‐grained multi‐tenant resource sharing. To this front, we present KeyValueServe, a low overhead cloud service with features aiding resource management. Results based on Hazelcast, a popular open source data grid, indicate that KeyValueServe can efficiently provide services to tenants without degrading performance. Providing consistent performance to all tenants for fluctuating workloads is still difficult. Performance problems occur at scale with diverse tenant requirements. To address this, the paper provides insights to contention and performance bottlenecks. Through experimental analysis, we uncover scenarios of performance degradation and demonstrate optimized performance via coalescing multiple clients' requests. Our work indicates that a Hazelcast cluster can get congested with multiple concurrent connections when processing client requests, resulting in poor performance. KeyValueServe can reduce the number of parallel connections maintained for client requests, resulting in improved performance.

A wide variety of services are available over the Web which can dramatically improve the functionality of applications. These services include information retrieval (including data lookups from a variety of sources and Web searches), natural language understanding, visual recognition, and data storage. A key problem is how to provide support for applications which use these services. This paper presents a rich software development kit (SDK) which accesses these services and provides a variety of features applications need to use these services, optimize performance, and compare them. A key aspect of our SDK is its support for natural language understanding services. We also present a personalized knowledge base built on top of our rich SDK that uses publically available data sources as well as private information. The knowledge base supports data analysis and reasoning over data.

Data stores are typically accessed using a clientserver paradigm wherein the client runs as part of an application process which is trying to access the data store. This paper presents the design and implementation of enhanced data store clients having the capability of caching data for reducing the latency for data accesses, encryption for providing confidentiality before sending data to the server, and compression for reducing the size of data sent to the server. We support multiple approaches for caching data as well as multiple different types of caches. We also present a Universal Data Store Manager (UDSM) which allows an application to access multiple different data stores and provides a common interface to each data store. The UDSM provides both synchronous and asynchronous interfaces to each data store that it supports. An asynchronous interface allows an application program to access a data store and continue execution before receiving a response from the data store. The UDSM also can monitor the performance of different data stores. A workload generator allows users to easily determine and compare the performance of different data stores. The paper examines the key design issues in developing both the enhanced data store clients and the UDSM. It also looks at important issues in implementing client-side caching. The enhanced data store clients and UDSM are used to determine the performance of different data stores and to quantify the performance gains that can be achieved via caching.

Ballooning is a popular solution for dynamic memory balancing. However, existing solutions may perform poorly in the presence of heavy guest swapping. Furthermore, when the host has sufficient free memory, guest virtual machines (VMs) under memory pressure is not be able to use it in a timely fashion. Even after the guest VM has been recharged with sufficient memory via ballooning, the applications running on the VM are unable to utilize the free memory in guest VM to quickly recover from the severe performance degradation. To address these problems, we present MemFlex, a shared memory swapper for improving guest swapping performance in virtualized environment with three novel features: (1) MemFlex effectively utilizes host idle memory by redirecting the VM swapping traffic to the host-guest shared memory area. (2) MemFlex provides a hybrid memory swapping model, which treats a fast but small shared memory swap partition as the primary swap area whenever it is possible, and smoothly transits to the conventional disk-based VM swapping on demand. (3) Upon ballooned with sufficient VM memory, MemFlex provides a fast swap-in optimization, which enables the VM to proactively swap in the pages from the shared memory using an efficient batch implementation. Instead of relying on costly page faults, this optimization offers just-in-time performance recovery by enabling the memory intensive applications to quickly regain their runtime momentum. Performance evaluation results are presented to demonstrate the effectiveness of MemFlex when compared with existing swapping approaches.

Distributed key-value stores have become indispensable for large scale low latency applications. Many cloud services have deployed in-memory data grids for their enterprise infrastructures and support multi-tenancy services. But it is still difficult to provide consistent performance to all tenants for fluctuating workloads that need to scale out. Many popular key-value stores suffer from performance problems at scale and different tenant requirements. To this front, we present our study with Hazelcast, a popular open source data grid, and provide insights to contention and performance bottlenecks. Through experimental analysis, this paper uncovers scenarios of performance degradation followed by optimized performance via end-point multiplexing. Our study suggests that processing increasing number of client requests spawning fewer number of threads help improve performance.

Dynamic VM memory management via the balloon driver is a common strategy to manage the memory resources of VMs under changing workloads. However, current approaches rely on kernel instrumentation to estimate the VM working set size, which usually result in high run-time overhead. Thus system administrators have to tradeoff between the estimation accuracy and the system performance. This paper presents iBalloon, a light-weight, accurate and transparent prediction based mechanism to enable more customizable and efficient ballooning policies for rebalancing memory resources among VMs. Experiment results from well known benchmarks such as Dacapo and SPECjvm show that iBalloon is able to quickly react to the VM memory demands, provide up to 54% performance speedup for memory intensive applications running in the VMs, while incurring less than 5% CPU overhead on the host machine as well as the VMs.

The recent shift towards write-intensive workload on big data (e.g., financial trading, social user-generated data streams)has pushed the proliferation of log-structured key-value stores, represented by Google's BigTable [1], Apache HBase [2] andCassandra [3]. While providing key-based data access with aPut/Get interface, these key-value stores do not support value-based access methods, which significantly limits their applicability in modern web and database applications. In this paper, we present DELI, a DEferred Lightweight Indexing scheme on the log-structured key-value stores. To index intensively updated bigdata in real time, DELI aims at making the index maintenance as lightweight as possible. The key idea is to apply an append-only design for online index maintenance and to collect index garbage at carefully chosen time. DELI optimizes the performance of index garbage collection through tightly coupling its execution with a native routine process called compaction. The DELI's system design is fault-tolerant and generic (to most key-valuestores), we implemented a prototype of DELI based on HBase without internal code modification. Our experiments show that the DELI offers significant performance advantage for the write-intensive index maintenance.

Checkpointing and rollback techniques enhance reliability and availability of virtual machines and their hosted IT services. This paper proposes VM-μCheckpoint, a light-weight pure-software mechanism for high-frequency checkpointing and rapid recovery for VMs. Compared with existing techniques of VM checkpointing, VM-μCheckpoint tries to minimize checkpoint overhead and speed up recovery by means of copy-on-write, dirty-page prediction and in-place recovery, as well as saving incremental checkpoints in volatile memory. Moreover, VM-μCheckpoint deals with the issue that latency in error detection potentially results in corrupted checkpoints, particularly when checkpointing frequency is high. We also constructed Markov models to study the availability improvements provided by VM-μCheckpoint (from 99 to 99.98 percent on reasonably reliable hypervisors). We designed and implemented VM-μCheckpoint in the Xen VMM. The evaluation results demonstrate that VM-μCheckpoint incurs an average of 6.3 percent overhead (in terms of program execution time) for 50 ms checkpoint intervals when executing the SPEC CINT 2006 benchmark. Error injection experiments demonstrate that VM-μCheckpoint, combined with error detection techniques in RMK, provides high coverage of recovery.

In emerging information networks, having a privacy preserving index (or PPI) is critically important for locating information of interest for data sharing across autonomous providers while preserving privacy. An understudied problem for PPI techniques is how to provide controllable privacy preservation, given the innate difference of privacy concerns regarding different data owners. In this paper we present a personalized privacy preserving index, coined ε-PPI, which guarantees quantitative privacy preservation differentiated by personal identities. We devise a new common-identity attack that breaks existing PPI's and propose an identity-mixing protocol against the attack in ε-PPI. The proposed ε-PPI construction protocol is the first without any trusted third party and/or trust relationships between providers. We have implemented our ε-PPI construction protocol by using generic MPC techniques (secure multi-party computation) and optimized the performance to a practical level by minimizing the expensive MPC part.

Scale-out programs run on multiple processes in a cluster. In scale-out systems, processes can fail. Computations using traditional libraries such as MPI fail when any component process fails. The advent of Map Reduce, Resilient Data Sets and MillWheel has shown dramatic improvements in productivity are possible when a high-level programming framework handles scale-out and resilience automatically.

Disruption tolerant networks (DTNs) are characterized by low node density, unpredictable node mobility, and lack of global network information. Most of current research efforts in DTNs focus on data forwarding, but only limited work has been done on providing efficient data access to mobile users. In this paper, we propose a novel approach to support cooperative caching in DTNs, which enables the sharing and coordination of cached data among multiple nodes and reduces data access delay. Our basic idea is to intentionally cache data at a set of network central locations (NCLs), which can be easily accessed by other nodes in the network. We propose an efficient scheme that ensures appropriate NCL selection based on a probabilistic selection metric and coordinates multiple caching nodes to optimize the tradeoff between data accessibility and caching overhead. Extensive trace-driven simulations show that our approach significantly improves data access performance compared to existing schemes.

Understanding the performance difference of a multi-tier Cloud application between different provisioning plans and workloads is difficult to achieve. A typical IaaS provider offers a variety of virtual server instances with different performance capacities and rental rates. Such instances are often marked with a high level description of their hardware/software configuration (e.g. 1 or 2 vC-PUs) which provides insufficient information on the performance of the virtual server instances. Furthermore, as each tier of an application can be independently provisioned with different types and numbers of VMs, the number of possible provisioning plans grows exponentially with each additional tier.

Distributed state monitoring plays a critical role in Cloud datacenter management. One fundamental problem in distributed state monitoring is to minimize the monitoring cost while maximizing the monitoring accuracy at the same time. In this paper, we present Volley, a violation likelihood based approach for efficient distributed state monitoring in Cloud datacenters. Volley achieves both efficiency and accuracy with a flexible monitoring framework which uses dynamic monitoring intervals determined by the likelihood of detecting state violations. Volley consists of three unique techniques. It utilizes efficient node-level adaptation algorithms that minimize monitoring cost with controlled accuracy. Volley also employs a distributed scheme that coordinates the adaptation on multiple monitor nodes of the same task for optimal task- level efficiency. Furthermore, it enables multi-task level cost reduction by exploring state correlation among monitoring tasks. We perform extensive experiments to evaluate Volley with system, network and application monitoring tasks in a virtualized datacenter environment. Our results show that Volley can reduce considerable monitoring cost and still deliver user specified monitoring accuracy under various scenarios.

Keyword search has been popularly used to query graph data. Due to the lack of structure support, a keyword query might generate an excessive number of matches, referred to as "answer graphs", that could include different relationships among keywords. An ignored yet important task is to group and summarize answer graphs that share similar structures and contents for better query interpretation and result understanding. This paper studies the summarization problem for the answer graphs induced by a keyword query Q . (1) A notion of summary graph is proposed to characterize the summarization of answer graphs. Given Q and a set of answer graphs G, a summary graph preserves the relation of the keywords in Q by summarizing the paths connecting the keywords nodes in G. (2) A quality metric of summary graphs, called coverage ratio, is developed to measure information loss of summarization. (3) Based on the metric, a set of summarization problems are formulated, which aim to find minimized summary graphs with certain coverage ratio. (a) We show that the complexity of these summarization problems ranges from ptime to NP-complete. (b) We provide exact and heuristic summarization algorithms. (4) Using real-life and synthetic graphs, we experimentally verify the effectiveness and the efficiency of our techniques.

State monitoring is widely used for detecting critical events and abnormalities of distributed systems. As the scale of such systems grows and the degree of workload consolidation increases in Cloud data centers, node failures and performance interferences, especially transient ones, become the norm rather than the exception. Hence, distributed state monitoring tasks are often exposed to impaired communication caused by such dynamics on different nodes. Unfortunately, existing distributed state monitoring approaches are often designed under the assumption of always-online distributed monitoring nodes and reliable inter-node communication. As a result, these approaches often produce misleading results which in turn introduce various problems to Cloud users who rely on state monitoring results to perform automatic management tasks such as auto-scaling. This paper introduces a new state monitoring approach that tackles this challenge by exposing and handling communication dynamics such as message delay and loss in Cloud monitoring environments. Our approach delivers two distinct features. First, it quantitatively estimates the accuracy of monitoring results to capture uncertainties introduced by messaging dynamics. This feature helps users to distinguish trustworthy monitoring results from ones heavily deviated from the truth, yet significantly improves monitoring utility compared with simple techniques that invalidate all monitoring results generated with the presence of messaging dynamics. Second, our approach also adapts to non-transient messaging issues by reconfiguring distributed monitoring algorithms to minimize monitoring errors. Our experimental results show that, even under severe message loss and delay, our approach consistently improves monitoring accuracy, and when applied to Cloud application auto-scaling, outperforms existing state monitoring techniques in terms of the ability to correctly trigger dynamic provisioning.

Opportunistic mobile networks consist of personal mobile devices which are intermittently connected with each other. Data access can be provided to these devices via cooperative caching without support from the cellular network infrastructure, but only limited research has been done on maintaining the freshness of cached data which may be refreshed periodically and is subject to expiration. In this paper, we propose a scheme to efficiently maintain cache freshness. Our basic idea is to let each caching node be only responsible for refreshing a specific set of caching nodes, so as to maintain cache freshness in a distributed and hierarchical manner. Probabilistic replication methods are also proposed to analytically ensure that the freshness requirements of cached data are satisfied. Extensive trace driven simulations show that our scheme significantly improves cache freshness, and hence ensures the validity of data access provided to mobile users.

The explosion of data consumption has led to a renewed interest in byte caching. With studies showing potential reductions in network traffic of 50%, this fine grained caching technique looks like a very good and attractive solution for mobile wireless operators. However, properties of wireless networks actually present new challenges. We first show that a single packet loss, re-ordering or corruption -- all common conditions over the air interface -- can result in circular dependencies and cause existing byte caching algorithms to loop endlessly. To remedy the problem, we then explore a new set of encoding algorithms. Third, we assess the impact of packet losses on byte caching performances, both in terms of byte savings and delay reduction. We found that a mere 1% packet loss can already nullify any delay reduction and instead cause significant increases that users may not be willing to tolerate. Finally, we shared several insights, including interactions between transport layer protocol's mechanisms (e.g., TCP window congestion) and byte caching operations that can cause sophisticated encoding algorithms to perform poorly. We believe that these insights are important for designing more efficient and robust byte caching encoding algorithms.

This demonstration illustrates a service for collection and delivery of images, in participatory camera networks, to maximize coverage while removing outliers (i.e., irrelevant images). Images, such as those taken by smart-phone users, represent an important and growing modality in social sensing applications. They can be used, for instance, to document occurrences of interest in participatory sensing campaigns, such as instances of graffiti on campus or invasive species in a park. In applications with a significant number of participants, the number of images collected may be very large. A key problem becomes one of data triage to reduce the number of images delivered to a manageable count, without missing important ones. In prior work, the authors presented a service, called PhotoNet [2], that reduces redundancy among delivered images by maximizing diversity. The current work significantly extends our previous effort by recognizing that diversity maximization often leads to selection of outliers; images that are visually different but not necessarily relevant, which in fact reduces the quality of the delivered image pool. We demonstrate a new prioritization technique that maximizes diversity among delivered pictures, while also reducing outliers.

We present a highly available system for environments such as stock trading, where high request rates and low latency requirements dictate that service disruption on the order of seconds in length can be unacceptable. After a node failure, our system avoids delays in processing due to detecting the failure or transferring control to a back-up node. We achieve this by using multiple primary nodes which process transactions concurrently as peers. If a primary node fails, the remaining primaries continue executing without being delayed at all by the failed primary. Nodes agree on a total ordering for processing requests with a novel low overhead wait-free algorithm that utilizes a small amount of shared memory accessible to the nodes and a simple compare-and-swap like protocol which allows the system to progress at the speed of the fastest node. We have implemented our system and show experimentally that it performs well and can transparently handle node failures without causing delays to transaction processing. The efficient implementation of our algorithm for ordering transactions is a critically important factor in achieving good performance.

This paper introduces several novel load-balancing algorithms for distributing Session Initiation Protocol (SIP) requests to a cluster of SIP servers. Our load balancer improves both throughput and response time versus a single node while exposing a single interface to external clients. We present the design, implementation, and evaluation of our system using a cluster of Intel x86 machines running Linux. We compare our algorithms to several well-known approaches and present scalability results for up to 10 nodes. Our best algorithm, Transaction Least-Work-Left (TLWL), achieves its performance by integrating several features: knowledge of the SIP protocol, dynamic estimates of back-end server load, distinguishing transactions from calls, recognizing variability in call length, and exploiting differences in processing costs for different SIP transactions. By combining these features, our algorithm provides finer-grained load balancing than standard approaches, resulting in throughput improvements of up to 24% and response-time improvements of up to two orders of magnitude. We present a detailed analysis of occupancy to show how our algorithms significantly reduce response time.

No abstract available.

Replication is commonly used to address the scalability and availability requirements of collaborative web applications in domains such as computer supported cooperative work, social networking, e-commerce and e-banking. While providing substantial benefits, replication also introduces the ov

Disruption Tolerant Networks (DTNs) are characterized by the low node density, unpredictable node mobility and lack of global network information. Most of current research efforts in DTNs focus on data forwarding, but only limited work has been done on providing effective data access to mobile users. In this paper, we propose a novel approach to support cooperative caching in DTNs, which enables the sharing and coordination of cached data among multiple nodes and reduces data access delay. Our basic idea is to intentionally cache data at a set of Network Central Locations (NCLs), which can be easily accessed by other nodes in the network. We propose an effective scheme which ensures appropriate NCL selection based on a probabilistic selection metric, and coordinate multiple caching nodes to optimize trade off between data accessibility and caching overhead. Extensive trace-driven simulations show that our scheme significantly improves data access performance compared to existing schemes.

We present the design, optimization and analysis of a highly flexible and efficient multi-leg stock trading system. Automated electronic multi-leg trading allows atomic processing of consolidated orders such as "Buy 200 shares of IBM and sell 100 shares of HPQ". While the expressive power of multi-leg trading brings significant value to investors, it also poses major challenges to stock exchange architecture design, due to additional complexities introduced in performance, tradability, and fairness. Performance can be significantly worse due to the need to coordinate transactions among multiple stocks at once. This paper studies the performance of multi-leg trading under different fairness constraints and variability in order price and order quantity. We identify the major performance bottlenecks when using traditional atomic commitment protocols such as 2-Phase Commit (2PC), and propose a new look-ahead algorithm to maximize transaction concurrency and minimize performance degradation. We have implemented a base-line 2PC prototype and a look-ahead optimized prototype on IBM z10 z Series e Server mainframes. Our experimental results show that the look-ahead optimization can improve throughput by 58% and reduce latency by 30%.

Dynamic application placement for clustered web applications heavily influences system performance and quality of user experience. Existing approaches claim that they strive to maximize the throughput, keep resource utilization balanced across servers, and minimize the start/stop cost of application instances. However, they fail to minimize the worst case of server utilization; the load balancing performance is not optimal. What's more, some applications need to communicate with each other, which we called dependent applications; the network cost of them also should be taken into consideration. In this paper, we investigate how to minimize the resource utilization of servers in the worst case, aiming at improving load balancing among clustered servers. Our contribution is two-fold. First we propose and define a new optimization objectives: limiting the worst case of each individual server's utilization, formulated by a min-max problem. A novel framework based on binary search is proposed to detect an optimal load balancing solution. Second, we define system cost as the weighted combination of both placement change and inter-application communication cost. By maximizing the number of instances of dependent applications that reside in the same set of servers, the basic load-shifting and placement-change procedures are enhanced to minimize whole system cost. Extensive experiments have been conducted and effectively demonstrate that: 1) the proposed framework achieves a good allocation for clustered web applications. In other words, requests are evenly allocated among servers, and throughput is still maximized; 2) the total system cost maintains at a low level; 3) our algorithm has the capacity of approximating an optimal solution within polynomial time and is promising for practical implementation in real deployments.

Publish-subscribe (pub-sub) is an emerging paradigm for building a large number of distributed systems. A wide area pub-sub system is usually implemented on an overlay network infrastructure to enable information dissemination from publishers to subscribers. Using an open overlay network raises several security concerns such as: confidentiality and integrity, authentication, authorization and Denial-of-Service (DoS) attacks. In this article we present EventGuard, a framework for building secure wide-area pub-sub systems. The EventGuard architecture is comprised of three key components: (1) a suite of security guards that can be seamlessly plugged-into a content-based pub-sub system, (2) a scalable key management algorithm to enforce access control on subscribers, and (3) a resilient pub-sub network design that is capable of scalable routing, handling message dropping-based DoS attacks, and node failures. The design of EventGuard mechanisms aims at providing security guarantees while maintaining the system’s overall simplicity, scalability, and performance metrics. We describe an implementation of the EventGuard pub-sub system to show that EventGuard is easily stackable on any content-based pub-sub core. We present detailed experimental results that quantify the overhead of the EventGuard pub-sub system and demonstrate its resilience against various attacks.

(A short version of this paper appears in IEEE INFOCOM 2009: http://www.research.ibm.com/people/i/iyengar/INFOCOM2009-kanon.pdf.) Peer-to-peer VoIP (voice over IP) networks, exemplified by Skype, are becoming increasingly popular due to their significant cost advantage and richer call forwarding features than traditional public switched telephone networks. One of the most important features of a VoIP network is privacy (for VoIP clients). Unfortunately, most peer-to-peer VoIP networks neither provide personalization nor guarantee a quantifiable privacy level. In this paper, we propose novel flow analysis attacks that demonstrate the vulnerabilities of peer-to-peer VoIP networks to privacy attacks. We then address two important challenges in designing privacy-aware VoIP networks: Can we provide personalized privacy guarantees for VoIP clients that allow them to select privacy requirements on a per-call basis? How to design VoIP protocols to support customizable privacy guarantee? This paper proposes practical solutions to address these challenges using a quantifiable k-anonymity metric and a privacy-aware VoIP route setup and route maintenance protocols. We present detailed experimental evaluation that demonstrates the performance and scalability of our protocol, while meeting customizable privacy guarantees.

To tackle SOA projects that span across various boundaries, enterprises are adopting a federated SOA approach in order to manage reuse across service domains. Managing service reuse involves sharing a subset of the services that are provided within a domain and fulfilling references to services required by applications or other services in a domain. While this is a major goal, it is also important for a federated enterprise to enable the autonomy of its multiple service domains. This paper proposes an approach for cross-domain service management that enables domain autonomy and that preserves across domains properties that are taken for granted by services within a domain. We introduce a cross-domain service management capability and show how this capability allows for services to be shared and reused without the need for a federation architect, and how it preserves intra-domain properties, thus enabling domain autonomy in a federation.

This paper proposes an approach for cross-domain connectivity that enables domain autonomy and that preserves across domains properties that are taken for granted by services within a domain.

This paper proposes VM-μCheckpoint, a lightweight software mechanism for high-frequency checkpointing and rapid recovery of virtual machines. VM-μCheckpoint minimizes checkpoint overhead and speeds up recovery by saving incremental checkpoints in volatile memory and by employing copy-on-write, dirty-page prediction, and in-place recovery. In our approach, knowledge of fault/error latency is used to explicitly address checkpoint corruption, a critical problem, especially when checkpoint frequency is high. We designed and implemented VM-μCheckpoint in the Xen VMM. The evaluation results demonstrate that VM-μCheckpoint incurs an average of 6.3% execution-time overhead for 50ms checkpoint intervals when executing the SPEC CINT 2006 benchmark.

Subtle implementation errors or mis-configurations in complex Internet services may lead to performance degradations without causing failures. These undiscovered performance anomalies afflict many of today's systems, causing violations of service-level agreements (SLAs), unnecessary resource over provisioning, or both. In this paper, we re-inserted realistic anomaly causes into a multi-tier Internet service architecture and studied their manifestations. We observed that each cause had certain workload and management parameters that were more likely to trigger manifestations, hinting that such parameters could be effective classifiers. This observation held even when anomaly causes manifested differently in combination than in isolation. Our study motivates EntomoModel, a framework for depicting performance anomaly manifestations. EntomoModel uses decision tree classification and a design-driven performance model to characterize the workload and management policy settings under which manifestations are likely. EntomoModel enables online system management that avoids anomaly manifestations by dynamically adjusting system management parameters. Our trace-driven evaluations show that manifestation avoidance based on EntomoModel, or entomophobic management, can reduce 98th percentile SLA violations by 67% compared to an anomaly oblivious adaptive approach. In a cloud computing scenario with elastic resource allocation, our approach uses less than half of the resources needed in static over-provisioning.

Mobile commerce and location based services (LBS) are some of the fastest growing IT industries in the last five years. Location update of mobile clients is a fundamental capability in mobile commerce and all types of LBS. Higher update frequency leads to higher accuracy, but incurs unacceptably high cost of location management at the location servers. We propose RoadTrack -- a road-network based, query-aware location update framework with two unique features. First, we introduce the concept of precincts to control the granularity of location update resolution for mobile clients that are not of interest to any active location query services. Second, we define query encounter points for mobile objects that are targets of active location query services, and utilize these encounter points to define the adequate location update schedule for each mobile. The RoadTrack framework offers three unique advantages. First, encounter points as a fundamental query awareness mechanism enable us to control and differentiate location update strategies for mobile clients in the vicinity of active location queries, while meeting the needs of location query evaluation. Second, we employ system-defined precincts to manage the desired spatial resolution of location updates for different mobile clients and to control the scope of query awareness to be capitalized by a location update strategy. Third, our road-network based check-free interval optimization further enhances the effectiveness of the Road-Track query-aware location update scheduling algorithm. This optimization provides significant cost reduction for location update management at both mobile clients and location servers. We evaluate the RoadTrack location update approach using a real world road-network based mobility simulator. Our experimental results demonstrate that the RoadTrack query aware location update approach outperforms existing representative location update strategies in terms of both client energy efficiency and server processing load.

This paper introduces dual-quorum replication, a novel data replication algorithm designed to support Internet edge services. Edge services allow clients to access Internet services via distributed edge servers that operate on a shared collection of underlying data. Although it is generally difficult to share data while providing high availability, good performance, and strong consistency, replication algorithms designed for specific access patterns can offer nearly ideal trade-offs among these metrics. In this paper, we focus on the key problem of sharing read/write data objects across a collection of edge servers when the references to each object 1) tend not to exhibit high concurrency across multiple nodes and 2) tend to exhibit bursts of read-dominated or write-dominated behavior. Dual-quorum replication combines volume leases and quorum-based techniques to achieve excellent availability, response time, and consistency for such workloads. In particular, through both analytical and experimental evaluations, we show that the dual-quorum protocol can (for the workloads of interest) approach the optimal performance and availability of Read-One/Write-All-Asynchronously (ROWA-A) epidemic algorithms without suffering the weak consistency guarantees and resulting design complexity inherent in ROWA-A systems.

Spatial alarms are considered as one of the basic capabilities in future mobile computing systems for enabling personalization of location-based services. In this paper, we propose a distributed architecture and a suite of safe region techniques for scalable processing of spatial alarms. We show that safe region-based processing enables resource optimal distribution of partial alarm processing tasks from the server to the mobile clients. We propose three different safe region computation algorithms to explore the impact of size and shape of the safe region on network bandwidth, server load and client energy consumption. Concretely, we show that the maximum weighted perimeter rectangular safe region approach outperforms previous techniques in terms of performance and accuracy. We further explore finer granularity safe regions by introducing grid-based and pyramid-based representation of rectilinear polygonal shapes using bitmap encoding. Our experimental evaluation shows that the distributed safe region-based architecture outperforms the two most popular server-centric approaches, periodic and safe period-based, for spatial alarm processing.

This paper introduces several novel load balancing algorithms for distributing session initiation protocol (SIP) requests to a cluster of SIP servers. Our load balancer improves both throughput and response time versus a single node, while exposing a single interface to external clients. We present the design, implementation and evaluation of our system using a cluster of Intel x86 machines running Linux. We compare our algorithms with several well-known approaches and present scalability results for up to 10 nodes. Our best algorithm, transaction least-work-left (TLWL), achieves its performance by integrating several features: knowledge of the SIP protocol; dynamic estimates of back-end server load; distinguishing transactions from calls; recognizing variability in call length; and exploiting differences in processing costs for different SIP transactions. By combining these features, our algorithm provides finer-grained load balancing than standard approaches, resulting in throughput improvements of up to 24 percent and response time improvements of up to two orders of magnitude. We present a detailed analysis of occupancy to show how our algorithms significantly reduce response time.

Peer-to-peer VoIP (voice over IP) networks, exemplified by Skype, are becoming increasingly popular due to their significant cost advantage and richer call forwarding features than traditional public switched telephone networks. One of the most important features of a VoIP network is privacy (for VoIP clients). Unfortunately, most peer-to-peer VoIP networks neither provide personalization nor guarantee a quantifiable privacy level. In this paper we propose novel flow analysis attacks that demonstrate the vulnerabilities of peer-to-peer VoIP networks to privacy attacks. We present detailed experimental evaluation that demonstrates these attacks quantifying performance and scalability degradation.

Many reputation management systems have been developed under the assumption that each entity in the system will use a variant of the same scoring function. Much of the previous work in reputation management has focused on providing robustness and improving performance for a given reputation scheme. In this paper, we present a reputation-based trust management framework that supports the synthesis of trust-related feedback from many different entities while also providing each entity with the flexibility to apply different scoring functions over the same feedback data for customized trust evaluations. We also propose a novel scheme to cache trust values based on recent client activity. To evaluate our approach, we implemented our trust management service and tested it on a realistic application scenario in both LAN and WAN distributed environments. Our results indicate that our trust management service can effectively support multiple scoring functions with low overhead and high availability.

One important problem for public broadcast Location-Based Services (LBS) is to enforce access control on a large number of subscribers. In such a system a user typically subscribes to a LBS for a time interval (a, b) and a spatial region (xbl, ybl, xir, ytr) according to a 3-dimensional spatial-temporal authorization model. In this paper, we argue that current approaches to access control using group key management protocols are not scalable. Our proposal STauth minimizes the number of keys which needs to be distributed and is thus scalable to a much higher number of subscribers and the dimensionality of the authorization model. We analytically and experimentally demonstrate the performance and scalability benefits of our approach against other group key management protocols.

Applications such as VoIP need to provide anonymity to clients while maintaining low latency to satisfy quality of service (QoS) requirements. Existing solutions for providing anonymity such as mix networks are not well suited to applications like VoIP, SSH, and gaming which require low communication latency. This paper investigates the problem of on-demand construction of QoS sensitive routes on anonymizing networks using the VoIP application. We first describe triangulation based timing analysis attacks on shortest path route set up protocols. We show that even when a small fraction (~1%) of the network is malicious, the adversary can infer the source (caller) with reasonably high probability. Second, we describe random walk based route set up protocols that significantly improve anonymity while satisfying latency- based QoS guarantees. We describe a prototype implementation of our proposal and show that our protocols can significantly reduce the probability of inferring the caller. We present a detailed experimental evaluation to demonstrate our attacks and quantify the performance and scalability of our guards.

Recently, we have seen increasing numbers of denial of service (DoS) attacks against online services and Web applications either for extortion reasons or for impairing and even disabling the competition. These DoS attacks have increasingly targeted the application level. Application-level DoS attacks emulate the same request syntax and network-level traffic characteristics as those of legitimate clients, thereby making the attacks much harder to detect and counter. Moreover, such attacks often target bottleneck resources such as disk bandwidth, database bandwidth, and CPU resources. In this article, we propose handling DoS attacks by using a twofold mechanism. First, we perform admission control to limit the number of concurrent clients served by the online service. Admission control is based on port hiding that renders the online service invisible to unauthorized clients by hiding the port number on which the service accepts incoming requests. Second, we perform congestion control on admitted clients to allocate more resources to good clients. Congestion control is achieved by adaptively setting a client's priority level in response to the client's requests in a way that can incorporate application-level semantics. We present a detailed evaluation of the proposed solution using two sample applications: Apache HTTPD and the TPCW benchmark (running on Apache Tomcat and IBM DB2). Our experiments show that the proposed solution incurs low performance overhead and is resilient to DoS attacks.

Service composition has emerged as a fundamental technique for developing Web applications. Multiple services, often from different organizations or trust domains, may be dynamically composed to satisfy a user's request. Access control in the presence of service compositions is a challenging security problem. In this paper, we present an access control model and techniques for specifying and enforcing access control rules on Web service compositions. A key advantage of our approach is that past histories of service invocations can be used to make access control decisions. Our approach allows role hierarchies and separation of duty constraints. Access controls rules may be parameterized by one or more arguments. We have implemented our access control model via a declarative policy specification language which uses pure-past linear temporal logic (PPLTL). We describe an implementation of our approach using a supply chain management (SCM) application. Our experiments show that our approach can enforce expressive and flexible access control policies while incurring reasonable performance overhead on the application.

In recent years, edge computing has emerged as a popular mechanism to deliver dynamic Web content to clients. However, many existing edge cache networks have not been able to harness the full potential of edge computing technology. In this paper, we argue and experimentally demonstrate that cooperation among the individual edge caches coupled with scalable server-driven document consistency mechanisms can significantly enhance the capabilities and performance of edge cache networks in delivering fresh dynamic content. However, designing large-scale cooperative edge cache networks presents many research challenges. Toward addressing these challenges, this paper presents cooperative edge cache grid (cooperative EC grid, for short)-a large-scale cooperative edge cache network for efficiently delivering highly dynamic Web content with varying server update frequencies. The design of the cooperative EC grid focuses on the scalability and reliability of dynamic content delivery in addition to cache hit rates, and it incorporates several novel features. We introduce the concept of cache clouds as a generic framework of cooperation in large-scale edge cache networks. The architectural design of the cache clouds includes dynamic hashing-based document lookup and update protocols, which dynamically balance lookup and update loads among the caches in the cloud. We also present cooperative techniques for making the document lookup and update protocols resilient to the failures of individual caches. This paper reports a series of simulation-based experiments which show that the overheads of cooperation in the cooperative EC grid are very low, and our architecture and techniques enhance the performance of the cooperative edge networks.

No abstract available.

Cooperation among individual caches has proven to be an effective strategy to improve the scalability and performance of edge cache networks delivering dynamic Web content. To date, research in the area of cooperative edge caching has mainly focused on serving client requests and maintaining freshness of cached documents. However, designing mechanisms to effectively manage the available resources is an important challenge that can have significant impact on the performance of an edge cache network. In this paper we propose a novel data placement scheme, called the utility-based placement scheme, which is not only sensitive to the ongoing cooperation in the edge cache but also takes into account the various costs and benefits of storing a data-item at an individual edge cache. At the heart of proposed scheme is a utility function that quantifies the usefulness of storing a data-item at a particular edge cache. Experiments show that the proposed scheme provides significant performance benefits

Transaction processing systems lie at the core of modern e-commerce applications such as on-line retail stores, banks and airline reservation systems. The economic success of these applications depends on the ability to achieve high user satisfaction, since a single mouse-click is all that it takes a frustrated user to switch to a competitor. Given that system resources are limited and demands are varying, it is difficult to provide optimal performance to all users at all times. However, often transactions can be divided into different classes based on how important they are to the online retailer. For example, transactions initiated by a "big spending" client are more important than transactions from a client that only browses the site. A natural goal then is to ensure short delays for the class of important transactions, while for the less important transactions longer delays are acceptable.

Scheduling/prioritization of DBMS transactions is important for many applications that rely on database backends. A convenient way to achieve scheduling is to limit the number of transactions within the database, maintaining most of the transactions in an external queue, which can be ordered as desired by the application. While external scheduling has many advantages in that it doesn’t require changes to internal resources, it is also difficult to get right in that its performance depends critically on the particular multiprogramming limit used (the MPL), i.e. the number of transactions allowed into the database. If the MPL is too low, throughput will suffer, since not all DBMS resources will be utilized. On the other hand, if the MPL is too high, there is insufficient control on scheduling. The question of how to adjust theMPL to achieve both goals simultaneously is an open problem, not just for databases but in system design in general. Herein we study this problem in the context of transactional workloads, both via extensive experimentation and queueing theoretic analysis. We find that the two most critical factors in adjusting the MPL are the number of resources that the workload utilizes and the variability of the transactions’ service demands. We develop a feedback based controller, augmented by queueing theoretic models for automatically adjusting the MPL. Finally, we apply our methods to the specific problem of external prioritization of transactions. We find that external prioritization can be nearly as effective as internal prioritization, without any negative consequences, when the MPL is set appropriately.

Denial of service (DoS) attacks attempt to consume a server's resources (network bandwidth, computing power, main memory, disk bandwidth etc.) to near exhaustion so that there are no resources left to handle requests from legitimate clients. An effective solution to defend against DoS attacks is to filter DoS attack requests at the earliest point (say, the Web site's firewall), before they consume much of the server's resources. Most defenses against DoS attacks attempt to filter requests from inauthentic clients before they consume much of the server's resources. Client authentication using techniques like IPSec or SSL may often require changes to the client-side software and may additionally require superuser privileges at the client for deployment. Further, using digital signatures (as in SSL) makes verification very expensive, thereby making the verification process itself a viable DoS target for the adversary. In this paper, we propose a light-weight client transparent technique to defend against DoS attacks with two unique features: (i) Our technique can be implemented entirely using JavaScript support provided by a standard client-side browser like Mozilla FireFox or Microsoft Internet Explorer. Client transparency follows from the fact that: (i) no changes to client-side software are required, (ii) no client-side superuser privileges are required, and (iii) clients (human beings or automated clients) can browse a DoS protected Web site in the same manner that they browse other Web sites, (ii) Although we operate using the client-side browser (HTTP layer), our technique enables fast IP level packet filtering at the server's firewall and requires no changes to the application(s) hosted by the Web server. In this paper we present a detailed design of our technique along with a detailed security analysis. We also describe a concrete implementation of our proposal on the Linux kernel and present an evaluation using two applications: bandwidth intensive Apache HTTPD and database intensive TPCW. Our experiments show that our approach incurs a low performance overhead and is resilient to DoS attacks

Caching on the edge of the Internet is becoming a popular technique to improve the scalability and efficiency of delivering dynamic web content. In this paper we study the challenges in designing a large scale cooperative edge cache network, focusing on mechanisms and methodologies for efficient cooperation among caches to improve the overall performance of the edge cache network. This paper makes three original contributions. First, we introduce the concept of cache clouds, which forms the fundamental framework for cooperation among caches in the edge network. Second, we present dynamic hashing-based protocols for document lookups and updates within each cache cloud, which are not only efficient, but also effective in dynamically balancing lookup and update loads among the caches in the cloud. Third, we outline a utility-based mechanism for placing dynamic documents within a cache cloud. Our experiments indicate that these techniques can significantly improve the performance of the edge cache networks.

Distributed applications composed of collections of Web services may call for diverse levels of reliability in different parts of the system. Byzantine fault tolerance (BFT) is a general strategy that has recently been shown to be practical for the development of certain classes of survivable, client-server, distributed applications; however, little research has been done on incorporating it into selective parts of multi-tier, distributed applications like Web services that have heterogeneous reliability requirements. To understand the impacts of combining BFT and Web services, we have created Thema, a new BFT middleware system that extends the BFT and Web services technologies to provide a structured way to build Byzantine-fault-tolerant, survivable Web services that application developers can use like other Web services. From a reliability perspective, our enhancements are also novel in that they allow Byzantine-fault-tolerant services: (1) to support the multi-tiered requirements of Web services, and (2) to provide standardized Web services support for their own clients (through WSDL interfaces and SOAP communication). In this paper we study key architectural implications of combining BFT with Web services and provide a performance evaluation of Thema using the TPC-W benchmark.

The emerging edge services architecture promises to improve the availability and performance of Web services by replicating servers at geographically distributed sites. A key challenge in such systems is data replication and consistency, so that edge server code can manipulate shared data without suffering the availability and performance penalties that would be incurred by accessing a traditional centralized database. This work explores using a distributed object architecture to build an edge service data replication system for an e-commerce application, the TPC-W benchmark, which simulates an online bookstore. We take advantage of application-specific semantics to design distributed objects that each manages a specific subset of shared information using simple and effective consistency models. Our experimental results show that by slightly relaxing consistency within individual distributed objects, our application realizes both high availability and excellent performance. For example, in one experiment, we find that our object-based edge server system provides five times better response time over a traditional centralized cluster architecture and a factor of nine improvement over an edge service system that distributes code but retains a centralized database.

Constructing Web pages from fragments has been shown to provide significant benefits for both content generation and caching. In order for a Web site to use fragment-based content generation, however, good methods are needed for fragmenting the Web pages. Manual fragmentation of Web pages is expensive, error prone, and unscalable. This paper proposes a novel scheme to automatically detect and flag fragments that are cost-effective cache units in Web sites serving dynamic content. Our approach analyzes Web pages with respect to their information sharing behavior, personalization characteristics, and change patterns. We identify fragments which are shared among multiple documents or have different lifetime or personalization characteristics. Our approach has three unique features. First, we propose a framework for fragment detection, which includes a hierarchical and fragment-aware model for dynamic Web pages and a compact and effective data structure for fragment detection. Second, we present an efficient algorithm to detect maximal fragments that are shared among multiple documents. Third, we develop a practical algorithm that effectively detects fragments based on their lifetime and personalization characteristics. This paper shows the results when the algorithms are applied to real Web sites. We evaluate the proposed scheme through a series of experiments, showing the benefits and costs of the algorithms. We also study the impact of using the fragments detected by our system on key parameters such as disk space utilization, network bandwidth consumption, and load on the origin servers.

This article presents a publishing system for efficiently creating dynamic Web content. Complex Web pages are constructed from simpler fragments. Fragments may recursively embed other fragments. Relationships between Web pages and fragments are represented by object dependence graphs. We present algorithms for efficiently detecting and updating Web pages affected after one or more fragments change. We also present algorithms for publishing sets of Web pages consistently; different algorithms are used depending upon the consistency requirements.Our publishing system provides an easy method for Web site designers to specify and modify inclusion relationships among Web pages and fragments. Users can update content on multiple Web pages by modifying a template. The system then automatically updates all Web pages affected by the change. Our system accommodates both content that must be proofread before publication and is typically from humans as well as content that has to be published immediately and is typically from automated feeds.We discuss some of our experiences with real deployments of our system as well as its performance. We also quantitatively present characteristics of fragments used at a major deployment of our publishing system including fragment sizes, update frequencies, and inclusion relationships.

Dividing web pages into fragments has been shown to provide significant benefits for both content generation and caching. In order for a web site to use fragment-based content generation, however, good methods are needed for dividing web pages into fragments. Manual fragmentation of web pages is expensive, error prone, and unscalable. This paper proposes a novel scheme to automatically detect and flag fragments that are cost-effective cache units in web sites serving dynamic content. We consider the fragments to be interesting if they are shared among multiple documents or they have different lifetime or personalization characteristics. Our approach has three unique features. First, we propose a hierarchical and fragment-aware model of the dynamic web pages and a data structure that is compact and effective for fragment detection. Second, we present an efficient algorithm to detect maximal fragments that are shared among multiple documents. Third, we develop a practical algorithm that effectively detects fragments based on their lifetime and personalization characteristics. We evaluate the proposed scheme through a series of experiments, showing the benefits and costs of the algorithms. We also study the impact of adopting the fragments detected by our system on disk space utilization and network bandwidth consumption.

We present architectures and algorithms for efficiently serving dynamic data at highly accessed Web sites together with the results of an analysis motivating our design and quantifying its performance benefits. This includes algorithms for keeping cached data consistent so that dynamic pages can be cached at the Web server and dynamic content can be served at the performance level of static content. We show that our system design is able to achieve cache hit ratios close to 100% for cached data which is almost never obsolete by more than a few seconds, if at all. Our architectures and algorithms provide more than an order of magnitude improvement in performance using an order of magnitude fewer servers over that obtained under conventional methods.

The existing approaches to fragment-based publishing, delivery and caching of web pages assume that the web pages are manually fragmented at their respective web sites. However manual fragmentation of web pages is expensive, error prone, and not scalable. This paper proposes a novel scheme to automatically detect and flag possible fragments in a web site. Our approach is basedonananalysisofthewebpagesdynamicallygeneratedat given web sites with respect to their information sharing behavior, personalization characteristics and change patterns. Categories and Subject Descriptors: H.3.3 [Information Systems- Information storage and retrieval]: Information search and retrieval

The emerging edge services architecture promises to improve the availability and performance of web services by replicating servers at geographically distributed sites. A key challenge in such systems is data replication and consistency so that edge server code can manipulate shared data without incurring the availability and performance penalties that would be incurred by accessing a traditional centralized database. This paper explores using a distributed object architecture to build an edge service system for an e-commerce application, an online bookstore represented by the TPC-W benchmark. We take advantage of application specific semantics to design distributed objects to manage a specific subset of shared information using simple and effective consistency models. Our experimental results show that by slightly relaxing consistency within individual distributed objects, we can build an edge service system that is highly available and efficient. For example, in one experiment we find that our object-based edge server system provides a factor of five improvement in response time over a traditional centralized cluster architecture and a factor of nine improvement over an edge service system that distributes code but retains a centralized database.

Internet streaming applications are affected by adverse network conditions such as high packet loss rates and long delays. This paper aims at mitigating such effects by leveraging the availability of client-side caching proxies. We present a novel caching architecture and associated cache management algorithms that turn edge caches into accelerators of streaming media delivery. A salient feature of our caching algorithms is that they allow partial caching of streaming media objects and joint delivery of content from caches and origin servers. The caching algorithms we propose are both network-aware and stream-aware; they take into account the popularity of streaming media objects, their bit-rate requirements, and the available bandwidth between clients and servers. Using realistic models of Internet bandwidth derived from proxy cache logs and measured over real Internet paths, we have conducted simulations to evaluate the performance of various cache management alternatives. Our experiments demonstrate that network-aware caching algorithms can significantly reduce service delay and improve overall stream quality. Our experiments also show that partial caching is particularly effective when bandwidth variability is not very high.

Server-driven consistency protocols can reduce read latency and improve data freshness for a given network and server overhead, compared to the traditional consistency protocols that rely on client polling. Server-driven consistency protocols appear particularly attractive for large-scale dynamic Web workloads because dynamically generated data can change rapidly and unpredictably. However, there have been few reports on engineering server-driven consistency for such workloads. This article reports our experience in engineering server-driven consistency for a sporting and event Web site hosted by IBM, one of the most popular sites on the Internet for the duration of the event. We also examine an e-commerce site for a national retail store. Our study focuses on scalability and cachability of dynamic content. To assess scalability, we measure both the amount of state that a server needs to maintain to ensure consistency and the bursts of load in sending out invalidation messages when a popular object is modified. We find that server-driven protocols can cap the size of the server's state to a given amount without significant performance costs, and can smooth the bursts of load with minimal impact on the consistency guarantees. To improve performance, we systematically investigate several design issues for which prior research has suggested widely different solutions, including whether servers should send invalidations to idle clients. Finally, we quantify the performance impact of caching dynamic data with server-driven consistency protocols and the benefits of server-driven consistency protocols for large-scale dynamic Web services. We find that (i) caching dynamically generated data can increase cache hit rates by up to 10%, compared to the systems that do not cache dynamically generated data; and (ii) server-driven consistency protocols can increase cache hit rates by a factor of 1.5-3 for large-scale dynamic Web services, compared to client polling protocols. We have implemented a prototype of a server-driven consistency protocol based on our findings by augmenting the popular Squid cache.

Many researchers have shown that server-driven consistency protocols can potentially reduce read latency. Server-driven consistency protocols are particularly attractive for large-scale dynamic web workloads because dynamically generated data can change rapidly and unpredictably. However, there have been no reports on engineering server-driven consistency for such a workload. This paper reports our experience in engineering server-driven consistency for a Sporting and Eventweb site hosted by IBM, one of the most popular web sites on the Internet for the duration of the event. Our study focuses on scalability and cachability of dynamic content. To assess scalability, we measure both the amount of state that a server needs to maintain to ensure consistency and the bursts of load that a server sustains to send out invalidation messages when a popular object is modified. We find that it is possible to limit the size of the server's state without significant performance costs and that bursts of load can be smoothed out with minimal impact on the consistency guarantees. To improve performance, we systematically investigate several design issues for which prior research has suggested widely different solutions, including how long servers should send invalidations to idle clients. Finally, we quantify the performance impact of caching dynamic data with server-driven consistency protocols and find that it can reduce read latency by more than 10%. We have implemented a prototype of a server-driven consistency protocol based on our findings on top of the popular Squid cache.

This paper presents a publishing system for efficiently creating dynamic Web content. Complex Web pages are constructed from simpler fragments. Fragments may recursively embed other fragments. Relationships between Web pages and fragments are represented by object dependence graphs. We present algorithms for efficiently detecting and updating Web pages affected after one or more fragments change. We also present algorithms for publishing sets of Web pages consistently; different algorithms are used depending upon the consistency requirements. Our publishing system provides an easy method for Web site designers to specify and modify inclusion relationships among Web pages and fragments. Users can update content on multiple Web pages by modifying a template. The system then automatically updates an Web pages affected by the change. Our system accommodates both content that must be proof-read before publication and is typically from humans as well as content that has to be published immediately and is typically from automated feeds. Our system is deployed at several popular Web sites including the 2000 Olympic Games Web site. We discuss some of our experiences with real deployments of our system as well as its performance.

We study design alternatives for, and describe implementations and performance of, a scalable and highly available Web server accelerator. The accelerator runs under an embedded operating system and improves Web server performance by caching data. The basic design alternatives include a content router or a TCP router (without content routing) in front of a set of Web cache accelerator nodes, with the cache memory distributed across the accelerator nodes. Content based routing reduces cache node CPU cycles but can make the front-end router a bottleneck. With the TCP router, a request for a cached object may initially be sent to the wrong cache node; this results in larger cache node CPU cycles, but can provide a higher aggregate throughput, because the TCP router becomes a bottleneck at a higher throughput than the content router. Based on measurement of implementations, we quantify the throughput ranges in which different designs are preferable. We also examine a combination of content based and TCP routing techniques. We examine optimizations, such as different communication and data delivery methods, replication of hot objects, and cache replacement policies that take into account the fact that there might be different bottlenecks in the system at different times; depending upon which resource is likely to become a bottleneck, a different cache replacement algorithm is applied.

This paper presents a new approach for consistently caching dynamic Web data in order to improve performance. Our algorithm, which we call data update propagation (DUP), maintains data dependence information between cached objects and the underlying data which affect their values in a graph. When the system becomes aware of a change to underlying data, graph traversal algorithms are applied to determine which cached objects are affected by the change. Cached objects which are found to be highly obsolete are then either invalidated or updated. The DUP was a critical component at the official Web site for the 1998 Olympic Winter Games. By using DUP, we were able to achieve cache hit rates close to 100% compared with 80% for an earlier version of our system which did not employ DUP. As a result of the high cache hit rates, the Olympic Games Web site was able to serve data quickly even during peak request periods.

We describe the design, implementation and performance of a Web server accelerator which runs on an embedded operating system and improves Web server performance by caching data. The accelerator resides in front of one or more Web servers. Our accelerator can serve up to 5000 pages/second from its cache on a 200 MHz PowerPC 604. This throughput is an order of magnitude higher than that which would be achieved by a high-performance Web server running on similar hardware under a conventional operating system such as Unix or NT. The superior performance of our system results in part from its highly optimized communications stack. In order to maximize hit rates and maintain updated caches, our accelerator provides an API which allows application programs to explicitly add, delete, and update cached data. The API allows our accelerator to cache dynamic as well as static data, analyze the SPECweb96 benchmark, and show that the accelerator can provide high hit ratios and excellent performance for workloads similar to this benchmark.

This paper describes a General-Purpose Software cache (GPS cache) which can improve the performance of many applications including Web servers and databases. It can service several hundred thousand cache hits per second on a uniprocessor. When used to cache data for a Web server accelerator, the overhead due to the GPS cache was an insignificant factor in the overall performance of the system. The GPS cache can store objects in memory, on disk, or both. The cache uses a new algorithm for managing expiration times of cached objects which is more efficient than previous ones. The GPS cache uses Data Update Propagation (DUP) to invalidate complex objects which is crucial for caching and maintaining updated copies of dynamic Web pages. Transactions can be logged using different buffering mechanisms in order to provide a balance between efficiency and currency of transaction log files. The GPS cache provides API functions which allow applications to directly manipulate its contents.

Virtual malls allow consumers to shop and purchase products on the World Wide Web from multiple stores. The paper presents a virtual mall in which stores may be distributed across multiple Web sites. Stores participate in the virtual mall by communicating with a mall coordinator. The virtual mall allows shoppers to perform actions across multiple stores simultaneously such as viewing product availability. Multiple purchases across different stores can be coordinated using multi-phase commits. The mall coordinator can authenticate clients on all stores participating in the virtual mall while only requiring clients to provide authentication information once. State information is preserved using dynamic argument embedding which is compatible with all browsers and servers supporting HTTP and is less obtrusive than cookies. The distributed virtual mall concept and infrastructure can be applied to other distributed electronic commerce applications on the Web.

We develop a general methodology for characterizing Web server access patterns based on a spectral analysis of finite collections of observed data from real systems. Our approach is used together with the access logs from the IBM Web site for the 1996 Olympic Games to demonstrate some of its advantages over previous methods and to analyze certain aspects of large-scale Web server performance.

This paper describes the system and key techniques used for achieving performance and high availability at the official Web site for the 1998 Olympic Winter Games which was one of the most popular Web sites for the duration of the Olympic Games. The Web site utilized thirteen SP2 systems scattered around the globe containing a total of 143 processors. A key feature of the Web site was that the data being presented to clients was constantly changing. Whenever new results were entered into the system, updated Web pages reflecting the changes were made available to the rest of the world within seconds. One technique we used to serve dynamic data efficiently to clients was to cache dynamic pages so that they only had to be generated once. We developed and implemented a new algorithm we call Data Update Propagation (DUP) which identifies the cached pages that have become stale as a result of changes to underlying data on which the cached pages depend, such as databases. For the Olympic Games Web site, we were able to update stale pages directly in the cache which obviated the need to invalidate them. This allowed us to achieve cache hit rates of close to 100%. Our system was able to serve pages to clients quickly during the entire Olympic Games even during peak periods. In addition, the site was available 100% of the time. We describe the keyfeatures employed by our site for high availability. We also describe how the Web site was structured to provide useful information while requiring clients to examine only a small number of pages.

Parallel algorithms for analyzing DNA and protein sequences are becoming increasingly important as sequence data continues to grow. This paper examines the parallel characteristics of four sequence alignment algorithms. The four algorithms presented are the dynamic programming algorithm developed by Needleman, Wunsch, and Sellers (the NWS algorithm), Fickett's algorithm, a parallel algorithm using some of Fickett's ideas, and an algorithm which uses some of Wilbur and Lipman's ideas for constructing alignments which are not always optimal. The NWS algorithm contains the most parallelism but also does more work than any of the other algorithms which we studied. Fickett's algorithm contains the least parallelism. However, a parallel algorithm which requires significantly fewer instructions than the NWS algorithm is obtained by modifying Fickett's algorithm. The algorithms have been implemented for a dataflow computer in the dataflow language Id.