We consider access control for IoT systems that involves shared accesses to the IoT devices as well as their data. Since IoT devices are dispersed all over the edge of the Internet, traditional centralized access control has problems. Blockchain based decentralized access control is thus the new solution trend. However, existing blockchain based access control methods do not focus on performance issues and may incur a high communication overhead. In this paper, we develop a Pruned Blockchain based Access Control (PBAC) protocol to cutdown the unnecessary message rounds and achieve high efficiency in access validations and policy management. To realize the PBAC protocols, it is necessary to carefully engineer the system architecture, which is also discussed in the paper. Experiments demonstrate the efficacy of the PBAC protocol, specifically, it reduces the access validation time by approximately $43 \%$.

We consider an IoT system where IoT devices are ubiquitous, distributed all over the environment. When some situation arises dynamically, the IoT services may collaborate to cope with the situation in a timely manner. During such collaboration, the collaborating IoT devices may have to access each other in order to accomplish the task. The accesses could involve the information and/or the control. To avoid causing security and privacy problems, sharing requires proper access control. Since there exists no preestablished security domain and the collaborating entities could belong to any owners, such as individuals, companies, organizations, and government agencies, the access control task in such open environment can be challenging. In this paper, we first survey existing access control models and analyze their suitability for such open IoT systems. Then, we propose a new model, Role-InverseView (RIV), for access control in open systems. In conventional role-based access control (RBAC) models, roles are defined by the security officers of an organization and are for subjects internal to the organization. In an open system, there is no predefined set of subjects and accessors could be anyone in the world. In RIV, we consider an inverse view of RBAC. Specifically, the owner of the resources defines its own version of roles and role hierarchy based its own view of the world of subjects who may access its IoT data and services. Permissions can then be defined on these owner defined roles. However, how to map the accessors to these RIV roles is an issue. We propose to mine the accessor information from the Internet and determine the role assignment accordingly. An infrastructure design is also presented to achieve efficient role mining and access validation.

In this paper, we consider the IoT data discovery problem in very large and growing scale networks. Specifically, we investigate in depth the routing table summarization techniques to support effective and space-efficient IoT data discovery routing. Novel summarization algorithms, including alphabetical based, hash based, and meaning based summarization and their corresponding coding schemes are proposed. The issue of potentially misleading routing due to summarization is also investigated. Subsequently, we analyze the strategy of when to summarize in order to balance the tradeoff between the routing table compression rate and the chance of causing misleading routing. For experimental study, we have collected 100K IoT data streams from various IoT databases as the input dataset. Experimental results show that our summarization solution can reduce the routing table size by 20 to 30 folds with 2-5% increase in latency when compared with similar peer-to-peer discovery routing algorithms without summarization. Also, our approach outperforms DHT based approaches by 2 to 6 folds in terms of latency and traffic.

Internet of Things (IoT) interconnects billions of smart sensors, devices, actuators, as well as people, over a distributed environment. To make further use of these things towards a better and smarter physical world, it is necessary to dynamically compose the IoT services to handle complex, dynamically arising tasks. In this paper, we consider how to efficiently discover and compose IoT services to achieve some given goals. When a dynamic task arises, a distributed planning is taken place over the IoT network to discover the needed available IoT services and how to compose them. To ensure planning efficiency, a Logic-based Overlay Network of Services (LONS) is maintained and updated periodically. We then develop a decentralized Graphplan based algorithm to traverse through the LONS to derive the desired service composition. An intelligent mutual exclusion consideration model in our algorithm results in an efficient backward search procedure for solution extraction. We consider different distributed planning variations and compare their tradeoffs in terms of network traffic and composition efficiency experimentally.

We consider an event-driven IoT data stream processing (DSP) model in the Edge Cloud. Periodical DSP workflows are issued dynamically to the edge. Instead of traditional deployment approach, we use a service-oriented deployment model in which the same DSP components in different workflows will be deployed as long running services. This can greatly reduce the overhead in transferring and starting DSP components. Accordingly, we develop a new edge resource allocation problem. Resources are allocated to long running services according to the statistical data flow rates to the services. Subsequently, a Robinhood greedy algorithm (RG) is developed to derive the service allocation solution. Experimental studies show that the RG algorithms can achieve allocations with significantly reduced communication cost and more balanced load compared to a baseline algorithm.

Abstract Workload prediction has been widely researched in the literature. However, existing techniques are per‐job based and useful for service‐like tasks whose workloads exhibit seasonality and trend. But cloud jobs have many different workload patterns and some do not exhibit recurring workload patterns. We consider job‐pool‐based workload estimation, which analyzes the characteristics of existing tasks' workloads to estimate the currently running tasks' workload. First cluster existing tasks based on their workloads. For a new task J, collect the initial workload of J and determine which cluster J may belong to, then use the cluster's characteristics to estimate J′s workload. Based on the Google dataset, the algorithm is experimentally evaluated and its effectiveness is confirmed. However, the workload patterns of some tasks do have seasonality and trend, and conventional per‐job‐based regression methods may yield better workload prediction results. Also, in some cases, some new tasks may not follow the workload patterns of existing tasks in the pool. Thus, develop an integrated scheme which combines clustering and regression and utilize the best of them for workload prediction. Experimental study shows that the combined approach can further improve the accuracy of workload prediction.

Role based access control (RBAC) has been widely adopted in industry and government. However, traditional RBAC is only suitable for closed enterprise environments. To enable cross-domain accesses, some role mapping schemes have been proposed to map the roles from the accessor domain to the accessee domain. As discussed in the literature, establishing role based systems is a labor intensive task and some semi-automated assistance tools have been introduced to reduce the manual efforts. Similarly, role mapping in large scale organizations can incur intense manual efforts, but there is not yet automated solutions in the literature. In this paper, we introduce a smart role mapping process, where prospective role mappings are generated automatically based on the similarities of the roles and recommended to the security officers. Based on the recommendations, the security officers can then approve or modify the mappings and achieve the role mapping task with much ease.

In this paper, we consider semantic based routing for IoT service discovery in peer-to-peer IoT networks. Due to the memory constraints on IoT and edge devices, we focus on the design of routing tables to achieve space-efficient as well as informative routing. To achieve the goal, we develop a scheme to enable routing information summarization, which is commonly used in IP based routing, but has not been done successfully in semantic based routing where keywords are the basis for addressing and lookup query specification. We combine ontology and Bloom filter to achieve summarization of IoT capabilities. To support summarization and reduce the space requirements for routing table indexing, we further developed a coding scheme, OnBF, to represent each IoT capability. Based on OnBF, we design the routing table, the summarization algorithm for the routing table, etc., to achieve efficient, multi-keyword based service discovery in IoT networks. We analytically and experimentally explore our proposed solution and the results show that our solution yields better routing, i.e., lower network traffic and almost optimal routing time (hops) for any given memory constraints for the routing table.

In this paper, we design semantic based routing algorithms for IoT service discovery. First, we consider the model for describing the IoT services and the corresponding discovery queries so that service lookup can be performed effectively. Second, we consider the limited memory space of many IoT devices and introduce our summarization algorithm for routing information compression to make sure that the routing table at each node can satisfy the space limit imposed by the node without needing to throw away useful routing information. Third, we develop a novel two-level coding mechanism to effectively code IoT service capabilities to enable summarization and further reduce routing table size. We experimentally compare various coding approaches and the results show that our scheme requires less memory and imposes lower volume of network traffic compared to existing approaches.

Inter-vehicle communication has the potential to significantly improve driving safety, but also raises security concerns. The fundamental mechanism to govern information sharing behaviors is access control. Since vehicular networks have a highly dynamic and open nature, access control becomes very challenging. Existing works are not applicable to the vehicular world. In this paper, we develop a new access control model, openRBAC, and the corresponding mechanisms for access control in vehicular systems. Our approach lets the accessee define a relative role hierarchy, specifying all potential accessor roles in terms of their relative perception to the accessees. Access control policies are defined for the relative roles in the hierarchy. Since the accessee has a clear understanding of the relative roles defined by itself, the policy definitions can be precise and less flawed.

Role based access control (RBAC) has been used extensively in practice since it naturally capturing the structure of the users in an organization. It is especially useful in multi-tenant cloud platforms. However, with the growing amount of data and growing number of devices, assigning permissions for these resources (such as data and devices) to roles become challenging. We develop a resource hierarchy based permission model and integrate it with RBAC to create the RRBAC (resource and role based access control) model to simplify the permission assignment in RBAC. However, realizing RRBAC requires careful design to ensure efficient permission assignment, validation and revocation. Instead of using policy based solutions, such as XACML, we design a resource tree based approach to achieve high performance for various permission related operations. Preliminary experiments show that RRBAC approach can achieve more efficient permission assignment and validation.

Cloud computing has been widely adopted by many companies and government entities. To ensure high quality computing resource provisioning, cloud platforms should offer smart resource management solutions. An important step toward better resource management is to accurately predict the workloads of the applications running on the cloud. Many existing workload prediction methods are regression based, which require the workloads of the applications show clear seasonality and trend. However, it is difficult to use these methods for tasks which may not have such recurring workload patterns. From careful analysis of the workloads in a real-world cloud, we found that many tasks have busty workloads that are very difficult to predict using regression-based prediction. Instead, we consider a job-pool based approach, where the knowledge about the workloads of a large pool of tasks is used to help predict the workloads of new tasks. In particular, we develop a clustering-based learning approach to realize the job-pool based concept. The pool of jobs are clustered based on their workloads, and a neuralnet is used to learn the characteristics of the workloads in each cluster. When a new job arrives, we use its initial workload pattern and submission parameters to find the cluster it belongs to. Then, the corresponding neuralnet is used to predict the workload of the new job far into the future. Based on this predicted long-term workload, smart resource management decisions can be made to reduce the potential overhead in scaling and migration. We also consider a non-clustering based learning solution and compare it with the clustering-based learning solution. Experimental results show that the clustering-based learning approach can predict the workload more accurately.

Vehicular communication can enhance the safety and effectiveness of the autonomous vehicle (AV) control process. However, existing AV communication never considers the issues of when to communicate, who to communicate with, and what information to share. We show that the answer to the when, who, and what questions are situation dependent and attempt to define a semantic model to capture a relatively complete set of situations. Based on the semantic model, we define the communication protocols that are best suited to different situations. We then experimentally show that our protocol is efficient and effective.

