Although clouds have strong virtual memory isolation guarantees, cache attacks stemming from shared caches have proved to be a large security problem. However, despite the past effectiveness of cache attacks, their viability has recently been called into question on modern systems, due to trends in cache hierarchy design moving away from inclusive cache hierarchies. In this paper, we reverse engineer the structure of the directory in a sliced, non-inclusive cache hierarchy, and prove that the directory can be used to bootstrap conflict-based cache attacks on the last-level cache. We design the first cross-core Prime+Probe attack on non-inclusive caches. This attack works with minimal assumptions: the adversary does not need to share any virtual memory with the victim, nor run on the same processor core. We also show the first high-bandwidth Evict+Reload attack on the same hardware. We demonstrate both attacks by extracting key bits during RSA operations in GnuPG on a state-of-the-art non-inclusive Intel Skylake-X server.

Despite the isolation mechanisms that are available to cloud service providers, like virtual machines and containers, the problem of side-channel vulnerabilities due to shared caches and multicore processors remains a threat. We present a hardware-software mechanism that improves the isolation of cloud processes in the presence of shared caches on multicore chips. Our technique can enable cache-side-channel free computing for Linux-based containers and virtual machines by com-bining the Intel CAT architecture that enables cache partitioning with novel scheduling techniques and state cleansing mechanisms. We evaluate our system using a CPU-bound workload and demonstrate cache-side-channel-free computation that is correct by construction. Our system allows Simultaneous Multithreading to remain enabled and does not require application level changes.

The increasing relevance of information assurance in cloud computing has forced governments and stakeholders to turn their attention to Information Technology (IT) security certifications and standards. The introduction of new frameworks such as FedRAMP in the US and C5 in Germany is aimed to raise the level of protection against threats and vulnerabilities unique to cloud computing. However, our in-depth and systematic analyses reveals that these new standards do not bring a radical change in the realm of certifications. Results also shows that the newly developed standards share much of their basis with older, more consolidated standards such as the ISO/IEC 27001 and hence the need for determining the added value. In this study, we provide an overview of ISO/IEC 27001, C5, and FedRAMP while examining their completeness and adequacy in addressing current threats to cloud assurance. We question the level of protection they offer by comparing these three certifications alongside each other. We identify weaknesses in the three frameworks and highlight necessary improvements to meet the security requirements indispensable in relation to the current threat landscape.

To demonstrate compliance with privacy and security principles, information technology (IT) service providers often rely on security standards and certifications. However, the appearance of new service models such as cloud computing has brought new threats to information assurance, weakening the protection that existing standards can provide. In this study, we analyze four highly regarded IT security standards used to assess, improve, and demonstrate information systems assurance and cloud security. ISO/IEC 27001, SOC 2, C5, and FedRAMP are standards adopted worldwide and constantly updated and improved since the first release of ISO in 2005. We examine their adequacy in addressing current threats to cloud security, and provide an overview of the evolution over the years of their ability to cope with threats and vulnerabilities. By comparing the standards alongside each other, we investigate their complementarity, their redundancies, and the level of protection they offer to information stored in cloud systems. We unveil vulnerabilities left unaddressed in the four frameworks, thus questioning the necessity of multiple standards to assess cloud assurance. We suggest necessary improvements to meet the security requirements made indispensable by the current threat landscape.

In this paper, we present a data acquisition and analysis framework for materials-to-devices processes, named 4CeeD, that focuses on the immense potential of capturing, accurately curating, correlating, and coordinating materials-to-devices digital data in a real-time and trusted manner before fully archiving and publishing them for wide access and sharing. In particular, 4CeeD consists of novel services: a curation service for collecting data from microscopes and fabrication instruments, curating, and wrapping of data with extensive metadata in real-time and in a trusted manner, and a cloud-based coordination service for storing data, extracting meta-data, analyzing and finding correlations among the data. Our evaluation results show that our novel cloud framework can help researchers significantly save time and cost spent on experiments, and is efficient in dealing with high-volume and fast-changing workload of heterogeneous types of experimental data.

Numerous event-based probing methods exist for cloud computing environments allowing a hypervisor to gain insight into guest activities. Such event-based probing has been shown to be useful for detecting attacks, system hangs through watchdogs, and for inserting exploit detectors before a system can be patched, among others. Here, we illustrate how to use such probing for trustworthy logging and highlight some of the challenges that existing event-based probing mechanisms do not address. Challenges include ensuring a probe inserted at given address is trustworthy despite the lack of attestation available for probes that have been inserted dynamically. We show how probes can be inserted to ensure proper logging of every invocation of a probed instruction. When combined with attested boot of the hypervisor and guest machines, we can ensure the output stream of monitored events is trustworthy. Using these techniques we build a trustworthy log of certain guest-system-call events. The log powers a cloud-tuned Intrusion Detection System (IDS). New event types are identified that must be added to existing probing systems to ensure attempts to circumvent probes within the guest appear in the log. We highlight the overhead penalties paid by guests to increase guarantees of log completeness when faced with attacks on the guest kernel. Promising results (less that 10% for guests) are shown when a guest relaxes the trade-off between log completeness and overhead. Our demonstrative IDS detects common attack scenarios with simple policies built using our guest behavior recording system.

This paper extends the concepts behind cloud services to offer hypervisor-based reliability and security monitors for cloud virtual machines. Cloud VMs can be heterogeneous and as such guest OS parameters needed for monitoring can vary across different VMs and must be obtained in some way. Past work involves running code inside the VM, which is unacceptable for a cloud environment. We solve this problem by recognizing that there are common OS design patterns that can be used to infer monitoring parameters from the guest OS. We extract information about the cloud user's guest OS with the user's existing VM image and knowledge of OS design patterns as the only inputs to analysis. To demonstrate the range of monitoring functionality possible with this technique, we implemented four sample monitors: a guest OS process tracer, an OS hang detector, a return-to-user attack detector, and a process-based keylogger detector.

Distributed stream processing systems need to support stateful processing, recover quickly from failures to resume such processing, and reprocess an entire data stream quickly. We present Apache Samza, a distributed system for stateful and fault-tolerant stream processing. Samza utilizes a partitioned local state along with a low-overhead background changelog mechanism, allowing it to scale to massive state sizes (hundreds of TB) per application. Recovery from failures is sped up by re-scheduling based on Host Affinity. In addition to processing infinite streams of events, Samza supports processing a finite dataset as a stream, from either a streaming source (e.g., Kafka), a database snapshot (e.g., Databus), or a file system (e.g. HDFS), without having to change the application code (unlike the popular Lambda-based architectures which necessitate maintenance of separate code bases for batch and stream path processing). Samza is currently in use at LinkedIn by hundreds of production applications with more than 10, 000 containers. Samza is an open-source Apache project adopted by many top-tier companies (e.g., LinkedIn, Uber, Netflix, TripAdvisor, etc.). Our experiments show that Samza: a) handles state efficiently, improving latency and throughput by more than 100X compared to using a remote storage; b) provides recovery time independent of state size; c) scales performance linearly with number of containers; and d) supports reprocessing of the data stream quickly and with minimal interference on real-time traffic.

Data locality is a fundamental problem to data-parallel applications where data-processing tasks consume different amounts of time and resources at different locations. The problem is especially prominent under stressed conditions such as hot spots. While replication based on data popularity relieves hot spots due to contention for a single file, hot spots caused by skewed node popularity, due to contention for files co-located with each other, are more complex, unpredictable, hence more difficult to deal with. We propose Pandas, a light-weight acceleration engine for data-processing tasks that is robust to changes in load and skewness in node popularity. Pandas is a stochastic delay-optimal algorithm. Trace-driven experiments on Hadoop show that Pandas accelerates the data-processing phase of jobs by 11 times with hot spots and 2.4 times without hot spots over existing schedulers. When the difference in processing times due to location is large, such as applicable to the case of memory-locality, the acceleration by Pandas is 22 times.

Many in the networking community believe that Software-Defined Networking, in which entire networks are managed centrally, has the potential to revolutionize the field. However, SDN faces several challenges that have prevented its wide-spread adoption. Current SDN technologies, such as OpenFlow, provide powerful and flexible APIs, but can be unreasonably complex for implementing nontrivial network control logic. The generality offered by these low-level abstractions impose no structure on the network, requiring programmers to herd switches themselves, with little guidance. Many researchers argue that SDNs must adopt more structured models, such as Fabric, with an intelligent edge and a fast but simple label-switched core. Our work draws heavily from these ideas.

Traffic for a typical MapReduce job in a data center consists of multiple network flows. Traditionally, network resources have been allocated to optimize network-level metrics such as flow completion time or throughput. Some recent schemes propose using application-aware scheduling which can shorten the average job completion time. However, most of them treat the core network as a black box with sufficient capacity. Even if only one network link in the core network becomes a bottleneck, it can hurt application performance. We design and implement a centralized flow-scheduling framework called Phurti with the goal of improving the completion time for jobs in a cluster shared among multiple Hadoop jobs (multi-tenant). Phurti communicates both with the Hadoop framework to retrieve job-level network traffic information and the OpenFlow-based switches to learn about the network topology. Phurti implements a novel heuristic called Smallest Maximum Sequential-traffic First (SMSF) that uses collected application and network information to perform traffic scheduling for MapReduce jobs. Our evaluation with real Hadoop workloads shows that compared to application and network-agnostic scheduling strategies, Phurti improves job completion time for 95% of the jobs, decreases average job completion time by 20%, tail job completion time by 13% and scales well with the cluster size and number of jobs.

While distributed graph processing engines have become popular for processing large graphs, these engines are typically configured with a static set of servers in the cluster. In other words, they lack the flexibility to scale-out or scale-in the number of servers, when requested to do so by the user. In this paper, we propose the first techniques to make distributed graph processing truly elastic. While supporting on-demand scale-out/in operations, we meet three goals: i) perform scale-out/in without interrupting the graph computation, ii) minimize the background network overhead involved in the scale-out/in, and iii) mitigate stragglers by maintaining load balance across servers. We present and analyze two techniques called Contiguous Vertex Repartitioning (CVR) and Ring-based Vertex Repartitioning (RVR) to address these goals. We implement our techniques in the LFGraph distributed graph processing system, and incorporate several systems optimizations. Experiments performed with multiple graph benchmark applications on a real graph indicate that our techniques perform within 9% and 21% of the optimum for scale-out and scale-in operations, respectively.

Overlay networking and ISP-assisted tunneling are effective solutions to overcome problematic BGP routes and bypass troublesome autonomous systems. Despite their demonstrated effectiveness, overlay support is not broadly available. In this paper, we propose Cloud-Routed Overlay Networks (CRONets), whereby users can readily build their own overlays using nodes from global and well-provisioned cloud providers like IBM Softlayer or Amazon EC2. While previous studies have demonstrated the benefits of overlay networks with the high-speed experimental Internet2 backbone, we are the first to evaluate the improvements in a realistic -- cloud -- setting. We conduct a large-scale experiment where we observe 6,600 Internet paths. The results show that CRONets improve the throughput for 78% of the default Internet paths with a median and average improvement factors of 1.67 and 3.27 times respectively, at a tenth of the cost of leasing private lines of comparable performance. We also performed a longitudinal measurement, and demonstrate that the performance gains are consistent over time with only a small number of overlay nodes needed to be deployed. However, given the size and dynamic nature of the Internet routing system (e.g., due to congestion and failures), selecting the proper path is still a challenging problem. To address it, we propose a novel solution based on the newly-introduced MPTCP extensions. Our experiments show that MPTCP can achieve the maximum observed throughput across the different overlay paths.

The infrastructure beneath a worldwide social network has to continually serve billions of variable-sized media objects such as photos, videos, and audio clips. These objects must be stored and served with low latency and high throughput by a system that is geo-distributed, highly scalable, and load-balanced. Existing file systems and object stores face several challenges when serving such large objects. We present Ambry, a production-quality system for storing large immutable data (called blobs). Ambry is designed in a decentralized way and leverages techniques such as logical blob grouping, asynchronous replication, rebalancing mechanisms, zero-cost failure detection, and OS caching. Ambry has been running in LinkedIn's production environment for the past 2 years, serving up to 10K requests per second across more than 400 million users. Our experimental evaluation reveals that Ambry offers high efficiency (utilizing up to 88% of the network bandwidth), low latency (less than 50 ms latency for a 1 MB object), and load balancing (improving imbalance of request rate among disks by 8x-10x).

Distributed graph processing systems largely rely on proactive techniques for failure recovery. Unfortunately, these approaches (such as checkpointing) entail a significant overhead. In this paper, we argue that distributed graph processing systems should instead use a reactive approach to failure recovery. The reactive approach trades off completeness of the result (generating a slightly inaccurate result) while reducing the overhead during failure-free execution to zero. We build a system called Zorro that imbues this reactive approach, and integrate Zorro into two graph processing systems -- PowerGraph and LFGraph. When a failure occurs, Zorro opportunistically exploits vertex replication inherent in today's graph processing systems to quickly rebuild the state of failed servers. Experiments using real-world graphs demonstrate that Zorro is able to recover over 99% of the graph state when 6--12% of the servers fail, and between 87--95% when half the cluster fails. Furthermore, using various graph processing algorithms, Zorro incurs little to no accuracy loss in all experimental failure scenarios, and achieves a worst-case accuracy of 97%.

The era of big data has led to the emergence of new systems for real-time distributed stream processing, e.g., Apache Storm is one of the most popular stream processing systems in industry today. However, Storm, like many other stream processing systems lacks an intelligent scheduling mechanism. The default round-robin scheduling currently deployed in Storm disregards resource demands and availability, and can therefore be inefficient at times. We present R-Storm (Resource-Aware Storm), a system that implements resource-aware scheduling within Storm. R-Storm is designed to increase overall throughput by maximizing resource utilization while minimizing network latency. When scheduling tasks, R-Storm can satisfy both soft and hard resource constraints as well as minimizing network distance between components that communicate with each other. We evaluate R-Storm on set of micro-benchmark Storm applications as well as Storm applications used in production at Yahoo! Inc. From our experimental results we conclude that R-Storm achieves 30-47% higher throughput and 69-350% better CPU utilization than default Storm for the micro-benchmarks. For the Yahoo! Storm applications, R-Storm outperforms default Storm by around 50% based on overall throughput. We also demonstrate that R-Storm performs much better when scheduling multiple Storm applications than default Storm.

Virtualization techniques are the key in both public and private cloud computing environments. In such environments, multiple virtual instances are running on the same physical machine. The logical isolation between systems makes security assurance weaker than physically isolated systems. Thus, Virtual Machine Introspection techniques become essential to prevent the virtual system from being vulnerable to attacks. However, this technique breaks down the borders of the segregation between multiple tenants, which should be avoided in a public cloud computing environment. In this paper, we focus on building an encrypted Virtual Machine Introspection system, CryptVMI, to address the above concern, especially in a public cloud system. Our approach maintains a query handler on the management node to handle encrypted queries from user clients. We pass the query to the corresponding compute node that holds the virtual instance queried. The introspection application deployed on the compute node processes the query and acquires the encrypted results from the virtual instance for the user. This work shows our design and preliminary implementation of this system.

Virtualization techniques are widely used in cloud computing environments today. Such environments are installed with a large number of similar virtual instances sharing the same physical infrastructure. In this paper, we focus on the memory usage optimization across virtual machines by automatically de-duplicating the memory on per-page basis. Our approach maintains a single copy of the duplicated pages in physical memory using copy-on-write mechanism. Unlike some existing strategies, which are intended only for applications and need user configuration, VMDedup provides an automatic memory de-duplication support within the hypervisor to achieve benefits across operating system code, data as well as application binaries. We have implemented a prototype of this system within the Xen hypervisor to support both para-virtualized and fully-virtualized instances of operating systems.

Virtual appliances (VAs) are ready-to-use virtual machine images that are configured for specific purposes. For example, a virtual machine image that contains all the software necessary to develop and host a JSP-based website is typically available as a "Java Web Starter" VA. Currently there are many VA repositories from which users can download VAs and instantiate them on Infrastructure-as-a-Service (IaaS) clouds, allowing them to quickly launch their services. This marketplace, however, lacks adequate mechanisms that allow users to a priori assess whether a specific VA is really configured with the software that it is expected to be configured with. This paper evaluates the integrity of software packages installed on real-world VAs, through the use of a software whitelist-based framework, and finds that indeed there is a lot of variance in the software integrity of packages across VAs. Analysis of 151 Amazon VAs using this framework shows that about 9% of real-world VAs have significant numbers of software packages that contain unknown files, making them potentially untrusted. Virus scanners flagged just half of the VAs in that 9% as malicious, demonstrating that virus scanning alone is not sufficient to help users select a trustable VA and that a priori software integrity assessment has a role to play.

In today's IaaS clouds users only get a logical view of the underlying network and have limited control. Delegating more control to end users would be beneficial but would also raise security concerns for the provider. Emerging Software Defined Networking (SDN) technologies have the capabilities to facilitate delegation of network controls and provide some level of network abstractions to end users. However, any delegation solution should try to balance the level of controls delegated to end users with the security constraints of the provider. In this paper, we propose a SDN-based framework to facilitate delegation of some network controls to end users, providing the means to monitor and configure their own slices of the underlying networks. Using two instantiations of this framework, we illustrate the tradeoffs between security and the level of network abstractions provided to end users.

The Third International Workshop on Dependability of Clouds, Data Centers, and Virtual Machine Technology (DCDV 2013) features papers covering various aspects of dependability and security in Clouds and Data Centers. Four sessions covering Cloud and Data Center Networking, Dependability Evaluation, Mobile and Cloud Computing, and Virtualization and Cloud include eleven papers.

As cloud computing clusters continue to grow, maintaining the health of these clusters becomes increasingly challenging. Recent work has studied how we can efficiently monitor the status of machines in these clusters and how we can detect problems or predict them before they occur, yet little work has focused on addressing the bottleneck between when these failures occur and when they are fixed: system administrators. As monitoring and failure detection systems mature, we are able to extract tremendous amounts of information about the status of the system in real time. However, this amount of data is difficult to understand for human beings, especially those inexperienced with the particular cluster. In this paper, we introduce a web-based visualization suite called Theius to allow system administrators to quickly understand the state of the cloud system as a whole. We outline the key features of this visualization tool, and show that it is more intuitive and easy to use than Ganglia, a state-of-the art visualization tool for clusters. Likewise, we demonstrate that our tool can scale, presenting a use case with our visualization showing a 5000 node cluster. Although our tool is implemented for Hadoop clusters, our contribution is general to any cloud computing system.

Cloud computing offers an attractive option for businesses to rent a suitable size MapReduce cluster, consume resources as a service, and pay only for resources that were consumed. A key challenge in such environments is to increase the utilization of MapReduce clusters to minimize their cost. One way of achieving this goal is to optimize the execution of Mapreduce jobs on the cluster. For a set of production jobs that are executed periodically on new data, we can perform an offline analysis for evaluating performance benefits of different optimization techniques. In this work, we consider a subset of production workloads that consists of MapReduce jobs with no dependencies. We observe that the order in which these jobs are executed can have a significant impact on their overall completion time and the cluster resource utilization. Our goal is to automate the design of a job schedule that minimizes the completion time (makespan) of such a set of MapReduce jobs. We introduce a simple abstraction where each MapReduce job is represented as a pair of map and reduce stage durations. This representation enables us to apply the classic Johnson algorithm that was designed for building an optimal two-stage job schedule. We evaluate the performance benefits of the constructed schedule through an extensive set of simulations over a variety of realistic workloads. The results are workload and cluster-size dependent, but it is typical to achieve up to 10-25 percent of makespan improvements by simply processing the jobs in the right order. However, in some cases, the simplified abstraction assumed by Johnson's algorithm may lead to a suboptimal job schedule. We design a novel heuristic, called BalancedPools, that significantly improves Johnson's schedule results (up to 15-38 percent), exactly in the situations when it produces suboptimal makespan. Overall, we observe up to 50 percent in the makespan improvements with the new BalancedPools algorithm. The results of our simulation study are validated through experiments on a 66-node Hadoop cluster.