Many existing IoT systems are built with predefined tasks and system architecture. To make better use of the large number of “things” availability in the IoT infrastructure, we consider to dynamically discover and compose IoT capabilities in the IoT network for new or dynamically arising tasks. To achieve the goal, we develop a semantic-based routing protocol for IoT service discovery. In the routing protocol to reduce the space requirement for routing, each node maintains a routing table with a “telescopic view”, i.e., more precise information about the capabilities of immediate neighbors and only a summary of capabilities for a further away neighborhood. We define an ontology of capabilities and design a capability summarization algorithm based on the ontology to realize the telescopic view concept. We also design an ontology coding scheme to further reduce the memory requirement for routing while enabling capability summarization. Our solutions significantly reduce the routing table size and, hence, is suitable for IoT devices with limited memory. Also, experimental results show that our approach can yield significantly lower network traffic and latency for IoT capability lookup when compared with existing semantic based routing algorithms.

Many real-world applications are complex, involving many user "choices", such as different functionalities, different ways to achieve a goal, etc. Conventional automated service composition models do not consider such potential choices, or simply consider them independently. Also, existing service composition models do not model exceptions and automated composition approaches require that after an exception, the original system goal should still be achieved. This may not be feasible for some exceptions. Thus, the service composition model should also consider alternate goals after exceptions occur. In this paper, we first define the concept of multi-functionality and develop a holistic service composition model. Since most existing composition reasoning techniques can only handle a single functionality, we extend them and develop new algorithms for automated holistic service composition. A case study system is used to illustrate how our approach automatically generates a holistic workflow for a system with multiple functionalities.

Internet of Things (IoT) interconnects billions of smart sensors, devices, actuators, as well as people, over a distributed environment to work together towards a better and smarter physical world. However, technologies are still under development to allow us to most effectively make use of the ubiquitous "smart things" to accomplish the desired goals in various human activities. Service discovery is one of these technologies that can help identify the desired IoT devices for the given task. In this paper, we design an efficient peer-to-peer (p2p) service discovery algorithm in an IoT network with a mix of static and mobile IoT nodes. Our algorithm is based on unstructured p2p routing with routing information caching (RIC). Due to the limited memory on IoT nodes, we bound the cache size to fit the IoT nodes and maximize the usefulness of their RIC content. First, we build an ontology of IoT device capabilities and design a hierarchical Bloom-filter based Indexing (HBFI) to index the capabilities in the ontology. HBFI is flexible in incorporating new capabilities and offers much more space efficient representation of the routing information. Also, the cache replacement scheme of RIC considers the reference time of the entries (as conventional), the mobility of the IoT nodes, and the inclusiveness of the capability concept. Experimental evaluations show that with the same memory size constraint, our scheme can provide more effective routing information and minimize the service discovery time compared to centralized, supernode based, DHT based, flooding based, and other information caching based solutions.

In this paper, we present a new SaaS (software as a service) design for employee job performance appraisals, SaaS-JPA. We use IoT and computer systems to collect data related to the daily works of employees. A semantic model is developed to guide the data collection process, facilitate data interpretation and interoperation, and enable big data analysis to make job performance appraisal decisions. We also propose two new performance assessment models: The similarity-based relative performance model and the revenue-based performance model. These performance models are enabled by the service technologies and big data analytics. Finally, we discuss the design of SaaS-JPA.

Good resource management is very important in the cloud and workload prediction is a crucial step towards achieving good resource management. While it is possible to predict the workloads of long-running tasks based on the seasonality in their historical workloads, it is difficult to do so for tasks which do not have such recurring workload patterns. In this paper, we consider a different solution for task workload prediction. Instead of using the historical workload of a task to predict the future workload of the same task, we use the knowledge about the workloads of a pool of tasks to help predict the workloads of new tasks. In this paper, we develop a clustering and learning based approach to realize this concept. First, the workloads of existing tasks are grouped into multiple clusters. Then, neural network is used to learn the characteristics of the workloads of each cluster. For each new task, we collect its initial workload, determine its cluster, and use the trained neural network of its cluster to predict its future workload. Our approach is experimentally evaluated using Google dataset. The results confirm the effectiveness of our integrated scheme.

Power line inspection is an essential but costly task while automated UAV (unmanned aerial vehicle) inspection can greatly reduce such costs. However, navigating along power lines is a challenging task due to the narrow width and limited features of power lines. Existing power line tracking methods have threshold selection problems and cannot work well for complex and changing backgrounds. We make use of power line specific knowledge to build a model to achieve predictive and continuous parameter selection so that the best thresholds are selected for changing scenarios. Experimental studies show that our solution is much better than existing ones. Specifically, we have built the first fully automated UAV that successfully tracks power lines in the real world.

Due to multi-tenancy, access control is a very important component in SaaS (Software as a Service), especially for controlling cross-tenant accesses. Due to the potential information flow among multiple tenants, information flow control should also be carefully addressed. Existing models for SaaS access control have some limitations, especially in information flow control. In this paper, we define a new SaaS-AIFC model to provide comprehensive and improved access and information flow control in SaaS. SaaS-AIFC incorporates two advanced features. First, SaaS-AIFC integrates the advanced role mapping technique to govern the cross-tenant accesses. Role mapping is very flexible and can be very efficient for SaaS with a large number of tenants. We integrate role mapping in SaaS by developing a detailed process for mapping establishment and retrieval during validation. Second, we propose a new IFC model in SaaS-AIFC, which tracks the dependency of data objects and uses the dependency information to achieve flexible information flow control. An architecture design for realizing the SaaS-AIFC model is also proposed.

The foraging problem, which evolved from ants finding food and delivering them to the nest, is for a swarm of robots to transport objects from a source to a destination. To avoid collision of robots or congestions, object transportation is generally conducted in a pipelining manner. Existing solutions towards the foraging problem either have performance problems or cannot tolerate failures. We present a self-stabilizing solution for the swarm robotic system to form a pipeline structure to transport objects and achieve the foraging task. In this paper, we first define the stable state for the swarm, which includes two requirements: (1) the robots operate in non-overlapping regions, i.e., transport objects in a pipeline structure and (2) the transportation rate of the system is optimal. Then, we introduce our self-stabilizing algorithm for the foraging problem and prove its convergence and the correctness of its convergence properties. Due to the self-stabilization nature, our solution is decentralized and fault tolerant. The swarm can achieve the foraging task as long as there is at least one working robot. Due to the definition of the stable state, our swarm system, when converged, can achieve optimal performance. We conduct simulations to evaluate the effectiveness of our algorithm, and the experimental results show that from any state, our algorithm can converge very quickly to reach the stable state and provide optimal performance for object transportation.

The papers in this special section focus on cyber-physical systems and applications for their use. A cyber-physical system (CPS) integrates a vast variety of static and mobile resources, including sensor and actuator networks, swarms of robots, remote-controlled vehicles, critical infrastructures, control and decision software, static data and just-in-time information from sensors, knowledge, data analytics and fusion software, event driven supply chains, and humans, and offers great potential for achieving tasks that are far beyond the capabilities of existing systems [1]. Individual users, organizations, and various communities can transform the vast space of cyberphysical entities into capabilities that no single entity can achieve alone. However, these capabilities do not come easily. Intelligence is needed for just-in-time composition of resources into services. Associated challenges include how to manage the vast number and diverse varieties of static and mobile physical entities, how to describe the capabilities of the cyber-physical entities, how to decompose high level goals into low-level control commands for the individual entities, how to achieve intelligent coordination and manage information flow among the entities.

In multi-domain service-based systems, services from different domains are composed together to accomplish critical tasks. In these systems, data flow from one domain to another through the composed services. Thus, security and trustworthiness are the major concerns. Many access control models have been developed for service-based systems. Also, many data provenance schemes have been proposed in recent years to support data quality assessment and enhancement, data reproduction, etc. However, none of the existing mechanisms consider both access control and data provenance in an integrated model. In this paper, we propose an integrated role-based access control and data provenance model to secure the cross-domain interactions. We develop a role-based data provenance scheme which tracks the roles of originators/contributors of a data object and uses this information to help evaluate data trustworthiness. We also make use of the data provenance information and the derived data quality attributes to assist with cross domain access and information flow control. This integrated model mutually enhances data provenance and access control, providing better security and trustworthiness for many multi-domain service-based applications.

Service computing technologies have been widely applied to many application domains to facilitate rapid system integration for desired goals. However, existing service models need to be enhanced for cyber-physical systems (CPS) and internet-of-things (IoT). In this paper, we develop an ontology model for the specification of services in CPS/IoT. First, we discuss the major differences in modeling software services and services in CPS/IoT. Then, we propose a novel PT-SOA (PT stands for physical things) model, which is mainly extended from OWL-S, to enhance existing service models for CPS/IoT systems. Finally, we show a case study system to illustrate how our model can facilitate proper service selection and composition.

The physical world is becoming smarter and smarter due to the advances in smart devices and CPS/IoT technologies. In this paper, we investigate the roles various cutting-edge technologies, such as service computing, big data analytics, crowd sourcing, gaming technologies, etc., can play to significantly enhance the intelligence of our physical environment and subsequently benefit the society. We consider a smart physical world (SPW) consisting of physical entities, cyber entities, and human. Service technologies can be used to model the entities in SPW and specify their capabilities. Service discovery and composition techniques can be used to, based on the modeling, compose these capabilities to solve real-world problems. To enable higher level intelligence, we further discuss how various technologies, such as big data analytics and artificial intelligence, can be used in the smart world to reason from sensor inputs to derive the situation facts, and from the situation facts to derive the reactive actions. From the derived actions (tasks), the service technologies can be used to compose the capabilities of the entities to realize the task. However, current technologies and artificial intelligence may fall short in many situations. We further propose a gaming-based crowd sourcing platform to make use of human intelligence to enable successful completion of some challenging reasoning and control tasks.

In cloud computing, good resource management can benefit both cloud users as well as cloud providers. Workload prediction is a crucial step towards achieving good resource management. While it is possible to estimate the workloads of long-running tasks based on the periodicity in their historical workloads, it is difficult to do so for tasks which do not have such recurring workload patterns. In this paper, we present an innovative clustering based resource estimation approach which groups tasks that have similar characteristics into the same cluster. The historical workload data for tasks in a cluster are used to estimate the resources needed by new tasks based on the cluster(s) to which they belong. In particular, for a new task T, we measure T's initial workload and predict to which cluster(s) it may belong. Then, the workload information of the cluster(s) is used to estimate the workload of T. The approach is experimentally evaluated using Google dataset, including resource usage data of over half a million tasks. We develop a workload model based on the dataset which is then used to estimate the workload patterns of several randomly selected tasks from the trace log. The results confirm the effectiveness of this cluster-based method for estimating the resources required by each task.