In this paper, we present our design of a Processing Element (PE) Aware MapReduce base framework, Pamar. Pamar is designed for supporting distributed computing on clusters where node PE configurations are asymmetric on different nodes. Pamar's main goal is to allow users to seamlessly utilize different kinds of processing elements (e.g., CPUs or GPUs) collaboratively for large scale data processing. To show proof of concept, we have incorporated our designs into the Hadoop framework and tested it on cluster environments having asymmetric node PE configurations. We demonstrate Pamar's ability to identify PEs available on each node and match-make user jobs with nodes, base on job PE requirements. Pamar allows users to easily parallelize applications across large datasets and at the same time utilizes different PEs for processing different classes of functions efficiently. The experiments show improvement in job queue completion time with Pamar over clusters with asymmetric nodes as compared to clusters with symmetric nodes.

Iterative-convergence algorithms are frequently used in a variety of domains to build models from large data sets. Cluster implementations of these algorithms are commonly realized using parallel programming models such as MapReduce. However, these implementations suffer from significant performance bottlenecks, especially due to large volumes of network traffic resulting from intermediate data and model updates during the iterations. To address these challenges, we propose partitioned iterative convergence (PIC), a new approach to programming and executing iterative convergence algorithms on frameworks like MapReduce. In PIC, we execute the iterative-convergence computation in two phases - the best-effort phase, which quickly produces a good initial model and the top-off phase, which further refines this model to produce the final solution. The best-effort phase iteratively performs the following steps: (a) partition the input data and the model to create several smaller, model-building sub-problems, (b) independently solve these sub-problems using iterative convergence computations, and (c) merge solutions of the sub-problems to create the next version of the model. This partitioned, loosely coupled execution of the computation produces a model of good quality, while drastically reducing network traffic due to intermediate data and model updates. The top-off phase further refines this model by employing the original iterative-convergence computation on the entire (un-partitioned) problem until convergence. However, the number of iterations executed in the top-off phase is quite small, resulting in a significant overall improvement in performance. We have implemented a library for PIC on top of the Hadoop MapReduce framework, and evaluated it using five popular iterative-convergence algorithms (Page Rank, K-Means clustering, neural network training, linear equation solver and image smoothing). Our evaluations on clusters ranging from 6 nodes to 256 nodes demonstrate a 2.5X-4X speedup compared to conventional implementations using Hadoop.

The combined effect of Moore's law and the failure of Den nard scaling have led to multi-core mobile devices with immense computation capabilities. The biggest limitation of the computation capability for any mobile device is its battery. Mobile cloud computing is used to offload compute intensive tasks that affect a mobile device's battery. Mobile ad-hoc computing can be used as an alternative to mobile cloud computing in cases where cloud access is not available or is inhibitive to application performance, although battery drain remains a critical argument against mobile ad-hoc computing. In this paper, we present Synergy, a middleware that increases the battery life for a system of mobile devices connected in a peer-to-peer ad-hoc network. Synergy conserves energy by scaling core frequencies and by intelligently distributing the computation among peer devices. The middleware is not restricted to mobile phones and in no way restricts the mobility of the devices. Synergy considers the mobile devices connected in a peer-to-peer fashion as a single multicore device with Wifi as the interconnect. With Synergy running on Google Nexus phones we were able to conserve up to 30.6% of the system battery while incurring a latency penalty of less than 5%.

Monitoring systems observe important information that could be a valuable resource to malicious users: attackers can use the knowledge of topology information, application logs, or configuration data to target attacks and make them hard to detect. The increasing need for correlating information across distributed systems to better detect potential attacks and to meet regulatory requirements can potentially exacerbate the problem if the monitoring is centralized. A single zero-day vulnerability would permit an attacker to access all information. This paper introduces a novel algorithm for performing policy-based security monitoring. We use policies to distribute information across several hosts, so that any host compromise has limited impact on the confidentiality of the data about the overall system. Experiments show that our solution spreads information uniformly across distributed monitoring hosts and forces attackers to perform multiple actions to acquire important data.

Large-scale MapReduce clusters that routinely process petabytes of unstructured and semi-structured data represent a new entity in the changing landscape of clouds. A key challenge is to increase the utilization of these MapReduce clusters. In this work, we consider a subset of the production workload that consists of MapReduce jobs with no dependencies. We observe that the order in which these jobs are executed can have a significant impact on their overall completion time and the cluster resource utilization. Our goal is to automate the design of a job schedule that minimizes the completion time (makespan) of such a set of MapReduce jobs. We offer a novel abstraction framework and a heuristic, called BalancedPools, that efficiently utilizes performance properties of MapReduce jobs in a given workload for constructing an optimized job schedule. Simulations performed over a realistic workload demonstrate that 15%-38% makespan improvements are achievable by simply processing the jobs in the right order.

Hadoop and the associated MapReduce paradigm, has become the de facto platform for cost-effective analytics over “Big Data”. There is an increasing number of MapReduce applications associated with live business intelligence that require completion time guarantees. In this work, we introduce and analyze a set of complementary mechanisms that enhance workload management decisions for processing MapReduce jobs with deadlines. The three mechanisms we consider are the following: 1) a policy for job ordering in the processing queue; 2) a mechanism for allocating a tailored number of map and reduce slots to each job with a completion time requirement; 3) a mechanism for allocating and deallocating (if necessary) spare resources in the system among the active jobs. We analyze the functionality and performance benefits of each mechanism via an extensive set of simulations over diverse workload sets. The proposed mechanisms form the integral pieces in the performance puzzle of automated workload management in MapReduce environments.

Performance characterization of applications' hardware behavior is essential for making the best use of available hardware resources. Modern architectures offer access to many hardware events that are capable of providing information to reveal architectural performance bottlenecks throughout the core and memory hierarchy. These events can provide programmers with unique and powerful insights into the causes of the resource bottlenecks in their applications. However, interpreting these events has been a significant challenge. We present an automated system that uses machine learning to identify an application's performance problems. Our system provides programmers with insights about the performance of their applications while shielding them from the onerous task of digesting hardware events. It uses a decision tree algorithm, random forests on our micro-benchmarks to fingerprint the performance problems. Our system divides a profiled application into functions and automatically classifies each function by the dominant hardware resource bottlenecks. Using the classifications from the hotspot functions, we were able to achieve an average speedup of 1.73 from three applications in the PARSEC benchmark suite. Our system provides programmers with a guideline of where, what, and how to fix the detected performance problems in applications, which would have otherwise required considerable architectural knowledge.

Ubiquitous and pervasive applications may present critical requirements from the point of view of functional correctness, reliability, availability, security, and safety. Unlike traditional safety-critical applications, the behavior of ubiquitous and pervasive applications is affected by the movements and location of users and resources. In this article, we first present emerging formal methods for the description of both entities and their behavior in pervasive computing environments; then, we introduce this special issue. Despite many previous works that have focused on modeling the entities, relatively few have concentrated on modeling or verifying behaviors; and almost none has dealt with combining techniques proposed in these two aspects. The articles accepted in this special issue cover some of the topics aforementioned and constitute a representative sample of the latest development of formal methods in pervasive computing environments.

Mobile devices are gradually changing people's computing behaviors. However, due to the limitations of physical size and power consumption, they are not capable of delivering a 3D graphics rendering experience comparable to desktops. Many applications with intensive graphics rendering workloads are unable to run on mobile platforms directly. This issue can be addressed with the idea of remote rendering: the heavy 3D graphics rendering computation runs on a powerful server and the rendering results are transmitted to the mobile client for display. However, the simple remote rendering solution inevitably suffers from the large interaction latency caused by wireless networks, and is not acceptable for many applications that have very strict latency requirements. In this article, we present an advanced low-latency remote rendering system that assists mobile devices to render interactive 3D graphics in real-time. Our design takes advantage of an image based rendering technique: 3D image warping, to synthesize the mobile display from the depth images generated on the server. The research indicates that the system can successfully reduce the interaction latency while maintaining the high rendering quality by generating multiple depth images at the carefully selected viewpoints. We study the problem of viewpoint selection, propose a real-time reference viewpoint prediction algorithm, and evaluate the algorithm performance with real-device experiments.

Placing data as close as possible to computation is a common practice of data intensive systems, commonly referred to as the data locality problem. By analyzing existing production systems, we confirm the benefit of data locality and find that data have different popularity and varying correlation of accesses. We propose DARE, a distributed adaptive data replication algorithm that aids the scheduler to achieve better data locality. DARE solves two problems, how many replicas to allocate for each file and where to place them, using probabilistic sampling and a competitive aging algorithm independently at each node. It takes advantage of existing remote data accesses in the system and incurs no extra network usage. Using two mixed workload traces from Face book, we show that DARE improves data locality by more than 7 times with the FIFO scheduler in Hadoop and achieves more than 85% data locality for the FAIR scheduler with delay scheduling. Turnaround time and job slowdown are reduced by 19% and 25\%, respectively.

A typical MapReduce cluster is shared among different users and multiple applications. A challenging problem in such shared environments is the ability to efficiently control resource allocations among the running and submitted jobs for achieving users' performance goals. To ease the task of evaluating and comparing different provisioning and scheduling approaches in MapReduce environments, we designed and implemented a simulation environment Sim MR which is comprised of three inter-related components: i) Trace Generator that creates a replayable MapReduce workload, ii) Simulator Engine that accurately emulates the job master functionality in Hadoop, and iii) a pluggable scheduling policy that dictates the scheduler decisions on job ordering and the amount of resources allocated to different jobs over time. We validate the accuracy of Sim MR environment by, first, executing a set of realistic MapReduce applications in a 66-node Hadoop cluster and then by replaying the collected job execution traces in SimMR. Our simulator accurately reproduces the original job processing: the completion times of the simulated jobs are within 5% of the original ones. SimMR can process over one million events per second. This allows users to simulate complex workloads in a few seconds instead of multi-hour executions in the real test bed. Finally, by using SimMR we analyze and compare performance of two novel deadline-driven schedulers over a diverse set of real and synthetic workloads.

A new metric distortion over latency (DOL) is proposed in this paper to overcome the deficiency of the traditional metric interaction latency in measuring the interactive performance of the modern remote rendering systems, which are enhanced with different latency reduction techniques. The proposed metric is novel in combining both latency and rendering quality into one score for measurement. Our experiments validate that in many scenarios, our new metric can effectively distinguish the performance difference between systems while interaction latency can not. The paper also introduces how DOL can be efficiently calculated at runtime.

The emerging cloud gaming service has been growing rapidly, but not yet able to reach mobile customers due to many limitations, such as bandwidth and latency. We introduce a 3D image warping assisted real-time video coding method that can potentially meet all the requirements of mobile cloud gaming. The proposed video encoder selects a set of key frames in the video sequence, uses the 3D image warping algorithm to interpolate other non-key frames, and encodes the key frames and the residues frames with an H.264/AVC encoder. Our approach is novel in taking advantage of the run-time graphics rendering contexts (rendering viewpoint, pixel depth, camera motion, etc.) from the 3D game engine to enhance the performance of video encoding for the cloud gaming service. The experiments indicate that our proposed video encoder has the potential to beat the state-of-art x264 encoder in the scenario of real-time cloud gaming. For example, by implementing the proposed method in a 3D tank battle game, we experimentally show that more than 2 dB quality improvement is possible.

The security of monitoring systems is critical for maintaining an accurate view of the state of infrastructure systems such as enterprise networks and critical infrastructure systems. A malicious user that controls a monitoring system has the ability of delaying the detection of security attacks and sabotages, and can acquire information about the infrastructure that can enable additional attacks. In this paper we present a distributed architecture that increases the resilient of monitoring systems to attacks against their availability, integrity, and confidentiality. Our approach is based on distributing the knowledge of the state of the infrastructure to a large number of non-dedicated servers, so that the compromise of any limited number of hosts does not cause a compromise of the entire monitoring system. We present an algorithm able to integrate information across the distributed servers to evaluate complex security policies. We analyze the security properties of our approach, and we experimentally evaluate the performance and the resilience of our architecture. We show that, compared to current solutions, our solution increases the resilience of a monitoring system while reducing the load on each monitoring machine.

Current post-mortem cyber-forensic techniques may cause significant disruption to the evidence gathering process by breaking active network connections and unmounting encrypted disks. Although newer live forensic analysis tools can preserve active state, they may taint evidence by leaving footprints in memory. To help address these concerns we present Forenscope, a framework that allows an investigator to examine the state of an active system without the effects of taint or forensic blurriness caused by analyzing a running system. We show how Forenscope can fit into accepted workflows to improve the evidence gathering process.

This paper shows how the extended compact genetic algorithm can be scaled using data-intensive computing techniques such as MapReduce. Two different frameworks (Hadoop and MongoDB) are used to deploy MapReduce implementations of the compact and extended compact genetic algorithms. Results show that both are good choices to deal with large-scale problems as they can scale with the number of commodity machines, as opposed to previous efforts with other techniques that either required specialized high-performance hardware or shared memory environments.

The MapReduce model uses a barrier between the Map and Reduce stages. This provides simplicity in both programming and implementation. However, in many situations, this barrier hurts performance because it is overly restrictive. Hence, we develop a method to break the barrier in MapReduce in a way that improves efficiency. Careful design of our barrierless MapReduce framework results in equivalent generality and retains ease of programming. We motivate our case with, and experimentally study our barrier-less techniques in, a wide variety of MapReduce applications divided into seven classes. Our experiments show that our approach can achieve better performance times than a traditional MapReduce framework. We achieve a reduction in job completion times that is 25% on average and 87% in the best case.

The objective of this research is to present an energy-conserving, self-adaptive Commodity Green Cloud Storage, called Lightning. Lightning's File System dynamically configures the servers in the Cloud Storage into logical Hot and Cold Zones. Lightning uses data-classification driven data placement to realize guaranteed, substantially long, periods (several days) of idleness in a significant subset of servers designated as the Cold Zone, in the commodity datacenter backing the Cloud Storage. These servers are then transitioned to inactive power modes and the resulting energy savings substantially reduce the operating costs of the datacenter. Furthermore, the energy savings allow Lightning to improve the data access performance by incorporation of high-performance, though high-cost Solid State Drives (SSD) without exceeding the total cost of ownership (TCO) of the datacenter. Analytical cost model analysis of Lightning suggests savings in the upwards of $24 million in the TCO of a 20,000 server datacenter. The simulation results show that Lightning can achieve 46% energy costs reduction even when the datacenter is at 80% capacity utilization.

Demand for 3D visualization is increasing in mobile devices as users have come to expect more realistic immersive experiences. However, limited networking and computing resources on mobile devices remain challenges. A solution is to have a proxy-based framework that offloads the burden of rendering computation from mobile devices to more powerful servers. We present the implementation of a framework for parallel remote rendering using commodity Graphics Processing Units (GPUs) in the proxy servers. Experiments show that this framework substantially improves the performance of rendering computation of 3D video.

We explore interacting with everyday objects by representing content as interactive surface particles. Users can build their own physical world, map virtual content onto their physical construction and play directly with the surface using a stylus. A surface particle representation allows programmed content to be created independent of the display object and to be reused on many surfaces. We demonstrated this idea through a projector-camera system that acquires the object geometry and enables direct interaction through an IR tracked stylus. We present three motivating example applications, each displayed on three example surfaces. We discuss a set of interaction techniques that show possible avenues for structuring interaction on complicated everyday objects, such as Surface Adaptive GUIs for menu selection. Through a preliminary informal evaluation and interviews with end users, we demonstrate the potential of interacting with surface particles and identify improvements necessary to make this interaction practical on everyday surfaces.

As an emerging technology, 3D video has shown a great potential to become the next generation media for tele-immersion. However, streaming and rendering this dynamic 3D data in real-time requires tremendous network bandwidth and computing resources. In this paper, we build a remote rendering model to better study different remote rendering designs and define 3D video rendering as an optimization problem. Moreover, we design a 3D video remote rendering system that significantly reduces the delay while maintaining high rendering quality. We also propose a reference viewpoint prediction algorithm with super sampling support that requires much less computation resources but provides better performance than the search-based algorithms proposed in the related work.

The recent development of high-speed data transmission over wireless cellular networks has enabled the delivery of multimedia broadcasting services to mobile users. These services involve a range of interactions among different system components, including the wireless channel, the network, and mobile devices, making it crucial for the service provider to verify the model, design, and behavior of a new service before it is deployed. However, previous studies have largely relied on network simulations or scaled experiments, and there has been little work on the sort of unified framework for quality-of-service (QoS) assessment, which considers the interactions between components, that we propose in this paper. Accurate models of the wireless channel, the network, and the data processing that takes place on an embedded system of a mobile client, are integrated within our framework, and allow us to predict several key system metrics and the quality of the video stream as it is perceived by users. Furthermore, different models of system components can be easily plugged in to extend this framework. As an example application, we analyze the performance of the process of decoding scalable videos on ARM-based mobile embedded systems in CDMA2000 wireless cellular networks.

The Query Tree Protocol (QT) in Law et al. (2000) is an efficient RFID tag singulation algorithm that is guaranteed to read all the tags in the broadcast range of a reader. However, QT ignores the capture effect. That is, after the reader broadcasts a bit string query prefix, it is assumed that it can distinguish one of three responses, namely {no response, one response, collision}. If the capture effect is modeled, QT would no longer be guaranteed to singulate all the tags in the reader's range, since "capturing" a tag ID in the midst of a collision would leave all the other tags in that collision unsingulated. In this paper, we introduce two modifications to QT that always singulate all the tags even when the capture effect is considered. We call these the Generalized Query Tree Protocols (GQT1, GQT2). We provide analytical bounds and simulation results of the singulation times of these new protocols in relation to QT.

With the advent of high-performance COTS clusters, there is a need for a simple, scalable and fault-tolerant parallel programming and execution paradigm. In this paper, we show that the popular MapReduce programming model can be utilized to solve many interesting scientific simulation problems with much higher performance than regular cluster computers by leveraging GPGPU accelerators in cluster nodes. We use the Massive Unordered Distributed (MUD) formalism and establish a one-to-one correspondence between it and general Monte Carlo simulation methods. Our architecture, MITHRA, leverages NVIDIA CUDA technology along with Apache Hadoop to produce scalable performance gains using the MapReduce programming model. The evaluation of our proposed architecture using the Black Scholes option pricing model shows that a MITHRA cluster of 4 GPUs can outperform a regular cluster of 62 nodes, achieving a speedup of about 254 times in our testbed, while providing scalable near linear performance with additional nodes.

The recent development of high-speed data transmission over wireless networks enables multimedia broadcasting service to mobile users. Multimedia broadcasting service involves interactions among different system and network components, so it is crucial for the service provider to verify the correctness of system/service model and design, and their behaviors before a new type of service is deployed. However, due to limitations of using network simulations or scaled experimental testbeds, there has been none of research on such verification and simulation framework in 3G broadcasting networks. Therefore, we propose a simulation and analysis framework for multimedia broadcasting service over wireless networks. With concrete modeling of wireless physical channel, network, and data processing on a client device, it enables the prediction of various interesting system parameters and perceived quality of multimedia streams to users. Different models of system and network components can be plugged easily in our simulation framework for further extensions. Using this framework, we analyze the processing performance for decoding scalable videos on mobile devices in CDMA2000 wireless networks.

Much of the recent interest in location estimation systems has focused on 802.11 fingerprinting. Unlike GPS systems, 802.11 based systems can accurately estimate a user's location inside buildings. Moreover, users don't need any special equipment to carry around, as their WiFi enabled cell phone can already act as the receiver in WiFi fingerprinting systems. However, wireless access points in buildings are placed mostly according to another criteria, namely to increase the network coverage inside the building. But optimal coverage may not necessarily result in optimal location discovery. In this paper, we provide analyses on data gathered for a real WiFi location estimation system, and show what makes it perform inaccurately in some parts of a building while it is more accurate in other parts. We have defined two new metrics for quantifying the wireless signal behavior of multiple access points in small neighborhoods in a building. Finally, we identify the properties that differentiate well behaving and poorly behaving neighborhoods.