Existing share access protocols require the client to retrieve all shares even for read accesses in order to achieve atomic semantics. In cloud storage with widely distributed servers, this implies significant communication latency (from client to the farthest server) and additional network traffic. In this paper, we consider a nearby share retrieval approach to improve read performance. We first analyze the impact of this approach on the consistency semantics. Then we present the nearby share retrieval (NSR) protocol that satisfies regular semantics and guarantees wait-free reads. Experimental results show that our protocol yields significantly better read performance than existing protocols. To further optimize the performance of read accesses, we setup experiments to analyze the performance impacts of the number of shares to be retrieved in one round. Experimental results show that for most of the data, using the least required number (the threshold number in (n, k) data partitioning schemes) yields the best performance. But for hot data (with high access rates), access more servers in one round can achieve better performance.

We present a planner for addressing a difficult, yet under-investigated class of planning problems: Fully Observable Non-Deterministic planning problems with strong solutions. Our strong planner employs a new data structure, MRDAG (multi-root directed acyclic graph), to define how the solution space should be expanded. We further equip a MRDAG with heuristics to ensure planning towards the relevant search direction. We performed extensive experiments to evaluate MRDAG and the heuristics. Results show that our strong algorithm achieves impressive performance on a variety of benchmark problems: on average it runs more than three orders of magnitude faster than the state-of-the-art planners, MBP and Gamer, and demonstrates significantly better scalability.

As the green house gas emission becomes a serious problem, a lot of researches now focus on how to monitor and manage carbon footprint (CF) of a production process or transportation, especially in the supply chain. Usually, most of the carbon footprint management systems are based on databases. But database is not sufficient in describing the production and transportation processes and the facilities used in these processes. In this paper, we develop an SOA based model for the carbon footprint management and labeling (CFML), using ontology and OWL-S techniques. We use OWL-S to describe the processes and workflows for production and transportation and extend it to specify the methods for deriving CF of them. We use the existing energy conversion formula to derive the CF when the energy data can be collected separately. We also derive an approach to separate the CFs when data of different processes have to be collected together. In a supply chain, a production company may have different choices of suppliers to provide certain components. To balance the tradeoff between carbon dioxide emission and cost of the overall production process, we design a supplier selection algorithm to derive the optimal solution.

Service-oriented architecture provides a framework for achieving rapid system composition and deployment. To satisfy different system QoS requirements, it is possible to select an appropriate set of concrete services and compose them to achieve the QoS goals. In addition, some of the services may be reconfigurable and provide various QoS tradeoffs. To make use of these reconfigurable services, the composition process should consider not only service selection, but also configuration parameter settings. However, existing QoS-driven service composition research does not consider reconfigurable services. Moreover, the decision space may be enormous when reconfigurable services are considered. In this paper, we deal with the issues of reconfigurable service modeling and efficient service composition decision making. We introduce a novel compositional decision making process, CDP, which explores optimal solutions of individual component services and uses the knowledge to derive optimal QoS-driven composition solutions. Experimental studies show that the CDP approach can significantly reduce the search space and achieve great performance gains. We also develop a case study system to validate the proposed approach and the results confirm the feasibility and effectiveness of reconfigurable services.

Enforcing access control in composite services is essential in distributed multidomain environment. Many advanced access control models have been developed to secure web services at execution time. However, they do not consider access control validation at composition time, resulting in high execution-time failure rate of composite services due to access control violations. Performing composition-time access control validation is not straightforward. First, many candidate compositions need to be considered and validating them can be costly. Second, some service composers may not be trusted to access protected policies and validation has to be done remotely. Another major issue with existing models is that they do not consider information flow control in composite services, which may result in undesirable information leakage. To resolve all these problems, we develop a novel three-phase composition protocol integrating information flow control. To reduce the policy evaluation cost, we use historical information to efficiently evaluate and prune candidate compositions and perform local/remote policy evaluation only on top candidates. To achieve effective and efficient information flow control, we introduce the novel concept of transformation factor to model the computation effect of intermediate services. Experimental studies show significant performance benefit of the proposed mechanism.

Artificial intelligence (AI) planners have been widely used in many fields, such as intelligent agents, autonomous robots, web service compositions, etc. However, existing AI planners share a common problem: When given a problem to solve, they either return a solution if one exists or report that no solution is found. However, simply reporting failure leaves no clues for people to trace the causes of the planning failure. In this paper, we present a novel approach that can propose virtual actions in the event of planning failure. Virtual actions enable traditional planners to succeed and hence return an incomplete plan instead of merely an error message. More importantly, the specifications of the virtual actions suggest what the missing parts may contain, thus providing important clues to users as to the nature of the failure. Experimental results show that our approach constantly returns useful and comprehensible information for humans, thus making AI planning more practical when solving real-world problems.

Although reuse is the main goal of SOA, composing existing services to realize different user requirements is still a difficult and time-consuming task. Research on workflow templates and design patterns can facilitate reuse and assist with the service composition task. Nevertheless, workflow templates are too specific, whereas design patterns may be too abstract; their effectiveness in assisting the composition process may be limited. In this paper, we propose a comprehensive service pattern model that is more flexible than workflow/service templates while allowing systematic instantiation into the concrete workflows. It can help ease the composition process and enable flexible pattern-based reuse.

In this paper, we consider the design issues in building robotic swarm systems as a service and develop a multi-level service-oriented robotic swarm (SORS) framework. First we consider how to support easy composition of services into workflows to accomplish user tasks. We identify a set of primitive virtual services for this purpose. Virtual services are not physical robotic swarm actions, but are high-level primitive services geared toward easy specification of the workflows of many tasks. To realize virtual services, SORS incorporates the layers of planning services and micro services to plan and control the swarm of robots. Two example micro services and the detailed algorithms in their implementation are given in the paper. Also, a case study system is developed to show the use of virtual services to specify the workflow for an example task and to illustrate the design of micro services to realize virtual services.

We propose a QoS and power management (QPM) framework for mobile devices making use of the service cloud. Several techniques for the realization of the QPM framework have been developed. First, we develop a function pool based prediction model to predict the power and QoS behaviors of the task activated by a mobile device. Based on the prediction, we design the cost function and the decision algorithm for selecting the best platforms for executing the services/applications in order to achieve optimal energy saving while satisfying QoS requirements. Several service and data migration policies have been designed for a service to be migrated and executed on a mobile device to achieve power and QoS gains. We apply the QPM framework and associated techniques to a facial recognition case study system to validate our approach. Experimental results show that, in the best case, the QPM framework can achieve 66.7% energy saving for the mobile device and at the same time, reduce the response time by 54.3%.

A swarm of robots deployed in dynamic, hostile environments may encounter situations that can prevent them from achieving optimality or completing certain tasks. To resolve these situations, the robots must have an adaptive software system that can proactively cope with changes. This adaptive system should emulate the intelligence of human reasoning and common sense but must not assume that the robots can communicate, be tightly coupled, or be constantly at a close range. This paper presents a path strategy evaluator (PSE) that learns an optimal path by considering not just the distance, but also how to minimize damages to each robot and enhance the likelihood that the swarm will succeed in its mission, all with minimal impositions on the functionality of the robots. Our evaluation shows that this PSE is able to learn a dynamic environment and its effect on the robots' critical components and output an optimal path for the robots.

Service cloud provides added value to customers by allowing them to compose services from multiple providers. Most existing web service security models focus on the protection of individual web services. When multiple services from different domains are composed together, it is critical to ensure the proper information flow on the chain of services. In a service chain, each service needs to determine whether the sensitive information can be directly or indirectly disseminated to the subsequent services. Also, each service in the chain needs to decide whether to accept the data passed to it directly or indirectly from prior services. Moreover, the input data that service si receives from si-1, si. InF, may cause certain side effects inside si, such as updating si's backend database using data computed from si. InF. Service si may wish to allow such side effects in one situation while reject some side effects in another situation. All these decisions should be made based on the service's information flow control policies. To achieve fine-grained information flow control, it is also necessary to analyze the flow and processing of the data and derive the dependencies between the data dynamically generated or used in a service chain. In this paper, we develop a run-time information flow control model for service cloud. First, we develop a run-time dependency analysis mechanism which enables each service in the service chain to determine the correlation between the locally accessed data and the data dynamically generated by the services in the service chain. Then, we develop a model to enable each service in a service chain to specify policies on how its sensitive information can be released to its subsequent services and what types of input data from prior services can be accepted and how they can flow within the services. Finally, we design a run-time protocol to enforce these policies in a service chain.

We address a difficult, yet under-investigated class of planning problems: fully-observable nondeterministic (FOND) planning problems with strong cyclic solutions. The difficulty of these strong cyclic FOND planning problems stems from the large size of the state space. Hence, to achieve efficient planning, a planner has to cope with the explosion in the size of the state space by planning along the directions that allow the goal to be reached quickly. A major challenge is: how would one know which states and search directions are relevant before the search for a solution has even begun? We first describe an NDP-motivated strong cyclic algorithm that, without addressing the above challenge, can already outperform state-of-the-art FOND planners, and then extend this NDP-motivated planner with a novel heuristic that addresses the challenge. 1

Robotic swarm systems have many important applications, such as assisting with search and rescue missions, exploring space-based environments, etc. They provide the capability of performing tasks that may be beyond the means of individual robots, such as carrying heavy loads, maneuvering over complex terrains, etc. For mission-critical and/or safety-critical applications, it is important to ensure that the system deployed is highly dependable. In this paper, we present a highly resilient swarm system framework to support Resilient Operational Basis for Ultrahigh Survivable and Trustworthy (ROBUST) robotic swarm systems operating in unknown environments. The framework consists of important characteristics that are necessary for achieving ROBUST swarm systems operating in unknown, hostile environments in order to be able to dependably accomplish their specified missions.

In a large-scale collaborative filtering system, pair wise similarity between users is usually measured by users' ratings on the whole set of items. However, this measurement may not be well defined due to the sparsity problem, i.e., the lack of adequate ratings on items for calculating accurate predictions. In fact, most correlated users have similar ratings only on a subset of items. In this paper, we consider a kernel-based classification approach for collaborative filtering and propose several kernel matrix construction methods by using biclusters to capture pair wise similarity between users. In order to characterize accurate correlation among users, we embed both local information and global information into the similarity matrix. However, this similarity matrix may not be a kernel matrix. Our solution is to approximate it with the matrix close to it and use low rank constraints to control the complexity of the matrix.

In this paper we develop a SCADA key management system to provide better security, performance, and scalability. Conventional symmetric key based approaches have several problems. We adopt public key based approaches due to its flexibility in authentication and access control and efficiency in rekeying. However, existing public key based approaches are not scalable. Simple replication of CAs (certificate authorities) raises security concerns. We consider several novel designs to bridge the gaps in existing approaches. First, a master key based semi-autonomous key refreshing scheme has been developed to shift the rekeying burdens from CAs to individual SCADA node. Then, we design a CA-grid approach, which combines the threshold scheme and replication of CAs to achieve better protection of the master keys, improved availability, and enhanced performance by load sharing. Analyses show that our scheme has many advantages than the existing SCADA key management systems.

Most existing works on data partitioning techniques simply consider to partition data objects and distribute the shares to servers. Such pure data partitioning approaches may bring potential performance and scalability problems when used in widely distributed systems. First, it is difficult to apply lazy update. Second, the share consistency verification may incur costly communications among widely distributed servers. In this paper, we propose a two-level DHT (TDHT) approach for widely distributed cloud storage to address these problems. First, we analyze the tradeoffs on security and availability between TDHT and the conventional pure data partitioning approach (integrated with DHT and called GDHT (global DHT)). The results show that TDHT can provide better security than GDHT and almost the same level of availability as GDHT. To compare their performance, we design a two-level access (TLA) protocol for the TDHT approach and compare it with the distributed version server (DVS) protocol proposed in [Ye10] for the GDHT approach. The experimental results show that TLA can provide much better user perceived update response latency and the same level or even better read access latency compared to DVS.

Ensuring secure information flow is a critical task for service composition in multi-domain systems. Research in security-aware service composition provides some preliminary solutions to this problem, but there are still issues to be addressed. In this paper, we develop a service composition mechanism specifically focusing on the secure information flow control issues. We first introduce a general model for information flow control in service chains, considering the transformation factors of services and security classes of data resources in a service chain. Then, we develop general rules to guide service composition satisfying secure information flow requirements. Finally, to achieve efficient service composition, we develop a three-phase protocol to allow rapid filtering of candidate compositions that are unlikely to satisfy the information flow constraints and thorough evaluation of highly promising candidates. Our approach can achieve effective and efficient service composition considering secure information flow.

Distributed governance is the process for individual entities in the system to make autonomous decisions in response to special situations. It is an important principle in governing the actions in cyber physical systems to achieve operation responsiveness. In this paper, we extend the widely adopted service-oriented architecture (SOA) paradigm to build a distributed governance model in the context of cyber-physical systems. To achieve distributed governance, we develop the novel distributed workflow model and the autonomous service composition process. Our distributed workflow infrastructure facilitates easy modification and evolution of the workflows and effectively incorporates the distributed service and workflow management mechanism. Our autonomous service composition scheme allows intelligent entities in the cyber physical system to participate in the service composition process and make local composition decisions which collectively, best satisfy the global Quality of Service (QoS) objectives. The distributed workflow and autonomous composition concepts can greatly enhance the timeliness, effectiveness, scalability, and agility of large-scale Cyber Physical Systems (CPS).

There have been works considering protocols for accessing partitioned data. Most of these works assume the local cluster based environment and their designs target atomic semantics. However, when considering widely distributed cloud storage systems, these existing protocols may not scale well. In this paper, we analyze the requirements of access protocols for storage systems based on data partitioning schemes in widely distributed cloud environments. We consider the regular semantics instead of atomic semantics to improve access efficiency. Then, we develop an access protocol following the requirements to achieve correct and efficient data accesses. Various protocols are compared experimentally and the results show that our protocol yields much better performance than the existing ones.

Secret sharing and erasure coding-based approaches have been used in distributed storage systems to ensure the confidentiality, integrity, and availability of critical information. To achieve performance goals in data accesses, these data fragmentation approaches can be combined with dynamic replication. In this paper, we consider data partitioning (both secret sharing and erasure coding) and dynamic replication in data grids, in which security and data access performance are critical issues. More specifically, we investigate the problem of optimal allocation of sensitive data objects that are partitioned by using secret sharing scheme or erasure coding scheme and/or replicated. The grid topology we consider consists of two layers. In the upper layer, multiple clusters form a network topology that can be represented by a general graph. The topology within each cluster is represented by a tree graph. We decompose the share replica allocation problem into two subproblems: the Optimal Intercluster Resident Set Problem (OIRSP) that determines which clusters need share replicas and the Optimal Intracluster Share Allocation Problem (OISAP) that determines the number of share replicas needed in a cluster and their placements. We develop two heuristic algorithms for the two subproblems. Experimental studies show that the heuristic algorithms achieve good performance in reducing communication cost and are close to optimal solutions.

Cloud computing is an emerging computation paradigm. To support successful cloud computing, service oriented architecture (SOA) should play a major role. Due to the nature of widely distributed service providers in clouds, the service performance could be impacted when the network traffic is congested. This can be a major barrier for tasks with real-time requirements. In clouds, this problem can be solved by migrating services to different platforms such that the communication cost can be minimized. In this paper, we consider the problem of service selection and migration in clouds. We develop a framework to facilitate service migration and design a cost model and the decision algorithm to determine the tradeoffs on service selection and migration.

Cyber-Physical Systems (CPSs) are combinations of physical devices controlled by software systems to accomplish specified tasks under stringent real-time and physical resource constraints. The major benefit of these systems lies in their potentially positive impacts on real world systems by enabling high dependability assurance. However, a key challenge is to determine not only correct but also cost-effective dynamic operation of all physical devices in the system in the context of real world constraints.In this paper, we present a novel context-sensitive resource-explicit service model and develop the corresponding composition formalisms to help automate the composition process under real-time constraints as well as under various physical resource constraints. The approach is illustrated using an emergency response system.

In this paper, a distributed path planner is presented based on a hierarchical control structure for a virtual vehicle system. The high-level planner cooperates closely with lower level planners to determine the shortest path for the virtual vehicle. The computation task is distributed among all the mobile robots to achieve better load balancing and efficient use of available computational resources. Moreover, a dynamic environment is considered in the path planner. With prior knowledge about the environment, the planner efficiently adjusts the original planned path and generates a new collision-free path when the sensor readings in the mobile robots report that a new obstacle has been detected. A virtual structure for a rigid-body transportation system that employs a large number of robots to lift a rigid body and transport it to a user specified location is presented along with the distributed path planner.

Existing Web service access control models focus on individual Web services, and do not consider service composition. In composite services, a major issue is information flow control. Critical information may flow from one service to another in a service chain through requests and responses and there is no mechanism for verifying that the flow complies with the access control policies. In this paper, we propose an innovative access control model to empower the services in a service chain to control the flow of their sensitive information. Our model supports information flow control through a back-check procedure and pass-on certificates. We also introduce additional factors such as the carry-along policy, security class, and transformation factor, to improve the protocol efficiency. A formal analysis is also presented to show the power and complexity of our protocol.

Edge server replication is an effective solution to achieve high performance in dynamic web applications, such as Web services. Many Web services involve frequent accesses to large-scale backend databases. Current database replication techniques are not directly applicable to edge server architectures. There is no algorithm to dynamically and automatically select the tables for replication. Also, most of the solutions do not consider the potentially limited disk sizes at the edge servers and the needs for them to serve many application sites. In this paper, we present a novel weighted table graph based database replication approach for edge servers to address these problems. Every step in our approach is based on quantitative computation, so it can generate an accurate result. Experimental studies show that our database replication approach significantly improves the performance of Web systems in terms of client response latency, Web application server off loading, and network bandwidth saving.

Cyber-physical systems (CPS) are complex net-centric hardware/software systems that can be applied to transportation, healthcare, defense, and other real-time applications. To meet the high reliability and safety requirements for these systems, proactive system health monitoring and management (HMM) techniques can be used. However, to be effective, it is necessary to ensure that the operation of the underlying HMM system does not adversely impact the normal operation of the system being monitored. In particular, it must be ensured that the operation of the HMM system will not lead to resource contentions that may prevent the system being monitored from timely completion of critical tasks. This paper presents an adaptive HMM system model that defines the fault diagnosis quality metrics and supports diagnosis requirement specifications. Based on the model, the sensor activation decision problem (SADP) is defined along with a steepest descent based heuristic algorithm to make the HMM configuration decisions that best satisfy the diagnosis quality requirements. Evaluation results show that the technique reduces the overall system resource consumption without adversely impacting the diagnosis capability of the HMM.

Service oriented architecture (SOA) has become a popular paradigm for software development in many application domains, including real-time applications. Timing analysis is a critical issue which can guide service composition to best satisfy the real time requirements of the composed system. However, existing timing analysis works do not sufficiently address some important issues. For example, admission control is an important technique for real time assurance, but most of the timing analysis techniques do not take admission control into account and, hence, may result in unrealizable decisions. Also, communication time is an important factor in real-time assurance, but most of the works do not provide clear approaches in dealing with communication time analysis. In this paper, we propose a timing specification model and analysis techniques for real-time service-oriented systems. In the specification model, a thorough consideration of all information required for timing analysis is discussed. For timing analysis, we consider the service time softly guaranteed by the admission control policy as well as estimated communication cost to reach more accurate timing estimates. Also, to avoid the analysis overhead in large-scale SOA systems, we propose a three-phase approach. In this approach, we first use a highly efficient but moderately accurate algorithm to eliminate most of the candidate compositions. More accurate timing prediction is performed on a small number of selected compositions in the second phase. In the third phase, specific concrete services are selected and admissions are performed to finalize the composition and service grounding. The approach is scalable and can effectively achieve service composition for real time requirement satisfaction.

We present a fast iterative planner (FIP) that aims to handle planning problems involving nondeterministic actions. In contrast to existing iterative planners, FIP is built upon Graphplan's intrinsic features, thus, enabling Graphplan variants, including SGP and FF, to be enhanced with the capability of iterative planning. In addition, FIP is able to produce program-like plans with conditional and loop constructs, and achieves efficient planning via novel algorithms for manipulating planning graphs. Experimental results on several nondeterministic planning problems show that FIP is more efficient than the well-known planner, MBP, especially as the size of the problems increases.

Edge server replication is an effective solution to achieve high performance in dynamic Web applications, such as Web services. It can replicate the application logic and the data close to the clients to reduce the response latency and network traffic and to offload the servers. Many Web services involve frequent accesses to large-scale backend databases. Current database replication techniques are not directly applicable to edge server architectures. Most of the solutions do not consider the potentially limited disk sizes at the edge servers and the needs for them to serve many application sites. In this paper, we present a novel database replication approach, PSO-MP, for edge servers to address the problems. Experimental studies show that the PSO-MP approach significantly improves the performance of Web systems in terms of client response latency, Web application server offloading, and network bandwidth saving.