Genetic algorithms(GAs) are increasingly being applied to large scale problems. The traditional MPI-based parallel GAs require detailed knowledge about machine architecture. On the other hand, MapReduce is a powerful abstraction proposed by Google for making scalable and fault tolerant applications. In this paper, we show how genetic algorithms can be modeled into the MapReduce model. We describe the algorithm design and implementation of GAs on Hadoop, an open source implementation of MapReduce. Our experiments demonstrate the convergence and scalability up to 10^5 variable problems. Adding more resources would enable us to solve even larger problems without any changes in the algorithms and implementation since we do not introduce any performance bottlenecks.

At the convergence of computer vision, graphics, and multimedia, the emerging 3D video technology promises immersive experiences in a truly seamless environment. However, the requirements of huge network bandwidth and computing resources make it still a big challenge to render 3D video on mobile devices at real-time. In this paper, we present how remote rendering framework can be used to solve the problem. The differences between dynamic 3D video and static graphic models are analyzed. A general proxy-based framework is presented to render 3D video streams on the proxy and transmit the rendered scene to mobile devices over a wireless network. An image-based approach is proposed to enhance 3D interactivity and reduce the interaction delay. Experiments prove that the remote rendering framework can be effectively used for quality 3D video rendering on mobile devices in real time.

User studies usually involve much organization and manual labor. Even when performed correctly, a common problem of the studies is user bias. This occurs when participating users' knowledge of the study influences their actions. Another problem is the willingness of the users to participate at all. Finally, participants will always have privacy concerns. We have developed a framework to help with anonymized user studies, trying to solve the aforementioned problems. We have prepared a demo to show the effectiveness of our system.

With the growth in the popularity of social networking sites like Facebook and MySpace, there is an increasing concern about privacy of content posted by users. Many users enter personal details about themselves but have poor understanding of theats such as identity theft and stalking. There is a need to educate and assist users in understanding how their personal data is exposed to other users. In this paper, we introduce the concept of negotiated audit which gives users of social networks valuable feedback about how their data is being used. Our design has three levels of auditing for both sharing and browsing data: no audit, complete audit and anonymous audit. Users can classify their data as requiring some level of auditing and can also set their browsing preference to one of the auditing levels. Users can only see some data if their browsing preference is compatible with the data's audit level thus giving rise to negotiation of how much users are willing to reveal about their activities and how much data they will be able to access. We provide a mathematical model and describe a simple social networking prototype called Sh@re that implements negotiated audit.

BootJacker is a proof-of-concept attack tool which demonstrates that authentication mechanisms employed by an operating system can be bypassed by obtaining physical access and simply forcing a restart. The key insight that enables this attack is that the contents of memory on some machines are fully preserved across a warm boot. Upon a reboot, BootJacker uses this residual memory state to revive the original host operating system environment and run malicious payloads. Using BootJacker, an attacker can break into a locked user session and gain access to open encrypted disks, web browser sessions or other secure network connections. BootJacker's non-persistent design makes it possible for an attacker to leave no traces on the victim machine.

This research investigates the automation of security assessment of the static and dynamic properties of cyber infrastructures, with emphasis on the electrical power grid. We describe a network model representing the static elements of a cyber infrastructure including devices, services, network connectivity, vulnerabilities, and access controls. The dynamic elements include workflow models of the operating procedures, processes and the state of a working power grid. We introduce a toolkit that with a little manual assistance can automatically generate these models from specifications, continuously update attributes from online event aggregators, and perform security assessment. The assessment reveals whether observed anomalies about the system could indicate possible security problems and permit dynamic ranking of alternative recovery procedures to minimize the total risk. We motivate the use of the tool-chain by showing an example scenario where the recovery procedure recommended to minimize security risk depends on the current state of system as well as the network topology.

3D video is an emerging technology that promises immersive experiences in a truly seamless environment. Currently, 3D video systems still require excessive bandwidth and computation power provided by gigabit switches and multi-core workstations machines. In order to extend the experience to mobile devices, we present a view-dependent compression methodology that shows great promise in making 3D video a reality on resource-constrained mobile devices. Using our technology, we are able to achieve a software-only rendering on a Nokia N800 PDA with only wireless network transmission. We believe that with the use of newer handhelds and improvements to our compression techniques, we will be able to deliver full-motion 3D video soon.

The field of pervasive computing has seen a lot of exciting innovations in the past few years. However, there are currently no mechanisms for describing the properties and capabilities of pervasive computing environments in a formal manner. This makes it difficult to prove the correctnesss of a pervasive computing environment, i.e. to verify that the environment satisfies certain desired properties. In this paper, we propose a formal model for describing pervasive computing environments based on ambient calculus and the associated ambient logic. The model allows us to state and verify several properties of these environments such as "anywhere anyhow services", "mobility of devices and applications" and "context-aware adaptation ". The model allows us to describe the resources present in an environment, the operations that can be performed in the environment, and how users can use the resources in th environment to perform different kinds of activities. As a case study, we shall describe some of the resources and operations supported by the Gaia middleware using this model, and verify an example property of a pervasive computing environment supported by Gaia.

Rootkits are used by malicious attackers who desire to run software on a compromised machine without being detected. They have become stealthier over the years as a consequence of the ongoing struggle between attackers and system defenders. In order to explore the next step in rootkit evolution and to build strong defenses, we look at this issue from the point of view of an attacker. We construct Cloaker, a proof-of-concept rootkit for the ARM platform that is non- persistent and only relies on hardware state modifications for concealment and operation. A primary goal in the design of Cloaker is to not alter any part of the host operating system (OS) code or data, thereby achieving immunity to all existing rootkit detection techniques which perform integrity, behavior and signature checks of the host OS. Cloaker also demonstrates that a self-contained execution environment for malicious code can be provided without relying on the host OS for any services. Integrity checks of hardware state in each of the machine's devices are required in order to detect rootkits such as Cloaker. We present a framework for the Linux kernel that incorporates integrity checks of hardware state performed by device drivers in order to counter the threat posed by rootkits such as Cloaker.

User applications and data in volatile memory are usually lost when an operating system crashes because of errors caused by either hardware or software faults. This is because most operating systems are designed to stop working when some internal errors are detected despite the possibility that user data and applications might still be intact and recoverable. Techniques like exception handling, code reloading, operating system component isolation, micro-rebooting, automatic system service restarts, watchdog timer based recovery and transactional components can be applied to attempt self-healing of an operating system from a wide variety of errors. Fault injection experiments show that these techniques can be used to continue running user applications after transparently recovering the operating system in a large percentage of cases. In cases where transparent recovery is not possible, individual process recovery can be attempted as a last resort.

The users of today's operating systems demand high reliability and security. However, faults introduced outside of the core operating system by buggy and malicious device drivers can significantly impact these dependability attributes. To help improve driver isolation, we propose an approach that utilizes the latest hardware virtualization support to efficiently sandbox each device driver in its own minimal virtual machine (VM) so that the kernel is protected from faults in these drivers. We present our implementation of a low-overhead virtual-machine based framework which allows reuse of existing drivers. We have constructed a prototype to demonstrate that it is feasible to utilize existing hardware virtualization techniques to allow device drivers in a VM to communicate with devices directly without frequent hardware traps into the virtual machine monitor (VMM). We have implemented a prototype parallel port driver which interacts through iKernel to communicate with a physical LED device.

Large collaborative infrastructures that span multiple organizations such as those that enable grid computing and scientific experimentation are being deployed and used today. In order to secure these infrastructures a comprehensive requirements study is needed that takes into account the novel risks, threats, and operational issues brought on by the large-scale, distributed nature of these systems. In this paper we argue that gaps in security policies and procedures combined with organizational autonomy are the primary drivers motivating a set of requirements that go beyond those observed today. With three example infrastructures in mind, namely, Teragrid, LHC Grid, and GEM, we explore the novel risks, threats, and operational issues to compose a set of operational security requirements; the satisfaction of which are essential for securing such large collaborative infrastructures

Design patterns capture software solutions to specific problems that have evolved over time and reflect many iterations of work. Documenting such patterns promotes proven design and software reuse. There has been a growing amount of work documenting design patterns for security, however, little work specific to VoIP security. In 2005 NIST released a report on recommendations and best practices for securing VoIP, however it lacks the structure, terminology, and ease-of-understanding needed for both technical and non-technical audiences that is an inherent feature of design patterns. In this paper, we document three design patterns for VoIP implementations related to specific security problems: (1) secure traversal of firewalls and NATs; (2) detecting and mitigating DDoS attacks; and (3) securing against eavesdropping. With many VoIP vendors rushing products to market with overlapping functionality and requirements for interoperability, documenting design patterns is poised to become an important part of secure programming processes for VoIP

A pervasive system features a plethora of devices, services and applications organized as a large distributed system. One approach to managing such systems is by policies where administrators specify the management action to be taken in different situations using event-condition-action (ECA) rules. An important problem with policy-based management of a pervasive system is that multiple rules can get triggered on a single event and the behavior of the system depends on the order of rule enforcement. Systems managed using ECA policies do not provide guarantees about system behavior when multiple rules are concurrently triggered. In this paper, we present a novel rule framework called event-condition-precondition-action-postcondition (ECPAP) that combines axiomatic specifications with ECA rules for specifying management rules. ECPAP rules contain action specifications in first-order predicate logic that enables us to reason about the enforcement order. We define a notion called enforcement semantics for policy-based management and show how this can be used to provide guarantees about system behavior. We present the details of the framework

Pervasive computing promotes an environment that blurs the distinction between digital and physical devices and integrates all entities in a physical space into a cohesive programmable unit. Some of the early research activities in pervasive computing focused on developing infrastructures for pervasive applications. These infrastructures successfully merged physical and digital entities in an environment to create aware homes, smart offices and active spaces. In recent years, ad-hoc pervasive computing has attracted attention with the proliferation of low cost, short-range wireless devices. Ad-hoc pervasive computing does not assume digital devices to be tied to physical environments and aims to create digital "clusters" that can be viewed as a unified entity. The user can program this cluster of devices with a single programming interface. In this paper, AVC introduce our middleware, called Mobile Gaia, for ad-hoc pervasive computing. Mobile Gaia is a services-based middleware that integrates resources of various devices. It manages several functions such as forming and maintaining device collections, sharing resources among devices and enables seamless service interactions. It also provides an application framework to develop applications for the device collection. The application framework decomposes the application into smaller components that can run on different devices in this collection. We discuss the architecture of mobile Gaia and introduce a sample application that has been designed using our middleware.