In recent years, the issues in web service security have been widely investigated and various security standards have been proposed. But most of these studies and standards focus on the access control policies for individual web services and do not consider the access issues in composed services. Consider a simple service chain where service s1accesses s2, and s2, in turn, accesses service s3. The information returned from s3to s2may be used to compute some results that are further returned to s1. The current web service security framework does not provide any mechanisms to control such an information flow, and hence, sensitive information may be leaked to s1without the consensus of s3. In this paper, we propose an enhanced security model to facilitate the control of information flow through service chains. It extends the basic security models by introducing the concepts of delegation and pass-on. Based on these concepts, new certificates, certificate chain, delegation and pass-on policies, and how they are used to control the information flow are discussed.

Availability analysis is an important issue in robotic swarm systems. It can help the designer to construct a cost-effective system with high availability and fewer resources. For the model and analysis to be fully specified and practical, this paper systematically investigates the major issues that need to be addressed in the analysis of various robotic swarm applications. Four models are established to consider systems with dependent and independent robots, homogenous and non-homogenous systems, and the effect of various types of motions on the overall system failure pattern. Detailed analysis of each of these models is performed based on renewal theory and continuous Markov Chain techniques. Numerical availability evaluations for two applications are also presented.

Software development process has become increasingly complex and expensive due to the growing size and criticality of modern software systems. Deficiencies during the development process lead to significant quality problems that can hamper both the initial development as well as subsequent maintenance activities. Hence, it is imperative to develop advanced techniques to increase the overall software dependability and reduce its development cost and time. Automated code synthesis is a promising method of achieving the above goals. It is a constructive process that can be used to generate programs from specifications. It can accelerate the development process and simplify verification tasks. However, current automated code synthesis techniques have only limited abilities and are mostly able to generate sequential codes. Automated AI planning is attractive for software engineering automation because of its emphasis on goals and the similarity of plans to programs. In this paper, we present a novel iterative planning approach to generate parameterized procedure-like generic reusable plans, i.e., procedural plans. Specifically, we enhance the Graphplan algorithm to a two-phased algorithm that is able to generate loop and conditional constructs. The proposed iterative planning approach is targeted for automated code synthesis and leads to sophisticated code synthesis in combination with component-based software development (CBSD). We have implemented a prototype for our iterative planning approach and used it to solve several well-known planning problems. The results show that the implemented planner is able to reason about complex relationships among planning operators and automatically generate procedural plans. It preserves the good performance of Graphplan and can scale well when the search space grows larger.

Content adaptation is an important technique for mobile devices. Existing content adaptation systems have been developed with specific adaptation goals. In this paper, we present an extensible content adaptation system, Xadaptor. We take a rule-based approach to facilitate extensible, systematic, and adaptive content adaptation. It integrates adaptation mechanisms for various content types and organizes them into the rule base. Rules are invoked based on the individual client information. We classify HTML page objects into structure, content, and pointer objects. Existing content adaptation techniques mainly focus on content objects and do not consider adaptation for structure and pointer objects. In Xadaptor, novel adaptation techniques for the structure object HTML table have been developed. We use fuzzy logic to model the adaptation quality and guide the adaptation decision. To demonstrate the feasibility of our approach, we have implemented a prototype system. Experimental studies show that Xadaptor is capable of on-the-fly content adaptation and is easily extensible

Realizing the quality of service (QoS) requirements for a software system continues to be an important and challenging issue in software engineering. A software system may need to be updated, or reconfigured, to provide modified QoS capabilities. These changes can occur at development time or at run-time. In component based software engineering, software systems are built by composing components. When the QoS requirements change, there is a need to reconfigure the components. Unfortunately, many components are not designed to be reconfigurable, especially in terms of QoS capabilities. It is often labor-intensive and error prone work to reconfigure the components, as developers need to manually check and modify the source code. Furthermore, the work requires experienced, senior developers, which makes it costly. The limitations motivate the development of a new rule-based, semi-automated component parameterization technique that performs code analysis to identify and adapt parameters and changes components into reconfigurable ones. Compared with a number of alternative QoS adaptation approaches, the proposed rule-based technique has advantages in terms of flexibility, extensibility and efficiency. The adapted components support the reconfiguration of potential QoS trade-offs among time, space, quality, etc. The proposed rule-based technique has been successfully applied to two substantial libraries of components. The F-measure or balanced F-score results for the validation are excellent, that is, 94 percent.

Failures of mission-critical software systems can have catastrophic consequences and, hence, there is strong need for scientifically rigorous methods for assuring high system reliability. To reduce the V&V cost for achieving high confidence levels, quantitatively based software defect prediction techniques can be used to effectively estimate defects from prior data. Better prediction models facilitate better project planning and risk/cost estimation. Memory based reasoning (MBR) is one such classifier that quantitatively solves new cases by reusing knowledge gained from past experiences. However, it can have different configurations by varying its input parameters, giving potentially different predictions. To overcome this problem, we develop a framework that derives the optimal configuration of an MBR classifier for software defect data, by logical variation of its configuration parameters. We observe that this adaptive MBR technique provides a flexible and effective environment for accurate prediction of mission-critical software defect data

The past decade has seen great progress in the development of embedded real-time systems, which are playing increasingly important roles in various application domains. However, the growing complexity of these systems has revealed the urgent need to develop advanced techniques to reduce the time-to-market as well as the overall system development cost. One method for achieving both of these goals is automated code synthesis combined with component based software development (CBSD). This enables the synthesizer to focus on generating the glue code needed to assemble an application from existing components. The main challenge is how to enable the synthesizer to recognize and generate complex conditional or loop statements. In this paper, a pattern-based code synthesis approach is enhanced to enable it to synthesize new loop statements. Specifically, we use an extended version of Graphplan to help the synthesizer to recognize and generate new loop statements. The paper proposes a planning domain model for code patterns and an automated code synthesis system, which integrates the enhanced AI planner with the code pattern integration system (CPIS) to fully automate the code synthesis process

Embedded systems are becoming highly complex and increasingly being used in critical applications. Integrated system health management (ISHM) techniques have therefore been developed to ensure the proper operation of these systems. However, some ISHM systems are relatively complex and may consume a significant amount of resources. In some situations, activating the full ISHM system may cause resource contention and prevents the target system from timely completing critical tasks. Thus, it is imperative to introduce the notion of adaptivity into ISHM systems. This paper systematically discusses the issues that need to be addressed in an adaptive ISHM system with a focus on adaptation in terms of QoS aspects. A novel model, adaptive diagnosis quality-oriented system model (ADQSM), is proposed to model the QoS specification and fault diagnosis quality measurement issues as well as the abstraction of the adaptation problem. We then present the method to evaluate various diagnosability attributes based on a modified fault signature matrix. We further map the ADQSM model to the particle swarm optimization (PSO) problem model and use PSO for rapid configuration decision making

Automated code synthesis is a constructive process that can be used to generate programs from specifications. It can, thus, greatly reduce the software development cost and time. The use of formal code synthesis approach for software generation further increases the dependability of the system. Though code synthesis has many potential benefits, the synthesis techniques are still limited. Meanwhile, components are widely used in embedded system development. Applying code synthesis to component based software development (CBSD) process can greatly enhance the capability of code synthesis while reducing the component composition efforts. In this paper, we discuss the issues and techniques for applying deductive code synthesis techniques to CBSD. For deductive synthesis in CBSD, a rule base is the key for inferring appropriate component composition. We use the code patterns to guide the development of rules. Code patterns have been proposed to capture the typical usages of the components. Several general composition operations have been identified to facilitate systematic composition. We present the technique for rule development and automated generation of new patterns from existing code patterns. A case study of using this method in building a real-time control system is also presented

This paper proposes a rule-based expert system model to assist developers in enhancing the quality of embedded software. The expert system supports semi-automated source code enhancements from multiple perspectives including optimization, reconfiguration to achieve quality of service (QoS) trade-offs, conformance to coding standards, etc., by defining a rule base that is composed of modularized and extensible rule sets. The rule sets are composed of re-usable rules; the rules capture the in-depth knowledge of different software experts. The expert system also adopts a technique to support automated fact generation. This allows the expert system to support processing programs developed in different programming languages

The rapid growth in the demand for embedded systems and the increased complexity of embedded software pose an urgent need for advanced embedded software development techniques. Software technology is shifting toward semi-automated code generation and integration of systems from components. Component-based development (CBD) techniques can significantly reduce the time and cost for developing software systems. Furthermore, effective component retrieval is a fundamental issue in CBD. In this paper, we address the issues in designing software repositories for embedded software components. We develop an On-line Repository for Embedded Software (ORES) to facilitate component management and retrieval. ORES uses an ontology-based approach to facilitate repository browsing and effective search. To allow easy browsing of ORES, we analyze the typical ontology relations for software components and develop a Merging and Echoing technique to convert the ontology into a hierarchy suitable for browsing, but without the loss of any critical semantic information contained in the ontology. We also develop an algorithm for grouping search results based on the ontology. Thus, we can display search result groups to avoid having to display a large number of search results or having to prune the results and risk reducing the recall factor. Another important aspect in embedded software is the set of nonfunctional requirements and properties. In ORES, we develop an XML-based specification method to capture nonfunctional properties as well as functional characteristics of components and enable retrieval of relevant components based on these specifications.

In distributed mobile systems, communication cost and disconnections are major concerns. In this paper, we address replica placement issues to achieve improved performance for systems supporting mobile transactions. We focus on handling correlated data objects and disconnections. Frequently, requests and/or transactions issued by mobile clients may access multiple data objects and should be considered together in terms of replica allocation. We discuss the replication cost model for correlated data objects and show that the problem of finding an optimal solution is NP. We further adjust the replication cost model for disconnections. A heuristic "expansion-shrinking" algorithm is developed to efficiently make replica placement decisions. The algorithm obtains near optimal solutions for the correlated data model and yields significant performance gains when disconnection is considered. Experimental studies show that the heuristic expansion-shrinking algorithm significantly outperforms the general frequency-based replication schemes.

Process-control systems usually deal with changeable environments so that high adaptability of these systems is required. After a process-control system has been implemented and deployed, it is not an easy task to adapt the system to satisfy new requirements. Considering this problem, we propose the use of relational program architectures to design process-control systems for high adaptability. With the relational program architecture, a process-control system is designed to be the composition of several Independently Developable End-user Assessable Logical (IDEAL) components through pre-defined composition patterns. Each IDEAL component is associated with several end-user visible properties and can be solved and validated in its restricted "view" of the system, i.e., it can be designed and implemented independently, and can be tested or verified by the end-user independently. In addition, the system level properties (safety, stability, and reliability) can be inferred from the individual IDEAL components mathematically. The relational program architecture can provide not only the ultra-high dependability assurance of a process-control system, but can also make the system highly adaptable. We propose several principles, by which we can accurately determine which components of the system need to be adapted and how to adapt them after the system's requirement has changed. These principles can be evolved to automated tool support.

Many critical application systems require reconfigurability in order to adapt under changing environment. To achieve system reconfigurability, it is possible to use adaptation mechanisms that are external to components or to use parameterized components. This paper focuses on making components reconfigurable in terms of QoS tradeoffs. We propose a new component parameterization technique which can transform individual components to reconfigurable ones such that they can support various QoS tradeoffs to achieve overall system QoS requirements. The parameterized components can be used to develop both statically and dynamically reconfigurable systems. The proposed technique is rule based, which provides flexibility and extensibility to enhance and improve the technique. A tool set has been developed based on the proposed technique to achieve semi-automated component parameterization.

Component-based development (CBD) techniques have been widely used to enhance the productivity and reduce the cost for software systems development. However, applying CBD techniques to embedded software development faces additional challenges. For embedded systems, it is crucial to consider the quality of service (QoS) attributes, such as timeliness, memory limitations, output precision, battery constraints. Frequently, multiple components implementing the same functionality with different QoS properties can be used to compose a system. Also, software components may have parameters that can be configured to satisfy different QoS requirements. Composition analysis, which is used to determine the most suitable component selections and parameter settings to best satisfy the system QoS requirement, is very important in embedded software development process. In this paper, we present a model and the methodologies to facilitate composition analysis. We define QoS requirements as constraints and objectives. Composition analysis is performed based on the QoS properties and requirements to find solutions (component selections and parameter settings) that can optimize the QoS objectives while satisfying the QoS constraints. We use a multiobjective concept to model the composition analysis problem and use an evolutionary algorithm to determine the Pareto-optimal solutions efficiently.

Conventional admission control models incur some performance penalty. First, admission control computation can overload a server that is already heavily loaded. Also, in large-scale media systems with geographically distributed server clusters, performing admission control on each cluster can result in long response latency, if the client request is denied at one site and has to be forwarded to another site. Furthermore, in prefix caching, initial frames cached at the proxy are delivered to the client before the admission decisions are made. If the media server is heavily loaded and, finally, has to deny the client request, forwarding a large number of initial frames is a waste of critical network resources. In this paper, a novel distributed admission control model is presented. We make use of proxy servers to perform the admission control tasks. Each proxy hosts an agent to coordinate the effort. Agents reserve media server's disk bandwidth and make admission decisions autonomously based on the allocated disk bandwidth. We develop an effective game theoretic framework to achieve fairness in the bandwidth allocation among the agents. To improve the overall bandwidth utilization, we also consider an aggressive admission control policy where each agent may admit more requests than its allocated bandwidth allows. The distributed admission control approach provides the solution to the stated problems incurred in conventional admission control models. Experimental studies show that our algorithms significantly reduce the response latency and the media server load.

This paper presents a method for decomposing process-control systems. This decomposition method is automated, meaning that a series of principles that can be evolved to support automated tools are given to help a designer decompose complex systems into a collection of simpler components. Each component resulting from the decomposition process can be designed and implemented independently of the other components. Also, these components can be tested or verified by the end-user independently of each other. Moreover, the system properties, such as safety, stability, and reliability, can be mathematically inferred from the properties of the individual components. These components are referred to as IDEAL (independently developable end-user assessable logical) components. This decomposition method is applied to a case study specified by the High-Integrity Systems group at Sandia National Labs, which involves the control of a future version of the Bay Area Rapid Transit (BART) system.

In this paper, we propose a comprehensive request processing approach at the proxy server to preprocess media requests with the goal of quality of service (QoS) enhancement. This approach integrates distributed admission control, batching and prefix caching schemes. A proxy assistant is designed to realize the proxy site request processing approach. Also, to fully utilize prefix caching, we allow a request to stay at the proxy to wait for the disk bandwidth of the media server to become available before the cached contents are exhausted. Performance studies show that our request processing approach significantly improves the admission rates, and response time

The training time for SVMs to compute the maximal marginal hyper-plane is at least O(N/sup 2/) with the data set size N, which makes it nonfavorable for large data sets. This work presents a study for enhancing the training time of SVMs, specifically when dealing with large data sets, using hierarchical clustering analysis. We use the dynamically growing self-organizing tree (DGSOT) algorithm for clustering because it has proved to overcome the drawbacks of traditional hierarchical clustering algorithms. Clustering analysis helps find the boundary points, which are the most qualified data points to train SVMs, between two classes. We present a new approach of combination of SVMs and DGSOT, which starts with an initial training set and expands it gradually using the clustering structure produced by the DGSOT algorithm. We compare our approach with the Rocchio Bundling technique in terms of accuracy loss and training time gain using two benchmark real data sets.

With the rapid growth in the development of modern and sophisticated software applications, such as multimodal distributed systems, the complexity of software development processes has increased enormously, posing an urgent need for automation of some of these processes. One of the key software development process is system testing. In This work, we evaluate the potential application of AI planning techniques in automating the testing process. We propose a framework for an automated planning system (APS) for applying AI planning techniques for automated testing of a software module. Using a comprehensive example, we demonstrate how the MEA-Graphplan (means-ends analysis graphplan) algorithm can be used to automatically generate test data (sequence of steps or actions) to transform the system from the current state to some desired goal state. MEA-Graph planning might prove to be computationally more efficient and effective than basic graph planning technique because here the planning graph is expanded in a goal-oriented manner using regression-matching graph constructed by regressing goals over actions that can overcome the problem of state-space explosion during graph expansion phase of the planning.

Summary form only given. Due to the extensive use of computers and networks in critical systems, survivability is no longer a luxury but an essential requirement. We consider survivability assurance for critical applications where the system may incur accidental failures as well as intentional attacks. A successful attack can penetrate and compromise a pan of the system and, consequently, make the system behave like incurring a malicious failure. We model successful attacks as Byzantine failures and use the replication scheme to uniformly cope with failures and attacks. Instead of using conventional replication protocols that generally have a high overhead, we develop a novel coordination protocol, namely, adaptive NMR (ANMR) algorithm, to provide efficient coordination among replicated sites. Also, a special data partitioning technique is used with ANMR to assure confidentiality of the system even if it is partially compromised. Due to the adaptive nature, our ANMR algorithm reduces the communication overhead incurred in conventional NMR schemes. When there is no failure, the system operates at a very good performance. When failures occur, the system adapts to the NMR scheme gracefully.

Summary form only given. We investigate a transaction based partial replication strategy for replicating database in the mobile environments. We propose a heuristic algorithm to select a set of data objects for replicating to and deallocating from the mobile node, based on the dynamically changing client access patterns. We conduct experiments to compare the performance of our algorithm with that of the full replication and frequency based partial replication algorithms. The results show that the transaction based partial replication algorithm always has a better performance than the full replication strategy. And, in most cases, it is better than frequency-based partial replication algorithms.

Summary form only given. Application level multicast approaches have attracted interests in both research and industrial communities. Among various approaches, constructing the overlay multicast tree based on mesh network is very promising for a large multicast group size. This approach is efficient in bandwidth utilization but suffer from high computation overhead. We present a new approach for constructing an overlay multicast tree in a large scale media streaming system using neural networks. The media server first constructs an overlay multicast tree for requests arriving in a relatively short time interval. Then the subsequent requests can join the multicast tree in a distributed way. To utilize the interface bandwidth efficiently, we formulate the original tree construction problem as a balanced multicast tree problem and propose a new SOFM-like neural network algorithm to obtain the solution. For the requests arriving at a later time, the proxy servers process the requests and join the multicast tree using a decentralized prediction based on a multilayered neural network. The tree is kept balanced in the tree joining process by having proxy servers predict the traffic load on its neighbors.

MOTIVATION: The increasing use of microarray technologies is generating large amounts of data that must be processed in order to extract useful and rational fundamental patterns of gene expression. Hierarchical clustering technology is one method used to analyze gene expression data, but traditional hierarchical clustering algorithms suffer from several drawbacks (e.g. fixed topology structure; mis-clustered data which cannot be reevaluated). In this paper, we introduce a new hierarchical clustering algorithm that overcomes some of these drawbacks. RESULT: We propose a new tree-structure self-organizing neural network, called dynamically growing self-organizing tree (DGSOT) algorithm for hierarchical clustering. The DGSOT constructs a hierarchy from top to bottom by division. At each hierarchical level, the DGSOT optimizes the number of clusters, from which the proper hierarchical structure of the underlying dataset can be found. In addition, we propose a new cluster validation criterion based on the geometric property of the Voronoi partition of the dataset in order to find the proper number of clusters at each hierarchical level. This criterion uses the Minimum Spanning Tree (MST) concept of graph theory and is computationally inexpensive for large datasets. A K-level up distribution (KLD) mechanism, which increases the scope of data distribution in the hierarchy construction, was used to improve the clustering accuracy. The KLD mechanism allows the data misclustered in the early stages to be reevaluated at a later stage and increases the accuracy of the final clustering result. The clustering result of the DGSOT is easily displayed as a dendrogram for visualization. Based on a yeast cell cycle microarray expression dataset, we found that our algorithm extracts gene expression patterns at different levels. Furthermore, the biological functionality enrichment in the clusters is considerably high and the hierarchical structure of the clusters is more reasonable. AVAILABILITY: DGSOT is available upon request from the authors.

Basically, the development of a software system contains specification, design, and implementation. Various specification mechanisms and design methods have been proposed to facilitate the implementation of software systems. However, high system quality cannot be easily assured because of some limitations of these current design methods as well as semantic gaps between the specification mechanisms and the design methods. In particular, manual effort is needed to transform the specification of a system into a design framework for the system. Considering these problems, in this paper, we propose a new system design method. This design method is systematic because by using it, the design framework of a system can be automatically created from the specification of the system. Also, the resulting design framework can support high quality assurance for the system. This design framework is a composition of several individual components, each of which can be completely independently developed and hardened. Further, the system properties (reliability, safety, liveness, etc.) can be mathematically inferred from the properties of the individual components. These components are referred to as IDEAL (Independently Developable End-user Assessable Logical) components and the design method is mainly targeted for continuous process-control systems. The paper develops the approach and illustrates it for a vehicle control system.