Despite recent advancements in cellular phone network infrastructure, survivability of the calls is still an open issue. Important business calls and tele-conferences cannot benefit from mobility because landlines are preferred owing to their reliability and tolerance to failures. In this paper, we present a framework to improve call survivability by monitoring the user's location and intimating him about the possibility of loss of connectivity, interference, and room schedules that might disrupt conversation. In addition, if a call drops because of unforeseeable circumstances like battery failure or cell-phone damage then the call is switched to the nearest available device capable of streaming voice

Applications designed for ubiquitous computing environments need to be coded in a specific way in order to fully realize the benefits of ubiquitous computing. Currently, applications for ubiquitous computing environments either need to be rewritten entirely to benefit from ubiquity, or special wrappers need to be written and customized for particular applications to provide limited compatibility. We argue that the real-world deployment of ubiquitous computing will be realized when users can migrate and use the applications they are familiar with in their daily lives with minimal effort. Furthermore, these applications should automatically benefit from typical ubiquitous computing features including multi-device support, runtime adaptation, environment-independence and context-awareness. In this paper we present a framework that allows us to port any generic application to the domain of ubiquitous computing without having to rewrite the code from scratch. We have experimented with the framework in our prototype ubiquitous computing platform known as active spaces. This has allowed us to explosively increase the number of applications supported by our active space.

Ubiquitous computing environments feature massively distributed systems containing a large number of devices, services and applications that help end-users perform various kinds of tasks. One way by which administrators and end-users can manage these environments is through the use of policies. In particular, obligation policies are used to specify what actions must or must not be performed by the environment on the occurrence of certain events. Obligation policies are often specified as event-condition-action (ECA) rules. However an important problem in ubiquitous computing systems is that different users and administrators may have conflicting policies for managing the system. Hence, a key challenge in policy-based management is detecting and resolving conflicts between multiple policy rules that get activated by a single event. Existing approaches are limited in power and scope mainly because they do not have semantic information about the effects of policy actions; hence, they cannot infer that two actions may conflict unless they are explicitly stated to be conflicting. In this paper, we propose an extended model of ECA called event-condition-action-post-condition (ECA-P), where developers and administrators can annotate actions with their effects. The ECA-P model allows inferring that actions may conflict based on conflicting post-conditions. Detected conflicts are resolved using meta-rules that specify preferred system states. The ECA-P framework also detects failures in policy execution by using postconditions to verify successful completion of policy actions. We present the details of the framework.

Pervasive systems comprise large collections of heterogeneous and mobile devices, services and applications. A management infrastructure is required to govern the system behavior according to policies specified by the system administrator. Policy-based management is a well-established approach where policies are specified as Event-Condition-Action (ECA) rules that determine the management actions to be performed when certain situations occur. The problem with ECA policies is that conflicting actions may get triggered on the same event resulting in policy conflicts. Cycles may result when a set of policy rules trigger each other continuously. Existing approaches to conflict detection are limited in scope and can only detect conflicting actions if they are explicitly stated. In addition, current techniques do not detect cycles in management policies. We propose an extension to the ECA rule framework, called Event-Condition-PreCondition-Action-PostCondition (ECPAP) as a rule framework for management policies. In this framework, actions are annotated with axiomatic specifications that enable powerful reasoning to detect conflicts and cycles in policies. We present the details of this framework

The confluence of pervasive computing, anywhere/anytime access to information resources and scalable computing enables the construction of smart environments or Active Spaces. In such a Space, a spectrum of computation and communication devices seamlessly augment human thought and activity with digital information, processing, and analysis to provide an observed or imagined world that is automated and enhanced by the behavioral context of its users. The power of such a computer infrastructure has three contributing factors; the translation of information to and from physical properties, the computers and their ability to transform data, and the cooperative computational environment that results from embedding these devices in a network. This computational environment or “Active World” is the likely long-term benefit of the current information technology revolution. Several major projects have shown the benefits of considering pervasive computing environments within an infrastructure, constructed from computing elements that interact to form active or smart spaces, and managed by a software control system or meta-operating system to provide integrity and consistency. As a case study, our experimental system, Gaia, creates a pervasive computing environment that encompasses multiple rooms of our new building: the Siebel Center. Tasks like tours, exhibitions, seminars, lectures, or meetings are supported by coordinated distributed applications and both tasks and their contents may be programmed. Mobile users within the building are tracked with location sensors and may create sessions involving different tasks which they then may migrate, suspend, or resume as they move from room to room. Despite recent advances, many challenges remain. Integrating the various services, components, applications, and entities into a programmable COTS infrastructure enables context sensitive applications that allow users to interact seamlessly with a combination of physical and computer facilities. Such an infrastructure of smart devices, rooms, and buildings raises the question of how to manage, program, automate, and formalize these heterogeneous sources, sinks, repositories, and processors of data. The organization, management, and programmability of physical devices and information activities in a pervasive computing environment is key to enabling diverse, autonomic, digital habitats such as university campuses, office buildings, scientific labs, and museums. However, the promise of pervasive computing cannot be realized without cost-effective and efficient mechanisms, policies, and tools to organize, manage, operate, repair, program, and evaluate systems built from pervasive computing components. Human tasks, human factors and pervasive system infrastructure interact in complex ways and methodologies need to be devised to explore and measure these interactions. In particular, a pervasive environment would need to enable opportunistic collaboration, facilitate social interaction, and support teaching and learning. This talk will explore the benefits of an Active World, the barriers to its deployment, and the research challenges that lie ahead.

The Gaia ubiquitous computing platform currently supports mobile devices through a thin client proxy architecture. Mobile devices run a lightweight proxy client written in J2ME to join an active space. While this approach allows a wide variety of devices to interact with active spaces, it lacks the ability to use device specific functionality. This problem is addressed by combining the J2ME client with a microserver, which is a bridge from the native language to J2ME. The microserver-proxy approach enables thin clients to fully access device-specific features while respecting security through a standard interface as Gaia services.

Pervasive Computing advocates the enhancement of physical spaces with computing and communication resources that help users perform various kinds of tasks. We call these enhanced physical spaces Active Spaces. Active Spaces are highly dynamic — the context and resources available in these evironments can change rapidly. The large number of entities present in these spaces and the dynamism associated with them make it difficult for developers to program these environments. It is not always clear at development time which resources are to be used for performing various kinds of tasks and how to use them. In this paper, we introduce a new high-level programming model for pervasive computing environments, Olympus. The main feature of this model is that developers can specify Active Space entities and common Active Space operations at an abstract, high level. Active Space entities (which include services, applications, devices, physical objects, locations and users) can be specified using high level descriptions. Our framework resolves these descriptions into actual Active Space entities based on constraints specified by the developer, ontological descriptions of entities, the resources available in the current space, space-level policies and the current context of the space. The programming model also provides the developers with operators for commonly used functions. Examples of operators include start, stop and move components. Thus, developers do not have to worry about how various tasks are performed in the space in which their program is to be deployed. These details are taken care of by the model and the developer is free to focus on the actual logic of the program. In this paper, we discuss the programming model, its implementation and several example Active Space programs that have been developed using this model.

Component technology promotes code reuse by enabling the construction of complex applications by assembling off-the-shelf components. However, components depend on certain characteristics of the environment in which they execute. They depend on other software components and on hardware resources. In existing component architectures, the application developer is left with the task of resolving those dependencies, i.e. making sure that each component has access to all the resources it needs and that all the required components are loaded. Nevertheless, according to encapsulation principles, developers should not be aware of the component internals. Thus, it may be difficult to find out what a component really needs. In complex systems, such as the ones found in modern distributed environments, this manual approach to dependency management can lead to disastrous results. Current systems rely heavily on manual configuration by users and system administrators. This is tolerable now, when users have to manage a few computers. But, in the near future, people will have to deal with thousands of computing devices and it will no longer be acceptable to require the user to configure each of them. This paper presents the results of our 6 year research (from 1998 to 2003) in the area of automatic configuration, describing an integrated architecture for managing dependencies in distributed component-based systems. The architecture supports automatic configuration and dynamic resource management in distributed heterogeneous environments. We describe a concrete implementation of this architecture, present experimental results, and compare our approach to other works in the area. Copyright © 2005 John Wiley & Sons, Ltd.

We examine the problem of providing useful feedback about access control decisions to users while controlling the disclosure of the system's security policies. Relevant feedback enhances system usability, especially in systems where permissions change in unpredictable ways depending on contextual information. However, providing feedback indiscriminately can violate the confidentiality of system policy. To achieve a balance between system usability and the protection of security policies, we present Know, a framework that uses cost functions to provide feedback to users about access control decisions. Know honors the policy protection requirements, which are represented as a meta-policy, and generates permissible and relevant feedback to users on how to obtain access to a resource. To the best of our knowledge, our work is the first to address the need for useful access control feedback while honoring the privacy and confidentiality requirements of a system's security policy.

Ubiquitous computing envisions an environment where physical and digital devices are seamlessly integrated. Users can access their applications and data anywhere in the environment. Applications are not bound to any single device and can migrate with the user to different environments. Therefore, application mobility is an important aspect of ubiquitous computing. We consider the problem of migrating applications across different ubiquitous computing environments (i.e. across different rooms, buildings or even cities). Migration is a tough problem because different environments have different resources (devices or services) available. The context of the environments may be different as well. Hence, mobile applications must adapt to changing contexts and resource availabilities as they migrate from one environment to the next. We introduce the notion of polymorphic applications, where applications can change their structure in order to adapt to different environments. While the structure of polymorphic applications can change during migration, the functionality and the state of the application are preserved as far as possible. This enables users to perform the same tasks as they move from one environment to the next, seamlessly. We make use of ontologies to ensure that the initial and final structures of a migrating application are semantically similar in terms of functionality and behavior. This paper describes our framework for enabling mobile polymorphic applications.

One of the factors that differentiates ubiquitous computing from traditional distributed computing is context. Context, such as time, location, and situation, allows a system to adapt to the current surroundings in order to facilitate the use of the computational environment. In this paper, we present a file system for ubiquitous computing applications that is context-aware. Context is used to support the types of applications and devices that are found in ubiquitous computing spaces. Novel features of the system include how the view of data adapts to the activity being currently performed and how user data is imported into the local environment. Our system is evaluated as part of a ubiquitous computing infrastructure deployed in a seminar room to investigate issues of performance, scalability, and usability.

Ubiquitous computing has fueled the idea of constructing sentient, information-rich "smart spaces" that extend the boundaries of traditional computing to encompass physical spaces, embedded devices, sensors, and other machinery. To achieve this, smart spaces need to capture situational information so that they can detect changes in context and adapt themselves accordingly. However, without considering basic security issues ubiquitous computing environments could be rife with vulnerabilities. Ubiquitous computing environments impose new requirements on security. Security services, like authentication and access control, have to be non-intrusive, intelligent, and able to adapt to the rapidly changing contexts of the spaces. We present a ubiquitous security mechanism that integrates context-awareness with automated reasoning to perform authentication and access control in ubiquitous computing environments.

The proliferation of wireless networks, hand-held PCs, touch panels, large flat displays, sensors, and embedded devices is transforming traditional habitats and living spaces into ubiquitous computing environments, or active spaces. We envision a middleware software infrastructure that abstracts the heterogeneity of these environments and transforms them into programmable environments. This middleware infrastructure provides support to manage the resources contained in an active space (low-level functionality), support to develop applications (application-level functionality), and support to define interaction rules among applications (active space-level functionality). In this paper, we present a mechanism called "application bridge" that implements active space-level functionality. Application bridges provide a simple, yet effective, mechanism to define dynamic application composition interaction rules that confer the active space a specific behavior based on a number of parameters, including context, application status, and user actions.

We investigate the cost of changing access control policies dynamically as a response action in computer network defense. We compare and contrast the use of access lists and capability lists in this regard, and develop a quantitative feel for the performance overheads and storage requirements. We also explore the issues related to preserving safety properties and trust assumptions during this process. We suggest augmentations to policy specifications that can guarantee these properties in spite of dynamic changes to system state. Using the lessons learned from this exercise, we apply these techniques in the design of dynamic access controls for dynamic environments.

Active networks aim to provide a software framework that enables network applications to customize the processing of their communication packets. Security is of critical importance to the success of active networking. This paper presents a design and a description of the implementation for securing the node of an active network using active networking principles. The secure node architecture includes an active node operating system security API, an active security guardian, and quality of protection (QoP) provisions. The architecture supports highly customized and situational policies created by users and applications dynamically. It permits active nodes to satisfy the application-specific dynamic security and protection requirements. The secure node architecture can provide a fundamental base for securing the active network infrastructure. We describe the integration of secure node architecture into an active network software system to demonstrate its flexible and innovative features.

Active Spaces are physical spaces augmented with heterogeneous computing and communication devices along with supporting software infrastructure. This integration facilitates collaboration between users, and promotes greater levels of interaction between users and devices. An Active Space can be configured for different types of applications at different times. We present an access control system that automates the creation and enforcement of access control policies for different configurations of an Active Space. Our system explicitly recognizes different modes of cooperation between groups of users, and the dependence between physical and virtual aspects of security in Active Spaces. Our model provides support for both discretionary and mandatory access control policies, and uses role-based access control techniques for easy administration of users and permissions. We dynamically assign permissions to user roles based on context information. We show how we can create dynamic protection domains. This allows administrators and application developers the ability to customize access control policies on a need-to-protect basis. We also provide a semi-formal specification and analysis of our model and show how we preserve safety properties in spite of dynamic changes to access control permissions.

Ubiquitous computing is poised to revolutionize the way we compute and interact with each other. However, unless privacy concerns are taken into account early in the design process, we will end up creating a very effective distributed surveillance system, which would be a dream come true for electronic stalkers and "big brothers". We present a protocol, which preserves the privacy of users and keeps their communication anonymous. In effect, we create a "mist" that conceals users from the system and other users. Yet, users will still be able to enjoy seamless interaction with services and other entities that wander within the ubiquitous computing environment.

This paper discusses the design and implementation for supporting customized security services in active networks using active networking principles. The customized security services support is based on a secure node architecture that includes an active node operating system security API, an active security guardian, and quality of protection provisions. The support of highly customized security services permits active nodes to satisfy the application-specific dynamic security and protection requirements. It associates quality of protection with network software and application security. Applications can dynamically select the suitable security configurations and services at each active routing node, based on their security and performance requirements. The secure node architecture, together with the support of dynamically customized security services, can provide a fundamental base for securing the active network infrastructure and active applications.

We discuss our approach to constructing a dynamic and secure smart home environment and tackling the challenges associated with it. We envision a smart home as an active environment populated with smart, dynamically configurable consumer devices capable of interacting with humans and other smart devices. In such a dynamic and active environment, there is a great need for an agile, lightweight, distributed security mechanism. This security mechanism needs to be programmable and able to evolve as rapidly as the environment itself. Yet, this mechanism should be able to adapt to environments with scarce resources. We present Tiny SESAME to meet these challenges while utilizing Jini/sup TM/ technology from Sun Microsystems to handle the common parts of distributed devices. Tiny SESAME is a lightweight component-based, Java-implementation of a subset of SESAME. SESAME is an extension to Kerberos that supports public key technologies, access control, and delegation of access rights. We discuss our Tiny SESAME and how it could be integrated with handheld and consumer devices.

The first decades of the new millennium will witness an explosive growth in the number and diversity of networked devices and portals. We foresee high degrees of mobility, heterogeneity, and interactions among computing devices connected to global networks. While previous research in distributed operating systems solved many problems related to resource management, they seldom addressed the problems of heterogeneity and dynamic adaptability. On the other hand, middleware solutions, like CORBA and Java/Jini, solve part of the heterogeneity problem by permitting seamless communication among different platforms. But, they do not address dynamic resource management and adaptability for applications requiring high-performance distributed computing. This paper presents 2K, an integrated operating system architecture that addresses the problems of resource management in heterogeneous networks, dynamic adaptability and configuration of component-based distributed applications.

This paper proposes two frameworks for secure multicast on active networks. The frameworks exploit the computational power of active networks to provide the security desired for multicast, while removing drawbacks in traditional approaches, The main security component in the frameworks is the active capability (AC) which replaces the passive session key. The main advantages of using an AC are lack of an asymmetric key pair requirement for authentication, lack of session key modification requirement when a member leaves the group and a highly distributed and scalable key distribution mechanism independent of availability of a group owner.

Network support for reliable sender-initiated multicast can aid software distribution, server-pushing of web-pages as well as pushing of prerecorded audio and video. Currently, bandwidth availability and propagation delays between the sender and the different recipients differ by many orders of magnitude. Hence, an important problem which needs to be addressed for facilitating reliable sender-initiated multicast is this problem of network heterogeneity. Prior work in reliable multicast either presents solutions to transmit at the rate of the bottleneck link of the entire multicast tree, or assumes knowledge of static bandwidth to each of the recipients. We propose an algorithm which does not make these assumptions but partitions the set of recipients on the basis of the available bandwidths at the time when the multicast is started; it then transmits separately to each set of recipients sharing a common quality of service (QoS). To the best of our knowledge, this is a first such solution. To achieve these goals, we propose (i) an algorithm to divide the set of receivers into classes with similar QoS, and (ii) callbacks for error recovery in reliable multicast. Our algorithm makes use of L4 switching at the routers but assumes the state at the routers to be soft state. Using analysis, we show our algorithm to be scalable for certain restricted network characteristics.

Computer users are increasingly multi-device equipped and no longer sedentary. It is desirable that the execution environment in any of these devices be customized to the user preferences and to the device characteristics. This paper describes a framework for managing execution environments in 2K, an adaptable, distributed, network-centric, user- and application-oriented operating system aimed at accommodating change. A 2K environment is a container of components, devices and configuration parameters and provides an execution context for the user within the 2K distributed system. A user has a distributed execution environment that consists of several subenvironments running on different platforms or temporarily suspended to be resumed later. The management of the execution environments is designed to provide a user-centric view of the system; it facilitates user mobility, by liberating users from the restriction of being explicitly attached to specific platforms, and by seamlessly recruiting resources where they are available.

A large number of protection domain crossings and context switches is often the cause of bad performance in complex object-oriented systems. We have identified the CompositeCall pattern which has been used to address this problem for decades. The pattern modifies the traditional client/server interaction model so that clients are able to build compound requests that are evaluated in the server domain. We implemented CompositeCalls for both a traditional OS, Linux, and an experimental object-oriented μkernel, Off++. In the first case, we learned about implications of applying CompositeCall to a non-object-oriented ‘legacy’ system. In both experiments, we learned when CompositeCalls help improving system performance and when they do not help. In addition, our experiments gave us important insights about some pernicious design traditions extensively used in OS construction. Copyright © 2000 John Wiley & Sons, Ltd.

A fast, degradation-free solution for the DCT block extraction problem is proposed. The problem is defined as extracting a DCT block from a DCT compressed frame composed of DCT blocks. This problem is encountered in both video/image manipulations in the compressed domain and transcodecs, for example, converting from MPEG to Motion JPEG. Traditionally, solutions involve using the pixel domain manipulation or Chang's (1992) algorithm with approximations. The new solution expands Chang's algorithms, takes full advantage of a fast DCT algorithm, and exploits characteristics of the input DCT blocks without any approximation. The new DCT block extraction achieves 70% performance improvement without any degradation of image quality compared with the conventional solutions.

We make two observations about communications middleware: first, most middleware are similar, the differences are in their interfaces and optimizations; second, neither a fixed set of abstractions nor a fixed implementation of a set of abstractions is likely to be sufficient and well-performing for all applications. Based on these observations, we present Quarterware, a customizable middleware architecture. It abstracts basic middleware functionality, and admits application specific specializations and extensions. We demonstrate its flexibility by deriving implementations for core facilities of CORBA, RMI, and MPI. The performance results show that the derived implementations equal or exceed the performance of corresponding native versions. These results suggest that customizing middleware on a per-application basis is an effective approach for building robust, high-performance applications.