Dramatic advances in computer and communication technologies have made it economically feasible to extend the use of embedded computer systems to more and more critical applications. At the same time, these embedded computer systems are becoming more complex and distributed. As the bulk of the complex application-specific logic of these systems is realized by software, the need for certifying software systems has grown substantially. While relatively mature techniques exist for certifying hardware systems, methods of rigorously certifying software systems are still being actively researched. Possible certification methods for embedded software systems range from formal verification to statistical testing. These methods have different strengths and weaknesses and can be used to complement each other. One potentially useful approach is to decompose the specification into distinct aspects that can be independently certified using the method that is most effective for it. Even though substantial-research has been carried out to reduce the complexity of the software system through decomposition, one major hurdle is the need to certify the overall system on the basis of the aspect properties. One way to address this issue is to focus on architectures in which the aspects are relatively independent of each other. However, complex embedded systems are typically comprised of multiple architectures. We present an alternative approach based on the use of application-oriented-frameworks for implementing embedded systems. We show that it is possible to design such frameworks for embedded applications and derive expressions for determining the system reliability from the reliabilities of the framework and the aspects. The method is illustrated using a distributed multimedia collaboration system.

Many agent-based systems have been developed over the past decade; however, the security issues are usually not addressed adequately. In order to make the mobile agent paradigm more useful and acceptable for Web and Internet applications, the security considerations should go beyond the protection of basic agent execution environments. In this paper, we present the design of a robust Java-based mobile agent system, PeAgent. The PeAgent system not only incorporates a fine-grain agent privilege control mechanism, but also includes a multi-level protection mechanism that can be used throughout the life-cycle of agents. A two-level domain hierarchy is constructed to organize the large number of Internet nodes in the agent system into manageable units: the global/domain management unit (GMU/DMU). Each unit consists of a certification authority (CA) and a location manager (LM). The certificates issued from GMU and DMU define the access privileges on the PeAgent servers for each agent. A context hierarchy is built up on the PeAgent servers for fine-level resource access control and agent management. Overall, the PeAgent system provides a secure computing environment for widely distributed applications over a network of heterogeneous platforms. It also facilitates the development of secure Web-based applications.

We present a novel distributed admission control model for multimedia delivery. Proxy servers form a large-scale distributed infrastructure and can be used to perform the admission control tasks. In our distributed admission control algorithm, an agent first characterizes its disk bandwidth requirement based on the distribution of requests arrived at the proxies. Then, it reserves the disk bandwidth from the server by maximizing its utility function. The server grants the bandwidth to the agents according to its capacity. Based on the granted bandwidth, each agent executes the admission control algorithm for its local requests. The distributed admission control model provides the admission control service close to the users and, hence, reduces the network load, media server load, and, in some cases, users' response latency.

Prefix caching has significant benefits in media delivery systems in terms of reduced startup latency and network traffic. However, with the conventional admission control model, prefix caching may incur some performance penalty. When the media server is heavily loaded and has to deny the client request finally, forwarding a large number of initial frames from proxy to clients can result in dramatic waste of critical network resource. An ideal solution to this problem is to let proxy servers perform the admission control on behalf of the media servers. In this paper, we present a distributed admission control policy. We consider an aggressive disk bandwidth allocation scheme where an agent may, with a certain probability, admit a new request when the current bandwidth used at the agent has reached its limit. We formulate the problem as a min-max optimization problem and provide a MINMAX algorithm to find the solutions. The effectiveness of our algorithm is demonstrated through simulation studies.

Computer systems are vulnerable to many different types of threats ranging from harmless mistakes in data entries to malicious attacks by computer hackers. Furthermore, the explosive growth of the Internet has introduced very sophisticated ways of compromising any computer system. Consequently, a great deal of time and effort has been spent on achieving computer network security. Most of the efforts to deal with computer security have emphasized the network security aspect (i.e., the focus so far has been on intruders from outside the system). However, there also exists a significant threat from "enemies within", e.g. attacks due to malicious code embedded in the software. Whether it is intentional or not, there are many software bugs that can potentially be the source of the information misusages. One approach for dealing with this issue is to certify component security and deduce system security from its components. The advantage of this method is that it is much simpler to validate a small component as compared with a large monolithic software system. In this paper, we define a general process that allows the system security to be decomposed into orthogonal aspects so that it is possible to rigorously certify the security of a system. The approach is illustrated for the security service for an e-mail application.

Component-based development (CBD) techniques have been widely used to enhance the productivity and reduce the cost for software systems development. However, applying CBD techniques to embedded software development faces additional challenges. For embedded systems, it is crucial to consider the QoS attributes, such as timeliness, memory requirement, output precision, power consumption, etc. When a system is composed of components, the appropriate components have to be selected such that the composed system is guaranteed to satisfy its QoS requirements. In this paper, we investigate the model for composition analysis. Based on the analysis model, we develop algorithms for selecting components to compose the designated system such that the overall system QoS properties can be pare to optimal. An overview of a repository-based embedded software development methodology was first presented. Then we discuss the composition analysis techniques. A case study is presented to illustrate our approach finally.

The goal of accurate software measurement data analysis is to increase the understanding and improvement of software development process together with increased product quality and reliability. Several techniques have been proposed to enhance the reliability prediction of software systems using the stored measurement data, but no single method has proved to be completely effective. One of the critical parameters for software prediction systems is the size of the measurement data set, with large data sets providing better reliability estimates. In this paper, we propose a software defect classification method that allows defect data from multiple projects and multiple independent vendors to be combined together to obtain large data sets. We also show that once a sufficient amount of information has been collected, the memory-based reasoning technique can be applied to projects that are not in the analysis set to predict their reliabilities and guide their testing process. Finally, the result of applying this approach to the analysis of defect data generated from fault-injection simulation is presented.

Rapid growth in the demand for embedded systems and the increased complexity of embedded software pose an urgent need for advanced embedded software development techniques. One attractive approach is to enable semi-automated code generation and integration of systems from components. However, the implementation and validation of these systems requires a steep learning curve due to the large number, variety, and complexity of software components. In this paper, we discuss the potential application of AI planning techniques in assisting with the synthesis of glue code for assembling a system from existing components as well as automated testing of the system. The approach works by transforming component specifications into rules that operate on a domain-specific state space. Each rule captures the semantics of a method in a class. The code assembly and testing requirements are described by identifying conditions (goals) that should be achieved. An automated planning system computes a sequence of rules and their instantiations that will achieve the goal state. This sequence is then used to synthesize the code or to generate test cases. The approach is illustrated using an example.

Distributed embedded software systems, such as sensor networks and command and control systems, are complex systems with stringent performance, reliability, security, and safety constraints. These are also long-lived systems that must be continually upgraded and evolved to incorporate enhanced functionality. One approach for achieving high quality and evolvability for these systems is to organize them in the form of application-oriented frameworks that allow the system to be composed from orthogonal aspects that can be independently developed, evolved, and certified. In this paper, we define a general framework that allows a distributed embedded system to have relatively independent aspects, including "plug-and-play" capability. We present conditions under which the reliability of the system can be inferred from the reliability of the individual aspects. The approach is illustrated for a framework-based distributed sensor network.

In a wireless mobile client-server environment, a mobile user may voluntarily disconnect itself from the Web server to save its battery life and avoid high communication prices. To allow Web pages to be updated while the mobile user is disconnected from the Web server, updates can be staged in the mobile host and propagated back to the Web server upon reconnection. In this paper, we analyze algorithms for supporting disconnected write operations for wireless Web access and develop a performance model to identify the optimal length of the disconnection period under which the cost of update propagation is minimized. The analysis result is particularly applicable to Web applications which allow wireless mobile users to modify Web contents while on the move. We show how the result can be applied to real-time Web applications such that the mobile user can determine the longest disconnection period such that it can still propagate updates to the server before the deadline so that a minimum communication cost is incurred.

We discuss a multicriteria transaction (MCT) model to address problems encountered in large-scale e-commerce transaction processing systems. A MCT is a generalized transaction where users can specify their preferences in a request by specifying multiple criteria in the transaction. With each criteria specification, a set of alternate execution paths is included. Thus, a MCT is less likely to fail. Moreover, the MCT model allows easy extraction of criteria from a set of transactions and, hence, optimal decisions can be made to achieve better customer satisfaction. We discuss the design of a MCT processing system and compare the MCT model to conventional transaction processing approaches.

Several methods have been explored for assuring the reliability of mission critical systems (MCS), but no single method has proved to be completely effective. This paper presents an approach for quantifying the confidence in the probability that a program is free of specific classes of defects. The method uses memory-based reasoning techniques to admit a variety of data from a variety of projects for the purpose of assessing new systems. Once a sufficient amount of information has been collected, the statistical results can be applied to programs that are not in the analysis set to predict their reliabilities and guide the testing process. The approach is applied to the analysis of Y2K defects based on defect data generated using fault-injection simulation.

The use of off-the-shelf components (COTS) can significantly reduce the time and cost of developing large-scale software systems. However, there are some difficult problems with the component-based approach. First, the developers have to be able to effectively retrieve components. This requires the developers to have an extensive knowledge of available components and how to retrieve them. After identifying the components, the developers also face a steep learning curve to master the use of these components. We are developing an On-line Repository for Embedded Software (ORES) to facilitate component management and retrieval. In this paper, we address the issues of designing software repository systems to assist users in obtaining appropriate components and learning to understand and use the components efficiently. We use an ontology to construct an abstract view of the organization of the components in ORES. The ontology structure facilitates repository browsing and effective search. We also develop a set of tools to assist with component comprehension, including a tutorial manager and a component explorer.

A mobile user may voluntarily disconnect itself from the Web server to save its battery life and avoid high communication prices. To allow Web pages to be updated while the mobile user is disconnected from the Web server, updates can be staged in the mobile unit and propagated back to the Web server upon reconnection. We analyze algorithms for supporting disconnected write operations and develop a performance model which helps identify the optimal length of the disconnection period under which the cost of update propagation is minimized. The analysis result is particularly applicable to Web applications which allow wireless mobile users to modify Web contents while on the move. We also show how the result can be applied to real-time Web applications such that the mobile user can determine the longest disconnection period such that it can still propagate updates to the server before the deadline with a minimum communication cost.

Computers are being used to automate critical services, including manufacturing systems, transportation, etc. For these critical applications, it is necessary to be able not only to achieve high quality but also to rigorously demonstrate that high quality has in fact been achieved. One approach that is used to facilitate prevention as well as detection of software faults is to decompose the requirements specification into more manageable portions. However, this does not necessarily enable the demonstration of high quality. This paper discusses a method of decomposing software into aspects that allows the system reliability to be inferred from the aspect reliabilities. Each aspect is independently developable, i.e., it can be designed and implemented independently of the other aspects in the system. In addition, each aspect is end-user assessable, i.e., it can be tested or verified by the end-user independently of any other aspect. We identify five classes of IDEAL (Independently Developable End-user Assessable Logical) aspects and, for each class, we present the conditions that must be satisfied in order to compute the system reliability from the aspect reliabilities.

Multiprocessor systems are widely used in many application programs to enhance system reliability and performance. However, reliability does not come naturally with multiple processors. We develop a multi-invariant data structure approach to ensure efficient and robust access to shared data structures in multiprocessor systems. Essentially, the data structure is designed to satisfy two invariants, a strong invariant, and a weak invariant. The system operates at its peak performance when the strong invariant is true. The system will operate correctly even when only the weak invariant is true, though perhaps at a lower performance level. The design ensures that the weak invariant will always be true in spite of fail-stop processor failures during the execution. By allowing the system to converge to a state satisfying only the weak invariant, the overhead for incorporating fault tolerance can be reduced. We present the basic idea of multi-invariant data structures. We also develop design rules that systematically convert fault-intolerant data abstractions into corresponding fault-tolerant versions. In this transformation, we augment the data structure and access algorithms to ensure that the system always converges to the weak invariant, even in the presence of fail-stop processor failures. We also design methods for the detection of integrity violations and for restoring the strong invariant. Two data structures, namely binary search tree and double-linked list, are used to illustrate the concept of multi-invariant data structures.

Most software reliability methods have been developed to predict the reliability of a program using only data gathered during the resting and validation of a specific program. Hence, the confidence that can be attained in the reliability estimate is limited since practical resource constraints can result in a statistically small sample set. One exception is the Orthogonal Defect Classification (ODC) method, which uses data gathered from several projects to track the reliability of a new program, Combining ODC with root-cause analysis can be useful in many applications where it is important to know the reliability of a program for a specific type of a fault. By focusing on specific classes of defects, it becomes possible to (a) construct a detailed model of the defect and (b) use data from a large number of programs. In this paper, we develop one such approach and demonstrate its application to modeling Y2K defects.

While there have been significant advances in fault tolerance research, the effort has focused on the design of individual fault-tolerant systems or methodologies. Recently, some research has been initiated to develop techniques that can provide a spectrum of fault tolerance capabilities. In this paper, we present the design of a fault tolerance framework that can support a wide range of applications with various fault tolerance requirements, various criticality levels, and various system models. The framework is designed to be parameterizable so that the user can configure it to obtain the desired features. Also, the framework is designed to be an off-the-shelf component such that application programs can be integrated within it easily to obtain the fault-tolerant version of the application system. A specialized N-modular redundancy (SNMR) scheme has been developed to serve as the primary approach for achieving efficient and cost-effective fault tolerance for the framework. In most cases, the SNMR scheme yields better performance and lower cost in providing fault tolerance as compared with conventional NMR schemes. It also enhances the scalability and customizability of the general replication method. This paper discusses the main issues in the design and implementation of the SNMR framework, including the major concept of the SNMR framework, various SNMR algorithms that tolerate various types of faults, an object-oriented overall system design and the interface protocol class hierarchy. The interface protocol class hierarchy provides a nice paradigm for the implementation of customizable, highly reusable, and easily extensible SNMR framework.

While there has been significant advances in fault tolerance research, the effort has focused on the design of individual fault-tolerant systems or methodologies. Recently, some research has been initiated to develop fault tolerance paradigms that can be used to provide a spectrum of fault tolerance levels. In this paper, we present the design of a fault tolerance framework that can be used to support a wide spectrum of applications with various fault tolerance requirements, various criticality levels, and various system models. The framework is designed to be parameterizable so that the user can configure it to obtain the desired features. Also, the framework is designed to be an off-the-shelf component such that application programs can be integrated within it easily to obtain the fault-tolerant version of the application system. A specialized N-modular redundancy (SNMR) scheme has been developed to serve as the primary approach for achieving efficient and cost-effective fault tolerance for the framework. In most cases, the SNMR scheme yields better performance and lower cost in providing fault tolerance as compared with conventional NMR schemes. It also enhances the scalability and customizability of the general replication method. This paper discusses the major concept of the SNMR framework and the main issues in the design and implementation of the framework, including an object-oriented overall system design and the interface protocol class hierarchy. The interface protocol class hierarchy provides a nice paradigm for the implementation of customizable, highly reusable, and easily extensible SNMR framework.

The authors discuss the implementation and performance assessment of a multilevel data structure system prototype. They compare the multilevel data structure approach with corresponding fault-intolerant implementations to assess the overhead imposed for incorporating fault tolerance. The simulation shows promising results in using multilevel data structures.

Computers are being used to achieve increasingly sophisticated control for large and complex systems. Many of these systems require a large shared state-space or database. Thus, handling real-time concurrent accesses to a shared database is an essential feature for modern fault-tolerant systems. Many fault-tolerant systems have been implemented for uniformly tolerating various types of failures, such as MAFT (Multicomputer Architecture for Fault Tolerance), FTP (Fault-Tolerant Processor), FTPP (Fault-Tolerant Parallel Processors) and Delta-4. However, most of these either lack the notion of a shared state-space or do not efficiently support parallel tasks that concurrently access a shared state-space. We use a processor-specialization approach to increase the effectiveness of replication and, consequently, achieve cost-effective fault tolerance in such systems. The SNMR (specialized N-modular redundancy) protocol has been developed based on these concepts. Compared to many existing Byzantine-resilient systems, the SNMR approach incurs less overhead and can be easily parameterized to fit various fault models.

Multiple agent systems are being used increasingly in various applications, including real time applications and safety critical systems. Many of these applications have a soft real time constraints and fuzzy rather than binary correctness criteria for the output value. Also, a principal characteristic of such systems is the trade off between using an efficient but less accurate strategy or a sophisticated but more time consuming strategy. We develop methods for assessing the quality of these systems in terms of the timeliness and accuracy of the output to aid decision making. We consider two commonly used coordination structures, parallel and pipeline structures. We also propose some adaptive schemes for increasing the quality of the system.

We consider a multiserver system consisting of a set of servers that provide some service to a set of clients by accessing some shared objects. The goal is to provide reliable service in spite of client or server failures such that the overhead during normal operating periods is low. We consider a relatively general fault model where a faulty processor can write spurious data for a period of time before it is detected and removed from the system. We first develop a solution in an autonomous physical world of clients and servers. The basic approach is to divide the servers into groups such that each server has some limitations which prevent it from arbitrarily damaging the system. This solution is then mapped to a distributed system of processor and memory units followed by an assessment of its performance.>

Conventionally, error checking on storage systems is performed on-the-fly (with probability 1) as the storage system is being accessed in order to improve the reliability of the storage system. However, such a procedure may needlessly cause degraded performance due to the extra processing time needed for executing the error checking code. In this paper, we consider fault-tolerance storage systems designed to provide continuous services to customers over a mission period and the design goal is (1) to maximize the cumulative number of requests that the storage system can service without failure over the mission period or (2) to be able to service at least a given number of requests without failure over the mission period with its system reliability maximized. We develop a Markov reward model to identify the design conditions under which probabilistic error checking procedures can better satisfy this design goal than conventional on-to-fly error checking procedures. The result helps determine the best time interval between successive executions of the error checking procedure to meet such design goal and is useful for designing adaptive systems that can temporarily tradeoff reliability for performance to meet design goal (2) in response to dynamic workload changes in the environment.

It is desirable to use redundant components to minimize the time required to accomplish a mission while at the same time ensuring that the mission will be completed in spite of failures. This characteristic is a fundamental requirement of the inherent fault tolerance approach. The authors first define inherently fault tolerant (IFT) programs and then review some theoretical aspects, namely, the correctness proof and existence conditions for IFT programs. They present two general classes of decentralized process-control systems that are amenable to IFT solutions.>

The authors develop a model for achieving reliable and high-performance control programs. The approach combines hierarchical control, inherent fault tolerance, and massive parallelism. The approach uses a fine-grain cellular automation for implementing the supervisory task of a hierarchical system. The use of massive parallelism significantly enhances the reliability of the process control system and speeds up the planning time. The authors present an algorithm for generating plans using cellular automation based on a discrete ray tracing algorithm. The formulated plan is optimal for the given class of control programs.>

An approach for designing high-performance ADT (abstract data type) components for massively parallel systems without sacrificing information hiding is presented. This approach merges information hiding clients and servers to achieve high communication bandwidth for transmitting requests and receiving responses. It uses multi-entry data structures, massive-state-transition interface operations, and a four-level decomposition approach to achieve both structured programming and information hiding within the ADT implementation. To facilitate the systematic design of various ADTs, they have been classified into three classes: unrelated, crystalline, and amorphous collections. The authors present general design decisions for each layer of each class of ADT and illustrate the theory with a detailed example from each class.>

We consider a distributed system consisting of a collection of clients and servers in which each server runs on a processor dedicated to it. Each server can be viewed as an instance of an abstract data-type module that provides a set of facilities for its clients. In such systems it may be possible to improve the performance of a server by scheduling its housekeeping activities to occur during periods when the server is waiting for requests from clients or is transmitting a response to a client. We consider the case where the client requests are handled by a foreground process while the maintenance tasks are performed by one or more background processes. We illustrate how the code for these processes can be developed in a stepwise manner, proceeding from coarse-grained concurrency to fine-grained concurrency. This approach is augmented with the use of rely/guarantee conditions which serve to simplify the proof of non-interference. The method is illustrated using a search-table abstraction.

Software for industrial process-control systems, such as nuclear power plant safety control systems and robots, can be very complex because of the large number of cases that must be considered. A design approach is proposed that uses decentralized control concepts, and is based on E.W. Dijkstra's concept of self-stabilizing systems (1974). This method greatly simplifies the software, so that its correctness can be verified more easily. A simple control system is described for a simulated robot that is tolerant of partial failure of controllers and mechanisms, and permits online repair and enhancement of the control functions.>

A stepwise method of deriving the high-performance implementation of a set of operations is proposed. This method is based on the ability to organize the data into a multilevel data structure to provide an efficient implementation of all the operations. Typically, for such data organization the performance may deteriorate over a period of time and that can be corrected by reorganizing the data. This data reorganization is done by the introduction of maintenance processes. For a particular example, the multilevel data organization and the different models of maintenance processes possible are considered. The various models of maintenance process provide varying amounts of concurrency by varying the degree of atomicity in different operations. Performance behavior for the different models is derived and a correctness proof for the developed implementation is outlined.>

One way of achieving high availability of data in a distributed system is to replicate the data on several nodes. We present an algorithm for a replicated storage system which takes advantage of the high reliability of ETHERNET local area networks and their broadcast capability. The algorithm is both simple and efficient. It does not use reliable communication protocols and does not require a separate recovery procedure or knowledge of the current status (up or down) of the other nodes in the network. It guarantees that all transactions will be completed within a finite time and that no record will be locked indefinitely. We discuss the properties of the algorithm and some extensions to it. We also compare it with some other methods of managing replicated storage systems.