Parallel programs running on top of generic protocols (e.g. TCP) in a cluster of workstations often do not perform or scale as well as one would expect. One reason for this is that both the performance and scalability of parallel applications are highly dependent on the speed of communication, yet the generic protocols used to guarantee reliable message delivery add unnecessary overhead which degrades the performance of the parallel application. The main thesis we explore in this paper is that it is possible to use knowledge of application behavior to design protocols that are more efficient. In particular, we investigate automatic techniques for generating optimized application-specific network protocols for parallel applications running on unreliable networks. Our algorithms assume that the application communication can be represented by a context free grammar. Such algorithms form the basis for a communication compiler.

Dynamic process migration supports load sharing and processor fault tolerance. We present the new freeze free algorithm for process migration, which uses six techniques to: reduce process migration latency by an order of magnitude to 19.9 ms, effectively eliminate message freeze times, and to support processor fault tolerance. The freeze free algorithm resumes execution after the transfer of four items: the combined process control and execution state, the current code page, the current heap page, and the current code page. The algorithm effectively eliminates message freeze time by separating the process state from the communication state, and thus allows message processing to proceed in parallel with process migration. The algorithm eliminates old host residual dependencies by flushing old host resident, modified data; while the process executes in parallel on the new host. The paper analyzes the costs in both the process migration latency period and the cross-network demand paging operations, and identifies further cost reductions. This paper demonstrates that small overhead is needed for good load sharing system speedup by measuring the impact of increasing overhead an speedup.

Tracking the changing dynamics of object-oriented frameworks[5], design patterns[7], architectural styles[8], and subsystems during the development and reuse cycle can aid producing complex systems. Unfortunately, current object-oriented programming tools are relatively oblivious to the rich architectural abstractions in a system.This paper shows that architecture-oriented visualization, the graphical presentation of system statics and dynamics in terms of its architectural abstractions, is highly beneficial in designing complex systems. In addition, the paper presents architecture-aware instrumentation, a new technique for building efficient on-line instrumentation to support architectural queries. We demonstrate the effectiveness and performance of the scheme with case studies in the design of the Choices object-oriented operating system.

The paper describes the design of the /spl mu/Choices object-oriented multimedia operating system. /spl mu/Choices provides an architecture for interconnecting different OS subsystems, with these subsystems realized as separate modules. The modules are implemented as independent object-oriented frameworks. Frameworks interact through exported abstract interfaces. The sub-classing of components within frameworks enables application and media-specific customization. /spl mu/Choices also provides a unified scheme for memory handling and passing across, as well as between, all OS subsystems. This allows buffer transfers and manipulation within and between operating system modules without copying, while allowing subsystems to specialize their views of memory buffers for efficient handling of problem-specific behavior. Interpreted agents may be embedded in the kernel that can control system level processing of multimedia streams without interference, eliminating excessive system call overhead. Operating system support for authentication, encryption, and delegation is transparently provided via an extensible framework that customizes interfaces to operating system resources. A new networking subsystem based on an asynchronous transfer mode network environment allows quality of service guarantees within the network protocol stack. These features are combined in /spl mu/Choices to give an environment that supports high bandwidth multimedia streams.

In this paper, we present techniques to improve the performance of parallel and distributed applications running on distributed systems built with unreliable local-area networks. The optimizations tailor the message passing system used by the application to the communication pattern exhibited by the application. The optimizations are global and application dependent since communication patterns vary from application to application. The techniques improve both the execution times and scalability of many parallel applications as well as distributed system services.

Software specification and implementation techniques based on state machines simplify design, coding, and validation. However, large systems require complex state machines. Incremental construction techniques can control this complexity. In this paper, we present a construction technique that permits derivation of complex state machines from simpler state machines. The technique uses subclassing, composition, delegation, and genericity to incrementally modify and combine simpler machines.In addition, we present a novel implementation technique that uses exactly one table-lookup and one addition to dispatch events on derived state machines, no matter the depth of the derivation. As an example, we describe the derivation of a complicated distributed virtual memory scheme from a simple paging virtual memory scheme.

No abstract available.

The comparative performance is studied of different message passing system designs experimentally on a shared memory Encore Multimax multiprocessor. The systems are measured both by benchmarks and by running example parallel applications. To act as a control, the shared memory machine results are compared with the performance of the benchmarks and applications on the Intel iPSC/2 running the NX/2 operating system. The design alternatives considered are buffering, buffer organization, reference and value semantics, synchronization, coordination strategy and the location of the system in user or kernel space. The results include measurements of the effects of the design alternatives, memory caching, message sizes and copying.>

This paper discusses the design of a switch for high-speed computer networking at gigabit rates. We present the Pulsar switch, a non-blocking design based on a high-spin-rate, port-dedicated, word-parallel, shift-register ring. Several design alternatives address the problem of Head-Of-Line blocking. In contrast to Batcher-Banyan switches, access to the ring is asynchronous which facilitates low delay and arbitrary packet length. The switch can support ATM cells simultaneously with packets sized for applications such as single characters, memory words, disk blocks, memory pages, or video images. Pulsar can be used as a high-throughput computer backplane replacement. The design can be implemented with existing high-speed circuit technology.

The Choices operating system architecture [?, ?, ?] uses class hierarchies and object-oriented programming to facilitate the construction of customized operating systems for shared memory and networked multiprocessors. The software is being used in the Tapestry Parallel Computing Laboratory at the University of Illinois to study the performance of algorithms, mechanisms, and policies for parallel systems. This paper describes the architectural design and class hierarchy of the Choices memory and secondary storage management system. The mechanisms and policies of a virtual memory system implement a memory hierarchy that exploits the trade-offs between response times and storage capacities. In Choices, the notion of a memory hierarchy is represented by layers in which abstract classes define interfaces between and internal to the layers. Concrete subclasses implement new algorithms or data structures or specializations of existing ones. This paper describes the motivation for an objecto...

A configuration management system organizes large software systems and helps maintain those systems over a long lifetime. The problems that arise in the design of such a tool include the manipulation and accurate representation of system configurations, versions and derivation histories. Access control, the large quantities of data, and the evolutionary nature of software development all help to compound the problems. The SAGA (Software Automation, Generation and Administration) project has developed CLEMMA, a configuration librarian. CLEMMA uses relational database technology to provide a powerful but compact configuration management system. It is based on an extended relational model of software development in which components have an object-oriented representation. The authors present the design of CLEMMA and discuss its solutions to the problems of configuration management.>

The programming of the interrupt handling mechanisms, process switching primitives, scheduling mechanism, and synchronization primitives of an operating system for a multiprocessor require both efficient code in order to support the needs of high- performance or real-time applications and careful organization to facilitate maintenance. Although many advantages have been claimed for object-oriented class hierarchical languages and their corresponding design methodologies, the application of these techniques to the design of the primitives within an operating system has not been widely demonstrated. To investigate the role of class hierarchical design in systems programming, the authors have constructed the Choices multiprocessor operating system architecture the C++ programming language. During the implementation, it was found that many operating system design concerns can be represented advantageously using a class hierarchical approach, including: the separation of mechanism and policy; the organization of an operating system into layers, each of which represents an abstract machine; and the notions of process and exception management. In this paper, we discuss an implementation of the low-level primitives of this system and outline the strategy by which we developed our solution.

A framework for the provision of fault tolerance in asynchronous systems is introduced. The proposal generalizes the form of simple recovery facilities supported by nested atomic actions in which the exception mechanisms only permit backward error recovery. It allows the construction of systems using both forward and backward error recovery and thus allows the exploitation of the complementary benefits of the two schemes. Backward recovery, forward recovery, and normal processing activities can occur concurrently within the organization proposed. Exception handling is generalized to provide a uniform basis for fault tolerance schemes with the atomic action structure. The generalization includes a resolution scheme for concurrently raised exceptions based on an exception tree and an abortion scheme that permits the termination of the internal atomic actions. An automatic resolution mechanism is outlined for exceptions in atomic actions which allows users to separate their recovery schemes from the details of the underlying algorithms.

Two complementary techniques have evolved for providing fault-tolerance in software: forward error recovery and backward error recovery. Few implementations permit both approaches to be combined within a particular application. Fewer techniques are available for the construction of fault-tolerant software for systems involving concurrent processes and multiple processors. Many schemes for supporting forward or backward recovery are based on some concept of an atomic action. The authors propose a mechanism for supporting an atomic action in a system of communicating sequential processes (CSP). The atomic action is used as the basic unit for providing fault-tolerance. The atomic action is called an FT-action, and both forward and backward error recovery are performed in the context of an FT-action.

We present a new protocol, called the Delay /Re-Read Protocol, for controlling concurrent access to a database. The protocol uses a combination of preventive and corrective measures for maintaining consistency. On recognizing that a transaction has read inconsistent data, the Protocol applies a corrective measure which requires the transaction to re-read some data. Alternatively, on recognizing that a transaction is about to write data which will result in inconsistency, the Protocol applies a preventive measure which delays the Write. A Read request is always granted without delay. The Protocol is deadlock-free, requires no backup data, and supports a greater degree of concurrency than Two Phase Locking. A transaction is never aborted or delayed indefinitely by the Protocol.

One of the requirements for building an operating system in a high-level operating system language, such as Ada, Concurrent Pascal, or Modula, is the construction of a language support system, or kernel. This paper presents a model that generalizes the concept of a kernel, and defines a kernel and the processes it supports to be at different levels of abstraction. A high-level language mechanism, the Execute statement, is then proposed as the basis of the interface between a kernel and the processes it supports. Software capabilities control access between levels and the Execute statement controls processor context switching between levels. The mechanisms rely on data typing for reliability and protection. They encourage systems that are well protected and exhibit an explicit hierarchical structure. Software capabilities and the Execute statement are illustrated with a pilot implementation on the Prime 650. An experimental operating system that encompasses their use is discussed. Extensions are presented which manage interrupts, timeslicing and preemption, and hardware protection mechanisms.

Petri nets are used to define a path and process notation which is more general in its ability to express synchronization than previous path notations. The Petri net classes corresponding to the path notation prove to be interesting in their own right and have demonstrable properties such as liveness and safeness.