Increasingly, safety-critical systems include artificial intelligence and machine learning components (i.e., Learning-Enabled Components (LECs)). However, when behavior is learned in a training environment that fails to fully capture real-world phenomena, the response of an LEC to untrained phenomena is uncertain, and therefore cannot be assured as safe. Automated methods are needed for self-assessment and adaptation to decide when learned behavior can be trusted. This work introduces a model-driven approach to manage self-adaptation of a Learning-Enabled System (LES) to account for run-time contexts for which the learned behavior of LECs cannot be trusted. The resulting framework enables an LES to monitor and evaluate goal models at run time to determine whether or not LECs can be expected to meet functional objectives. Using this framework enables stakeholders to have more confidence that LECs are used only in contexts comparable to those validated at design time.

Modern localization techniques allow ground vehicle robots to determine their position with centimeter-level accuracy under nominal conditions, enabling them to utilize fixed maps to navigate their environments. However, when localization measurements become unavailable, the position accuracy will drop and uncertainty will increase. While research and development on localization estimation seeks to reduce the severity of these outages, the question of what actions a robot should take under high localization uncertainty is still unresolved, and can vary on a platform-by-platform and mission-by-mission basis. In this paper, we exploit localization uncertainty measures to adapt system control parameters in real time. Offline, we optimize non-linear activation functions whose control parameters and relevant weights are trained and learned using Evolutionary Algorithm (EA). Subsequently, in real time, we apply the optimized adaptation functions to the controller look-ahead distance and intermediate linear and angular velocity commands, which we identify as the most sensitive to localization error. Evolutionary runs are conducted in which a simulated target vehicle is tasked with following a randomly generated path while minimizing cross-track error, with time varying localization uncertainty added. These runs produce situation-dependent weights for parameters to the adaptation functions, which are transferred to the physical platform, a 1:5-scale autonomous vehicle. In simulation, our system was able to reduce cross-track error, which in certain cases exceeds 250 centimeters on non-adapted systems, to below 15 centimeters on average using EA-derived weights and parameters applied to our proposed adaptation system. Evaluation on the physical platform demonstrates that without the adaptation module in place, the platform is unable to successfully follow the path; with the adaptation module, the platform automatically adjusts its velocity and look-ahead distance to compensate for localization uncertainty.

Cyber-physical systems that implement self-adaptive behavior, such as autonomous robots, need to ensure that requirements remain satisfied across run-time adaptations. The Robot Operating System (ROS), a middleware infrastructure for robotic systems, is widely used in both research and industrial applications. However, ROS itself does not assure self-adaptive behavior. This paper introduces AC-ROS, which fills this gap by using assurance case models at run time to manage the self-adaptive operation of ROS-based systems. Assurance cases provide structured arguments that a system satisfies requirements and can be specified graphically with Goal Structuring Notation (GSN) models. AC-ROS uses GSN models to instantiate a ROS-based MAPE-K framework, which in turn uses these models at run time to assure system behavior adheres to requirements across adaptations. For this study, AC-ROS is implemented and tested on EvoRally, a 1:5-scale autonomous vehicle.

Security certification establishes that a given system satisfies properties and constraints as specified in the system security profile. Mechanisms and techniques have been developed to assess if and how well the system complies with the properties, thereby providing a degree of confidence in the security certification. Generally, certification of security controls defined by NIST SP800-53 is performed at design time to provide confidence in a system’s trustworthiness to achieve the organization’s mission and business requirements. Assuring confidence in a self-adaptive system’s security profile is challenging when both functional and security conditions may change at run time. Static security solutions are insufficient, given that dynamic application of defense mechanisms often needs to dynamically adapt security functionality at run time as part of self-protection. This security adaptation may hinder maintaining functional constraints or vice versa. In addition, adaptation capabilities may give rise to the need for dynamic certification, which can be a difficult procedure given the complexity of the security dependencies. Confidence in an information system’s compliance with security constraints can be expressed using security assurance cases (SACs). NIST security controls are defined with a hierarchical structure that makes them amenable to being specified in terms of SACs. A collection of SACs for related security controls form a network that can be used to measure the confidence of security compliance through certification-based evidence. Once the system is deployed, environmental and functional uncertainties may require the coordination of functional and security adaptations. This paper introduces the MAPE-SAC, a security-focused feedback control loop, and its interaction with a MAPE-K, function and performance-focused control loop, to dynamically manage run-time adaptations in response to changes in functional and security conditions. We illustrate the use of both control loops and their interaction with an example of two independent systems that need to cooperate to facilitate autonomous search and rescue in the aftermath of a natural disaster.

Bipedal hopping is an efficient form of locomotion, yet it remains relatively rare in the natural world. Previous research has suggested that the tail balances the angular momentum of the legs to produce steady state bipedal hopping. In this study, we employ a 3D physics simulation engine to optimize gaits for an animat whose control and morphological characteristics are subject to computational evolution, which emulates properties of natural evolution. Results indicate that the order of gene fixation during the evolutionary process influences whether a bipedal hopping or quadrupedal bounding gait emerges. Furthermore, we found that in the most effective bipedal hoppers the tail balances the angular momentum of the torso, rather than the legs as previously thought. Finally, there appears to be a specific range of tail masses, as a proportion of total body mass, wherein the most effective bipedal hoppers evolve.

Animal movements are realized by a combination of high-level control from the nervous system and joint-level movement provided by the musculoskeletal system. The digital muscle model (DMM) emulates the low-level musculoskeletal system and can be combined with a high-level artificial neural network (ANN) controller forming a hybrid control strategy. Previous work has shown that, compared to ANN-only controllers, hybrid ANN/DMM controllers exhibit similar performance with fewer synapses, suggesting that some computation is offloaded to the low-level DMM. An open question is how the complexity of the robot, in terms of the number of joints, affects the evolution of the ANN control structure. We explore this question by evolving both hybrid controllers and ANN-only controllers for worm-like animats of varying complexity. Specifically, the number of joints in the worms ranges from 1 to 12. Consistent with an earlier study, the results demonstrate that, in most cases, hybrid ANN/DMM controllers exhibit equal or better performance than ANN-only controllers. In addition, above a threshold for animat complexity (number of joints), the ANNs for one variant of the hybrid controllers have significantly fewer connections than the ANN-only controllers.

We investigate a hierarchical approach to robot control inspired by joint-level control in animals. The method combines a high-level controller, consisting of an artificial neural network (ANN), with joint-level controllers based on digital muscles. In the digital muscle model (DMM), morphological and control aspects of joints evolve concurrently, emulating the musculoskeletal system of natural organisms. We introduce and compare different approaches for connecting outputs of the ANN to DMM-based joints. We also compare the performance of evolved animats with ANN-DMM controllers with those governed by only high-level (ANN-only) and low-level (DMM-only) controllers. These results show that DMM-based systems outperform their ANN-only counterparts while also exhibiting less complex ANNs in terms of the number of connections and neurons. The main contribution of this work is to explore the evolution of artificial systems where, as in natural organisms, some aspects of control are realized at the joint level.

Many robotic systems experience fluctuating dynamics during their lifetime. Variations can be attributed in part to material degradation and decay of mechanical hardware. One approach to mitigating these problems is to utilize an adaptive controller. For example, in model-free adaptive control (MFAC) a controller learns how to drive a system by continually updating link weights of an artificial neural network (ANN). However, determining the optimal control parameters for MFAC, including the structure of the underlying ANN, is a challenging process. In this paper we investigate how to enhance the online adaptability of MFAC-based systems through computational evolution. We apply the proposed methods to a simulated robotic fish propelled by a flexible caudal fin. Results demonstrate that the robot is able to effectively respond to changing fin characteristics and varying control signals when using an evolved MFAC controller. Notably, the system is able to adapt to characteristics not encountered during evolution. The proposed technique is general and can be applied to improve the adaptability of other cyber-physical systems.

The musculoskeletal systems of animals are governed by a complex network of neurons that define both high- and low-level control. Individual joints are manipulated by multi-ple muscles acting as effectors for both movement and sta-bilization. We previously proposed a digital muscle model (DMM), where the morphological and control aspects of sim-ulated joints evolve concurrently. The resulting solutions can provide insight into the evolution of natural organisms as well as possible designs for engineered systems. In this paper, we explore the integration of this model with an arti-ficial neural network (ANN), focusing on the communication connections between the two. In the singly-connected strat-egy, a single ANN output is delivered to a joint; each con-stituent muscle responds to the signal according to an evolved function. In the individually-connected strategy, a unique ANN output is delivered to each simulated muscle. Results indicate that for low degree-of-freedom (DOF) robots, the individually-connected systems exhibit higher fitness than the singly-connnected systems. However, in larger DOF robots, the two strategies perform comparably, despite the fact that evolved ANNs for the singly-connected system are consid-erably simpler in terms of the number of connections in the network.

The neuromuscular systems of animals are governed by extremely complex networks of control signals, sensory feedback loops, and mechanical interactions. Morphology and control are inherently intertwined. In the case of animal joints, groups of muscles work together to provide power and stability to move limbs in a coordinated manner. In contrast, many robot controllers handle both high-level planning and low-level control of individual joints. In this paper, we propose a joint-level control method, called digital muscles, that operates in a manner analogous to biological muscles, yet is abstract enough to apply to conventional robotic joints. An individual joint is controlled by multiple muscle nodes, each of which responds to a control signal according to a node-specific activation function. Evolving the physical orientation of muscle nodes and their respective activation functions enables relatively complex and coordinated gaits to be realized with simple high-level control. Even using a sinusoid as the high-level control signal, we demonstrate the evolution of effective gaits for a simulated quadruped. The proposed model realizes a control strategy for governing the behavior of individual joints, and can be coupled with a high-level controller that focuses on decision making and planning.

Passive joints provide a means to reduce the mechanical complexity of a robot because they do not require direct actuation from a motor. However, the inclusion of such components complicates the development process, as their behavior is highly dependent on external stimuli in combination with actuation of other components. In this paper, we describe a study on the evolution of morphological characteristics and controller parameters for an amphibious robot with passive arm joints. Results show that this approach is able to exploit the properties of passive joints, producing effective locomotion in both aquatic and terrestrial environments. Evolved solutions demonstrate a strong coupling between fin morphology and control strategy with respect to performance.

Developing complex behaviors for aquatic robots is a difficult en- gineering challenge due to the uncertainty of an underwater environment. Neuroevolution provides one method of dealing with this type of problem. Artificial neural networks discern different conditions by mapping sensory input to responses, and evolutionary computation provides a training algorithm suitable to the high dimensionality of the problem. In this paper, we present results of applying neuroevolution to an aquatic robot tasked with station keeping, that is, maintaining a given position despite surrounding water flow. The virtual device exposed to evolution is modeled af- ter a physical counterpart that has been fabricated with a 3D printer and tested in physical environments. Evolved behaviors exhibit a variety of unexpected, complex fin/flipper movements that enable the robot to achieve and maintain station, despite water flow from different directions. Moreover, the results show that evolved controllers are able to effectively carry out this task using only infor- mation from a simulated accelerometer and gyroscope, matching the inertial measurement unit (IMU) on the actual robot.

In this paper, we describe a study of the evolution of consensus, a cooperative behavior in which members in both homogeneous and heterogeneous groups, must agree on information sensed in their environment. We conducted the study using digital evolution, a form of evolutionary computation where a population of computer programs (digital organisms) exists in a user-defined computational environment and is subject to instruction-level mutations and natural selection. We placed these digital organisms into groups whose fitness relied upon their ability to perform consensus. We then tested different degrees and types of genetic variation present in the population, based on biologically inspired models of gene flow, including mutation, sexual recombination, migration, and horizontal gene transfer. Our experimental treatments examined the effect of these processes on genetic variation and groups' ability to reach consensus. The results of these experiments demonstrate that while genetic heterogeneity within groups increases the difficulty of the consensus task, a surprising number of groups were able to overcome these obstacles and evolve this cooperative behavior.

Designing a robotic fish is a challenging endeavor due to the non-linear dynamics of underwater environments. In this paper, we present an evolutionary computation approach for designing the caudal fin of a carangiform robotic fish. Evolutionary experiments are performed in a simulated environment utilizing a mathematical model to approximate the hydrodynamic motion of a flexible caudal fin. With this model, time-consuming computational fluid dynamic simulations can be avoided while maintaining a physically realistic simulation. Two approaches are employed to maximize a robotic fish's average velocity. First, a hill-climbing algorithm is applied to find the optimal stiffness for a fixed shape caudal fin. Next, both fin stiffness and shape are simultaneously optimized with a genetic algorithm. Additionally, simulated caudal fins are compared to physically validated fins, which were fabricated with the aid of a 3D printer and tested on a robotic fish prototype. Results show a correlation between evolved results, model predicted behavior, and physical robot performance with some disparity due to the difficulty in accurately approximating real world performance in a simulation environment. Despite the disparity, evolutionary design is shown to be a viable process.

Transferring virtual robotic designs into physical robots has become possible with the development of 3D printers. Accurately simulating the performance of real robots in a virtual environment requires modeling a variety of conditions, including the physical composition of the robots themselves. In this paper, we investigate how modeling material flexibility through the use of a passive joint affects the resulting arm morphology and gait of a crawling virtual robot. Results indicate that flexibility can be a beneficial characteristic of robotic morphology design while also providing insight into the benefits of modeling material properties in a simulation environment.

Quorum sensing (QS) is a collective behavior whereby actions of individuals depend on the density of the surrounding population. Bacteria use QS to trigger secretion of digestive enzymes, formation and destruction of biofilms, and, in the case of pathogenic organisms, expression of virulence factors that cause disease. Investigations of mechanisms that prevent or disrupt QS, referred to as quorum quenching, are of interest because they provide a new alternative to antibiotics for treating bacterial infections. Traditional antibiotics either kill bacteria or inhibit their growth, producing selective pressures that promote resistant strains. In contrast, quorum quenching and other so-called anti-infective strategies focus on altering behavior. In this article we evolve QS in populations of digital organisms, a type of self-replicating computer program, and investigate the effects of quorum quenching on these populations. Specifically, we injected the populations with mutant organisms that were impaired in selected ways to disrupt the QS process. The experimental results indicate that the rate at which these mutants are introduced into a population influences both the evolvability of QS and the persistence of an existing QS behavior. Surprisingly, we also observed resistance to quorum quenching. Effectively, populations evolved resistance by reaching quorum at lower cell densities than did the parent strain. Moreover, the level of resistance was highest when the rate of mutant introduction increased over time. These results show that digital organisms can serve as a model to study the evolution and disruption of QS, potentially informing wet-lab studies aimed at identifying targets for anti-infective development.

Over billions of years, natural selection has continued to select for a framework based on (1) parallelism and (2) cooperation across various levels of organization within organisms to drive their behaviors and responses. We present a design for a bottom-up, reactive controller where the agent's response emerges from many parallelized, enzymatic interactions (bottom-up) within the biologically-inspired process of signal transduction (reactive). We use enzymes to explore the potential for evolving simulated robot controllers for the central-place foraging problem. The properties of the robot and stimuli present in its environment are encoded in a digital format ("molecule") capable of being manipulated and altered through self-contained computational programs ("enzymes") executing in parallel inside each controller to produce the robot's foraging behavior. Evaluation of this design in unbounded worlds reveals evolved strategies employing one or more of the following complex behaviors: (1) swarming, (2) coordinated movement, (3) communication of concepts using a primitive language based on sound and color, (4) cooperation, and (5) division of labor.

One of the processes by which microorganisms are able to rapidly adapt to changing conditions is horizontal gene transfer, whereby an organism incorporates additional genetic material from sources other than its parent. These genetic elements may encode a wide variety of beneficial traits. Under certain conditions, many computational models capture the evolutionary dynamics of adaptive behaviors such as toxin production, quorum sensing, and biofilm formation, and have even provided new insights into otherwise unknown or misunderstood phenomena. However, such models rarely incorporate horizontal gene transfer, so they may be incapable of fully representing the vast repertoire of behaviors exhibited by natural populations. Although models of horizontal gene transfer exist, they rarely account for the spatial structure of populations, which is often critical to adaptive behaviors.

We present a study in the evolution of temporal behavior, specifically synchronization and desynchronization, through digital evolution and group selection. In digital evolution, a population of self-replicating computer programs exists in a user-defined computational environment and is subject to instruction-level mutations and natural selection. Group selection links the survival of the individual to the survival of its group, thus encouraging cooperation. Previous approaches to engineering synchronization and desynchronization algorithms have taken inspiration from nature: In the well-known firefly model, the only form of communication between agents is in the form of flash messages among neighbors. Here we demonstrate that populations of digital organisms, provided with a similar mechanism and minimal information about their environment, are capable of evolving algorithms for synchronization and desynchronization, and that the evolved behaviors are robust to message loss. We further describe how the evolved behavior for synchronization mimics that of the well-known Ermentrout model for firefly synchronization in biology. In addition to discovering self-organizing behaviors for distributed computing systems, this result indicates that digital evolution may be used to further our understanding of synchronization in biology.

HyperNEAT represents a class of neuroevolutionary algorithms that captures some of the power of natural development with a computationally efficient high-level abstraction of development. This class of algorithms is intended to provide many of the desirable properties produced in biological phenotypes by natural developmental processes, such as regularity, modularity and hierarchy. While it has been previously shown that HyperNEAT produces regular artificial neural network (ANN) phenotypes, in this paper we investigated the open question of whether HyperNEAT can produce modular ANNs. We conducted such research on problems where modularity should be beneficial, and found that HyperNEAT failed to generate modular ANNs. We then imposed modularity on HyperNEAT’s phenotypes and its performance improved, demonstrating that modularity increases performance on this problem. We next tested two techniques to encourage modularity in HyperNEAT, but did not observe an increase in either modularity or performance. Finally, we conducted tests on a simpler problem that requires modularity and found that HyperNEAT was able to rapidly produce modular solutions that solved the problem. We therefore present the first documented case of HyperNEAT producing a modular phenotype, but our inability to encourage modularity on harder problems where modularity would have been beneficial suggests that more work is needed to increase the likelihood that HyperNEAT and similar algorithms produce modular ANNs in response to challenging, decomposable problems.

Understanding the evolution of cooperation as part of an evolutionary stable strategy (ESS) is a difficult problem that has been the focus of much work. The associated costs of cooperation may lower the fitness of an organism below that of its non-cooperating counterpart, allowing the more fit organism to persist and outcompete the cooperator. Insight into these behaviors can help provide a better understanding of many aspects of the natural world, as well as provide future avenues for fighting disease.

This paper describes a study of the evolution of distributed behavior, specifically the control of agents in a mobile ad hoc network, using neuroevolution. In neuroevolution, a population of artificial neural networks (ANNs) are subject to mutation and natural selection. For this study, we compare three different neuroevolutionary systems: a direct encoding, an indirect encoding, and an indirect encoding that supports heterogeneity. Multiple variations of each of these systems were tested on a problem where agents were able to coordinate their collective behavior. Specifically, movement of agents in a simulated physics environment affected which agents were able to communicate with each other. The results of experiments indicate that this is a challenging problem domain for neuroevolution, and although direct and indirect encodings tended to perform similarly in our tests, the strategies employed by indirect encodings tended to favor stable, cohesive groups, while the direct encoding versions appeared more stochastic in nature.

For centuries it was thought that bacteria live asocial lives. However, recent discoveries show many species of bacteria communicate in order to perform tasks previously thought to be limited to multicellular organisms. Central to this capability is quorum sensing, whereby organisms detect cell density and use this information to trigger group behaviors. Quorum sensing is used by bacteria in the formation of biofilms, secretion of digestive enzymes and, in the case of pathogenic bacteria, release of toxins or other virulence factors. Indeed, methods to disrupt quorum sensing are currently being investigated as possible treatments for numerous diseases, including cystic fibrosis, epidemic cholera, and methicillin-resistant Staphylococcus aureus. In this paper we demonstrate the evolution of a quorum sensing behavior in populations of digital organisms. Specifically, we show that digital organisms are capable of evolving a strategy to collectively suppress self-replication, when the population density reaches a specific, evolved threshold. We present the evolved genome of an organism exhibiting this behavior and analyze the collective operation of this “algorithm. ” Finally, through a set of experiments we demonstrate that the behavior scales to populations up to 400 times larger than those in which the behavior evolved.

This paper describes a study of the evolution of robust communication, specifically the distribution of data among individuals in a population, using digital evolution. In digital evolution, a population of self-replicating computer programs exists in a user-defined computational environment and is subject to instruction-level mutations and natural selection. To encourage the evolution of this cooperative behavior, we make use of "digital germlines," a form of group-level selection similar to multicellularity in biology. The results of experiments using the Avida platform for digital evolution demonstrate that populations of digital organisms are capable of evolving to distribute data in a network, and that through the application of different selective pressures, these digital organisms can overcome communication obstacles such as message loss, limited bandwidth, and node failure.

As software developers, we strive to create computational systems that are as robust and versatile as biological organisms have evolved to be in nature. We propose a software development methodology capable of producing self-adaptive software, using digital evolution to discover behaviors and optimize solutions. Employing this methodology we present an example behavioral concept from inception to fruition on physical hardware, as a proof of concept of the approach. We evolve environmentally-aware motility behaviors through digital evolution, automatically translate the evolved programs into C code, and compile and load the programs onto mobile robots.

The use of chemicals to communicate among organisms has enabled countless species, from microorganisms, to colonies of insects, to mammals, to survive and flourish in their respective environments. Ants, arguably nature's most successful exploiters of this behavior, have evolved the use of pheromones to communicate in a wide range of situations, including mating, colony recognition, territory marking, and recruitment to new nest sites and food sources. We examine the evolution of the use of pheromones to aid in the location of, and migration to, a target area by groups of digital organisms. In an initial set of experiments, these organisms evolved efficient patterns of exploration that obviated the need for pheromones. When evolved in a more adverse environment, organisms again evolved effective search strategies, but also evolved the use of pheromones to enable the task to be completed by group members more quickly and with fewer movements. We also show that evolved organisms are more robust and better able to react to a change in the environment than a handbuilt solution. This work demonstrates the complexities that exist in the evolution of pheromone-enabled cooperation and provides insight into the behaviors executed by seemingly simple organisms in nature.

In general, a population will grow until a limiting factor, such as resource availability, is reached. However, increased task efficiency can also regulate the size of a population during task development. Through the use of digital evolution, we demonstrate that the evolution of a group-level task, requiring a small number of individuals, can cause a population to self-regulate its size, even in the presence of abundant energy. We also show that as little as a 1% transfer of energy from a parent group to its offspring produces significantly better results than no energy transfer. A potential application of this result is the configuration and management of real-world distributed agent-based systems.

This paper describes a study in the evolution of cooperative behavior, specifically the construction of communication networks, through digital evolution and multilevel selection. In digital evolution, a population of self-replicating computer programs exists in a user-defined computational environment and is subject to instruction-level mutations and natural selection. Multilevel selection links the survival of the individual to the survival of its group, thus encouraging cooperation. The results of experiments using the Avida digital evolution platform demonstrate that populations of digital organisms are capable of constructing communication networks, and that these networks can exhibit desired properties depending on the selective pressures used. We also show that the use of a digital germline can significantly improve evolvability of cooperation.

This paper describes a study in the evolution of distributed cooperative behavior, specifically leader election, through digital evolution and group selection. In digital evolution, a population of self-replicating computer programs exists in a user-defined computational environment and is subject to instruction-level mutations and natural selection. Group selection is the theory that the survival of the individual is linked to the survival of the group, thus encouraging cooperation. The results of experiments using the Avida digital evolution platform demonstrate that group selection can produce populations capable of electing a leader and, when that leader is terminated, electing a new leader. This result serves as an existence proof that group selection and digital evolution can produce complex cooperative behaviors, and therefore have promise in the design of robust distributed computing systems.

Autonomic computing systems must be able to detect and respond to errant behavior or changing conditions with little or no human intervention. Clearly, decision making is a critical issue in such systems, which must learn how and when to invoke corrective actions based on past experience. This paper describes the design, implementation, and evaluation of MESO, a pattern classifier designed to support online, incremental learning and decision making in autonomic systems. A novel feature of MESO is its use of small agglomerative clusters, called sensitivity spheres, that aggregate similar training samples. Sensitivity spheres are partitioned into sets during the construction of a memory-efficient hierarchical data structure. This structure facilitates data compression, which is important to many autonomic systems. Results are presented demonstrating that MESO achieves high accuracy while enabling rapid incremental training and classification. A case study is described in which MESO enables a mobile computing application to learn, by imitation, user preferences for balancing wireless network packet loss and bandwidth consumption. Once trained, the application can autonomously adjust error control parameters as needed while the user roams about a wireless cell

This paper describes service clouds, a distributed infrastructure designed to facilitate rapid prototyping and deployment of adaptive communication services. The infrastructure combines adaptive middleware functionality with an overlay network substrate in order to support dynamic instantiation and reconfiguration of services. The service clouds architecture includes a collection of low-level facilities that can be invoked directly by applications or used to compose more complex services. After describing the service clouds architecture, we present results of experimental case studies conducted on the PlanetLab Internet testbed alone and a mobile computing testbed.

This paper describes Service Clouds, a distributed infrastructure designed to facilitate rapid prototyping and deployment of services that enhance communication performance, robustness, and security. The infrastructure combines adaptive middleware functionality with an overlay network substrate in order to support dynamic instantiation and reconfiguration of services. The Service Clouds architecture includes a collection of low-level facilities that can be either invoked directly by applications or used to compose more complex services. After describing the Service Clouds architecture, we present results of two experimental case studies conducted on the PlanetLab Internet testbed, the first to improve throughput of bulk data transfer, and the second to enhance the robustness of multimedia streaming

Abstract This paper describes the internal architecture and operation of an adaptable communication component called the MetaSocket. MetaSockets are created using Adaptive Java, a reflective extension to Java that enables a component's internal architecture and behavior to be adapted at runtime in response to external stimuli. This paper describes how adaptive behavior is implemented in MetaSockets, as well as how MetaSockets interact with other adaptive components, such as decision makers and event mediators. Results of experiments on a mobile computing testbed demonstrate how MetaSockets respond to dynamic wireless channel conditions in order to improve the quality of interactive audio streams delivered to iPAQ handheld computers. Copyright © 2006 John Wiley & Sons, Ltd.

Energy optimization is important in wireless ad hoc networks, where node battery power is usually limited. Research results show that such a network can exploit controlled node mobility to reduce communication-related energy consumption. However, node movement itself usually consumes energy. In this paper we study the energy optimization problem that accounts for energy costs associated with both communication and physical node movement. We refer to this model as informed mobility. We first review the theoretical foundations on how to reduce total communication energy consumption, as well as increase system lifetime, by combining node movement and transmission power adaptation. Next, we describe and analyze the informed mobility optimization problem. Based on this analysis, we introduce localized algorithms and protocols for informed mobility. We propose iMobif, a flow-based informed mobility framework that collects network information for mobility decision making. We demonstrate how to use iMobif to minimize total communication energy consumption as well as to maximize system lifetime. We compare the performance of iMobif to that of systems with no mobility or only cost-unaware mobility. Simulation results show iMobif is effective in reducing energy consumption relative to such systems.

We propose an Adaptive CORBA Template (ACT), which enables run-time improvements to CORBA applications in response to unanticipated changes in either their functional requirements or their execution environments. ACT enhances CORBA applications by transparently weaving adaptive code into their object request brokers (ORBs) at run time. The woven code intercepts and adapts the requests, replies, and exceptions that pass through the ORBs. Specifically, ACT can be used to develop an object-oriented framework in any language that supports dynamic loading of code and can be applied to any CORBA ORB that supports portable interceptors. Moreover, ACT can be used to support interoperation among otherwise incompatible adaptive CORBA frameworks. To evaluate the performance and functionality of ACT, we implemented a prototype in Java. Our experimental results show that the overhead introduced by the ACT infrastructure is negligible, while the adaptations offered are highly flexible.

Path probing is essential to maintain an efficient overlay network topology. However, the cost of complete probing can be as high as O(n/sup 2/), which is prohibitive in large-scale overlay networks. Recently we proposed a method that trades probing overhead for inference accuracy in sparse networks such as the Internet. The method uses physical path information to infer path quality for all of the n/spl times/(n-1) overlay paths, while actually probing only a subset of the paths. We propose and evaluate a distributed approach to implement this method. We describe a minimum diameter, link-stress bounded overlay spanning tree, which is used to collect and disseminate path quality information. All nodes in the tree collaborate to infer the quality of all paths. Simulation results show this approach can achieve a high-level of inference accuracy while reducing probing overhead and balancing link stress on the spanning tree.

This paper addresses the energy consumption of forward error correction (FEC) protocols as used to improve quality-of-service (QoS) for wireless computing devices. The paper also characterizes the effect on energy consumption and QoS of the power saving mode in 802.11 wireless local area networks (WLANs). Experiments are described in which FEC-encoded audio streams are multicast to mobile computers across a WLAN. Results of these experiments quantify the tradeoffs between improved QoS, due to FEC, and additional energy consumption caused by receiving and decoding redundant packets. Two different approaches to FEC are compared relative to these metrics. The results of this study enable the development of adaptive software mechanisms that attempt to manage these tradeoffs in the presence of highly dynamic wireless environments.

Path probing is essential to maintaining an efficient overlay network topology. However, the cost of a full-scale probing is as high as O(n/sup 2/), which is prohibitive in large-scale overlay networks. Several methods have been proposed to reduce probing overhead, although at a cost in terms of probing completeness. In this paper, an orthogonal solution is proposed that trades probing overhead for estimation accuracy in sparse networks such as the Internet. The proposed solution uses network-level path composition information (for example, as provided by a topology server) to infer path quality without full-scale probing. The inference metrics include latency, loss rate and available bandwidth. This approach is used to design several probing algorithms, which are evaluated through analysis and simulation. The results show that the proposed method can significantly reduce probing overhead while providing hounded quality estimations for all n /spl times/ (n - 1) overlay paths. The solution is well suited to medium-scale overlay networks in the Internet. In other environments, it can be combined with extant probing algorithms to further improve performance.

Experiments with an IEEE 802.11 wireless LAN show that the packet losses at multiple nodes can exhibit a certain degree of correlation. Analysis and simulation results show that conventional packet loss models do not adequately capture the loss characteristics exhibited in experimental traces. This paper proposes a new approach for modeling packet losses that explicitly accounts for spatial loss correlation. The improved accuracy of the new approach, compared to conventional models, is demonstrated by comparing results of simulations and experiments.

Describes the design and operation of a composable proxy infrastructure that enables mobile Internet users to collaborate via heterogeneous devices and network connections. The approach is based on detachable Java I/O streams, which enable proxy filters and transcoders to be dynamically inserted, removed, and reordered on a given data stream. Unlike conventional Java I/O streams, detachable streams can be stopped, disconnected, reconnected, and restarted. As such, they provide a convenient method by which to support the dynamic composition of proxy services. Moreover, use of the I/O stream abstraction enables network distribution and stream adaptability to be implemented transparently with respect to application components. The operation and implementation of detachable streams are described. To evaluate the composable proxy infrastructure, it is used to enhance interactive audio communication among users of a Web-based collaborative computing framework. Two forward error correction (FEC) proxylets are developed, one using block erasure codes and the other using the GSM 06.10 encoding algorithm. Separately, each type of FEC improves the ability of the audio stream to tolerate errors in a wireless LAN environment. When composed in a single proxy, however, they cooperate to correct additional types of burst errors. Results are presented from a performance study conducted on a mobile computing testbed.

This paper addresses the problem of reliably multicasting Web resources across wireless local area networks (WLANs) in support of collaborative computing applications. An adaptive forward error correction (FEC) protocol is described, which adjusts the level of redundancy in the data stream in response to packet loss conditions. The proposed protocol is intended for use on a proxy server that supports mobile users on a WLAN. The software architecture of the proxy service and the operation of the adaptive FEC protocol are described. The performance of the protocol is evaluated using both experimentation on a mobile computing testbed as well as simulation. The results of the performance study show that the protocol can quickly accommodate worsening channel characteristics in order to reduce delay and increase throughput for reliable multicast channels.

A core-based forwarding multicast protocol uses a core router as a traffic transit center: All multicast packets are first sent to the core, then distributed to destinations on a multicast tree rooted at the core. The purpose of this paper was to evaluate, via simulation, the effect of various core selection methods on multicast performance. Performance metrics of interest include network resource usage, packet delay, the join time of multicast participants, and link congestion. In addition, we assess the feasibility of these heuristics in real-world environments. The main contribution of this work is the discovery of a simple yet effective core selection heuristic that can be implemented in a wide variety of networks. Specifically, our results show that the tree center heuristic (using the center of the existing multicast tree as the new core node) significantly outperforms heuristics based on random selection and performs as well as other heuristics that are computationally more expensive. © 2000 John Wiley & Sons, Inc.

This paper describes Pavilion, an object-oriented middleware framework for developing collaborative web-based applications. Pavilion enables a developer to construct new applications by inheriting and extending its default functionality. Reusable and extensible Pavilion components include interfaces to common web browsers, a reliable multicast protocol tailored for delivery of web resources, a leadership protocol for floor control, and a highly modular proxy server that supports data type-specific plug-ins. The architecture and operation of Pavilion are described, followed by a discussion of VGuide, a synchronous VRML application built using Pavilion. VGuide enables one user to lead other users through virtual worlds in a synchronous manner.

Traditionally, link-state routing (LSR) uses two costly techniques to achieve its robustness and responsiveness: message forwarding on every communication link in the broadcast of network status updates, and the periodic broadcast of local status by every router. In this paper, we present a novel LSR protocol, called tree-based LSR (T-LSR), which reduces the operational overhead of LSR as follows. A leader router is elected to periodically broadcast network status on behalf of all the other routers in the network, and a spanning tree is constructed to support these broadcasts. The T-LSR protocol distinguishes itself from previous tree-based, lightweight LSR methods by its fault-tolerance features: the T-LSR protocol is shown to maintain consistent routing information and leader preferences throughout the network in the presence of undetected transmission/information corruption problems. The results of a simulation study demonstrate that the T-LSR protocol imposes a small fraction of the overhead of conventional LSR.

This paper presents a case study in the use of reliable multicasting in Web-based multi-party applications. To carry out this study, we have designed and implemented WEBCLASS, a multicast browser tool written in Java. In WEBCLASS, all the actions of a "master" Web browser are mimicked on a set of client browsers. Monitoring of the master browser is performed by a set of threads, which use a reliable multicast protocol to disseminate state information and Web resources to programs that control the client browsers. The architecture and operation of the main components of WEBCLASS are described, and experimental results of a performance study are presented.

This paper describes H-RMC, a reliable multicast protocol designed for implementation in the Linux kernel.H-RMC takes advantage of IP multicast and is primarily a NAK-based protocol.To accommodate low-loss environments, where feedback in the form of NAKs is scarce, H-RMC receivers return periodic update messages in the absence of other reverse traffic.H-RMC uses a combination of rate-based and window-based flow control.The sender maintains minimal information about each receiver so that buffered data is not released prematurely, and polls receivers in case it has not heard from them at the time of buffer release.Combined, these techniques produce a reliable multicast data stream with a relatively low rate of feedback.Performance results show that adequate kernel buffer space, combined with a two-stage rate control method and polling, are effective in minimizing feedback from receivers and thereby in maintaining reasonable throughputs.

Given the ubiquity of multimedia technology, it is important that Computer Science students not only learn the basics of multimedia design, but also gain hands-on experience with applications of the technology. This paper describes the integration of multimedia concepts and tools into a Computer Science curriculum. An NSF-sponsored Multimedia Laboratory was established and used to support three senior-level courses: software engineering, computer graphics, and computer networks. Curriculum development, laboratory exercises, and the role of projects are described.

We propose solutions to several multicast core management problems, including automatic core selection, core failure handling, and core migration, for use in networks based on link-state routing. The proposed approach uses a central server, called the core binding server (CBS), to manage core-group bindings, accompanied by a network-level leader election protocol in order to achieve robustness. By modeling the selection of the CBS as a leader election problem, this approach can handle any combination of network component failures, including those that partition the network. Further, our simulation results reveal that the central server can sustain extremely high workloads, and demonstrate the effectiveness of our core selection and core migration methods.

A core-based forwarding multicast protocol uses a core router as a traffic transit center: all multicast packets are first sent to the core, then distributed to destinations on a multicast tree rooted at the core. The purpose of this paper is to evaluate, via simulation, the effect of various core selection methods on multicast performance. The main contribution of this work is the discovery of a simple yet effective core selection heuristic that can be implemented in a wide range of networks. Specifically, our results show that the tree center heuristic (using the center of the existing multicast tree as the new core node) significantly outperforms heuristics based on random selection, and performs as well as heuristics that are more computationally expensive.

Algorithmic enhancements are described that enable large computational reduction in mean square-error data clustering. These improvements are incorporated into a parallel data-clustering tool, P-CLUSTER, designed to execute on a network of workstations. Experiments involving the unsupervised segmentation of standard texture images were performed. For some data sets, a 96 percent reduction in computation was achieved.

In this work, we place the problem of group leader election in a context "inside the network," meaning that participants in the election process are network switches/routers, rather than hosts. A robust solution to the problem, called the Network Leader Election (NLE) protocol, is proposed for use in networks based on link-state routing (LSR). The protocol is robust, for it achieves leadership consensus in the presence of adverse events, such as leader failures and network partitioning. The correctness of the protocol can be proved formally. A simulation study reveals that the NLE protocol incurs low overhead in handling leader failures and in group creation. In addition, it is shown how important network functions, including hierarchical routing, address resolution, and multicast core management, can benefit from the NLE protocol.

In this paper, we propose a flooding method, called switch-aided flooding (SAF), for use in ATM networks. SAF-based protocols take advantage of hardware-supported cell relay and cell duplication, characteristic of such networks, in order to reduce the time needed to disseminate changes in network topology and resource availability. SAF protocols use a spanning multipoint connection (SMC), which is a hardware-switched network spanning tree, but revert to conventional link-by-link flooding when the spanning MC is unavailable or under construction. The results of a simulation study reveal that the proposed flooding protocols deliver network updates several times faster than conventional approaches, while using significantly less bandwidth.

A centralized protocol, C-GMC, is proposed for the construction and maintenance of multipoint connections (MCs). The operation of the protocol is independent of the MC topology algorithm, which is rendered a "plug-in" module. The C-GMC protocol is targeted at networks based on link state routing and uses the concept of a per-MC server. The problems of server election and migration are modeled as consensus problems in distributed systems, and an efficient solution is proposed. Results of a simulation study show that the C-GMC protocol is able to efficiently handle worst case workloads generated by multiparty communication sessions with thousands of participants.

A new approach to the design of collective communication operations in wormhole-routed mesh networks is described. The approach extends the concept of dominating sets in graph theory by accounting for the relative distance-insensitivity of the wormhole switching strategy and by taking advantage of a multiport communication architecture, which allows each node to simultaneously transmit messages on different outgoing channels. Collective communication operations are defined in terms of sets of extended dominating nodes (EDNs). The nodes in a set of EDNs can deliver (receive) messages to (from) a different, larger set of nodes in a single message-passing step under dimension-ordered wormhole routing and without channel contention among messages. The EDN model can be applied to different collective operations in 2D and 3D mesh networks. The authors focus on EDN-based broadcast and global combine operations. Performance evaluation results are presented that confirm the advantage of this approach over other methods.

We propose a protocol for the construction and maintenance of multipoint connections (MCs). The protocol is based on link-state routing: information regarding multipoint connections is broadcast to network switches, which perform all computations locally. The protocol is generic in that it can be used with MCs of different types, including symmetric MCs, receiver-only MCs, and asymmetric MCs. Results of a simulation study show that this generality can be achieved with negligible (in normal traffic periods) to moderate (in very busy periods) signaling overhead.

Algorithmic enhancements are described that allow large reduction (for some data sets, over 95 percent) in the number of floating point operations in mean square error data clustering. These improvements are incorporated into a parallel data clustering tool, P-CLUSTER, developed in an earlier study. Experiments on segmenting standard texture images show that the proposed enhancements enable clustering of an entire 512/spl times/512 image at approximately the same computational cost as that of previous methods applied to only 5 percent of the image pixels.

A new approach to broadcast in wormhole-routed two- and three-dimensional torus networks is proposed. The underlying network is assumed to support only deterministic, dimension-ordered unicast routing. The approach extends the graph theoretical concept of dominating nodes by accounting for the relative distance-insensitivity of the wormhole routing switching strategy. The proposed algorithm also takes advantage of an all-port communication architecture, which allows each node to simultaneously transmit messages on different outgoing channels. The resulting broadcast operation is based on a tree structure that uses multiple levels of extended dominating nodes(EDNs). Performance results are presented that confirm the advantage of this method over other approaches.

This paper presents the results of an investigation of collective communication operations for distributed computing across asynchronous transfer mode (ATM) networks. Several collective operations have been implemented and studied on a three-switch ATM network testbed at Michigan State University. The methods use virtual topologies constructed from ATM virtual channels. A particular type of virtual topology is described that efficiently implements several collective operations through the use of hardware-supported ATM multicast channels. Performance measurements are presented that illustrate how a thread-based software design can take advantage of such underlying hardware features.

This paper defines and describes the properties of a multicast virtual topology, the M-array and a resource-efficient variation, the REM-array. It is shown how several collective operations can be implemented efficiently using these virtual topologies, while maintaining low complexity. Because the methods are applicable to any parallel computing environment that supports multicast communication in hardware, they provide a framework for collective communication libraries that are portable and yet take advantage of such low-level hardware functionality. In particular, the paper describes the practical issues of using these methods in wormhole-routed massively parallel computers (MPCs) and in workstation clusters connected by Asynchronous Transfer Mode (ATM) networks. Performance results are given for both environments.

In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. This method may be used to develop deterministic, partially-adaptive, and fully-adaptive routing algorithms for wormhole-routed networks with arbitrary topologies. We first establish the necessary and sufficient condition for deadlock free routing, based on the analysis of the message flow on each channel. We then use the model to develop new adaptive routing algorithms for 2D meshes.>

This paper presents efficient algorithms that implement one-to-many, or multicast, communication in wormhole-routed torus networks. By exploiting the properties of the switching technology and the use of virtual channels, a minimum-time multicast algorithm is presented for n-dimensional torus networks that use deterministic, dimension-ordered routing of unicast messages. The algorithm can deliver a multicast message to m-1 destinations in [log/sub 2/ m] message-passing steps, while avoiding contention among the constituent unicast messages. Performance results of a simulation study on torus networks with up to 4096 nodes are also given.>

The paper presents the results of an investigation into the efficient implementation of reduction operations for cluster-based parallel computing across asynchronous transfer mode (ATM) local area networks. The study combines graph theoretical analysis with experimentation on an ATM network. Different reduction algorithms are analyzed in terms of the amount of message traffic produced and the number of message-passing steps required. This analysis, which indicates how to take advantage of switch-based interconnects and hardware multicast communication, is applied to the development of both N/1 and N/K reduction protocols. Performance measurements from implementations on a three-switch ATM testbed are presented to support the analytical results.>

Clusters of high-performance workstations are emerging as promising platforms for parallel scientific computing. The paper describes an eigenvalue solver for symmetric tridiagonal matrices, as implemented on a cluster of workstations using two different interprocess communication packages, PVM and P4. The algorithm is based on the split-merge technique, which uses Laguerre's iteration and exploits the separation property of rank two splitting in order to create subtasks that can be solved independently. A performance study that compares the distributed, parallel split-merge algorithm to a parallel version of the well-known bisection algorithm, over standard matrix types, demonstrates the performance advantage of the new algorithm and its cluster implementation.>

A new approach to broadcast in wormhole-routed three-dimensional (3D) mesh networks is proposed. The approach extends the concept of dominating sets from graph theory by accounting for the relative distance-insensitivity of the wormhole routing switching strategy and by taking advantage of an all-port communication architecture, which allows each node to simultaneously transmit messages on different outgoing channels. The resulting broadcast operation is based on a tree structure that is composed of multiple levels of extended dominating nodes (EDN). Performance evaluation results, in the form of analysis and simulation, are presented that confirm the advantage of this technique over the recursive doubling approaches to broadcast.

This paper presents efficient algorithms that implement one-to-many, or multicast, communication in wormhole-routed torus networks. By exploiting the properties of the switching technology and the use of virtual channels, a minimum-time multicast algorithm is presented for n-dimensional torus networks that use deterministic, dimension-ordered routing of unicast messages. The algorithm can deliver a multicast message to m - 1 destinations in [log_2 m] message-passing steps, while avoiding contention among the constituent unicast messages. Performance results of a simulation study on torus networks are also given.

Parallel implementations of two computer vision algorithms on distributed cluster platforms are described. The first algorithm is a square-error data clustering method whose parallel implementation is based on the well-known sequential CLUSTER program. The second algorithm is a motion parameter estimation algorithm used to determine correspondence between two images taken of the same scene. Both algorithms have been implemented and tested on cluster platforms using the PVM package. Performance measurements demonstrate that it is possible to attain good performance in terms of execution time and speedup for large-scale problems, provided that adequate memory; swap space, and I/O capacity are available at each node.

A new model for broadcast in wormhole-routed networks is proposed. The model uses and extends the concept of dominating sets in order to systematically develop efficient broadcast algorithms for all-port wormhole-routed systems, in which each node can simultaneously transmit messages on different outgoing channels. In this paper, two broadcast algorithms for two-dimensional (2D) mesh networks are presented. In the first approach, the source node uses a multicast algorithm to deliver the message to a set of dominating nodes, which can subsequently deliver the message to all other nodes in the network in a single message-passing step. This algorithm requires at most [log2N] steps, where N is the total number of nodes in the network, although in many cases only [log2N]−1 steps are needed. The second algorithm, called the D-node algorithm, reduces the number of steps by using multiple levels of dominating nodes in a recursive manner. For square meshes containing N=22(k+2) nodes, k≥0, the D-node algorithm requires at most k+4 steps. Similar upper bounds are shown to hold for meshes of other sizes and shapes. For specific source nodes and mesh shapes, the number of steps is shown to equal the theoretical lower bound of [log5N]. A simulation study confirms the advantage of the D-node algorithm, under various system parameters and conditions, over other broadcast algorithms.

This paper presents the results of an investigation into the efficient implementation of multicast operations for cluster-based parallel computing on asynchronous transfer mode (ATM) networks. Both software- and hardware-based multicast operations have been implemented and studied on a three-switch ATM network testbed. Performance measurements are presented that illustrate how software approaches can best take advantage of switch-based network architectures, and what additional advantage can be gained from using underlying hardware support.>

Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms.>

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log/sub 2/ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given.>

In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. We first establish the necessary and sufficient condition for deadlock-free routing based on the analysis of the message flow on each channel. We then show how to use the model to prove that a given adaptive routing algorithm is deadlock-free. Finally, we use the method to develop new, efficient adaptive routing algorithms for 2D meshes and hypercubes.

A method to reduce broadcast time in wormhole routed hypercube systems in described. The method takes advantage of the destance insensitivity of wormhole routing and the presence of multiple ports between processors and their routes. Performance results from an nCUBE-2 multicomputers are given that demonstrate the advantage of the method over the traditional spanning binomial tree approach.

This paper addresses the problem of collective data distribution, specifically multicasi, in wormhole-rouied hypercubes.The system model allows a processor to send and receive data in all dimensions simultaneously.New theoretical results that characterize contention among messages in wormhole-routed hypercubes are developed and used to design new multicast routing algorithms.The algorithms are compared in terms of the number of steps required in each, their measured execution times when implemented on a relatively small-scale nCUBE-2, and their simulated execution times on larger hypercubes.The results indicate that significant performance improvement is possible when the multicast algorithm actively identifies and uses multiple ports in parallel.

Practical and efficient implementations of barrier synchronization for wormhole-routed hypercube multicomputers are presented. Both broadcast and multicast barrier synchronization are considered. For systems that do not support hardware broadcast or multicast, a software U-cube tree is proposed. This method generalizes to n-dimensional meshes. Performance measurements for several barrier synchronization techniques implemented on a 64-node nCUBE-2 are given.>

The authors describe the initial implementation of the ComPaSS communication library to support scalable software development in massively parallel processors. ComPaSS provides high-level global communication operations for both data manipulation and process control, many of which are based on a small set of low-level communication primitives. The ComPaSS library is unique in that these low-level operations are provably optimal for a class of architectures representative of many commercial scalable systems-in particular, those using wormhole routing and n-dimensional mesh network topologies. The authors concentrate on the multicast component of the ComPaSS library, which is useful in several data parallel operations. The design of the multicast primitive is described, and an example of its use in a data parallel application is given. Improvements in performance resulting from use of the library on a 64-node nCUBE-2 are presented.>

Reconfigurable chips are fabricated with redundant elements that can be used to replace the faulty elements. The fault cover problem consists of finding an assignment of redundant elements to the faulty elements such that all of the faults are repaired. In reconfigurable chips that consist of arrays of elements, redundant elements are configured as spare rows and spare columns. This paper considers the problem in which a chip contains several replicates of a heterogeneous array, one or more sets of spare rows, and one or more sets of spare columns. Each set of spare rows is identical to the set of rows in the array, and each set of spare columns is identical to the set of columns in the array. Specifically, an ith spare row can only be used to replace an ith row of an array, and similarly with spare columns. Repairing the chip reduces to finding a cover for the faults in each of the arrays. These covers must be disjoint; that is, a particular spare row or spare column can be used in the cover of at most one array. Results are presented for three fault cover problems that arise under these conditions.

Recently, multichannel networks composed of several parallel, medium-speed channels multiplexed on a single high-speed medium have been proposed as a practical way to harness the high bandwidths of optical fibers. In order to limit the cost of network interfaces, a partially-connected multichannel network allows each node access to only a proper subset of the channels, its channel set. Staircase interconnection topologies constitute a family of partially-connected multichannel networks in which every node can still send messages directly to every other node.

A description is given of the token-passing multicast (TPM) protocol, a token-based protocol that provides reliable, ordered multicast communication for distributed process groups in the presence of failures and network partitions. The TPM protocol combines several positive features of other reliable multicast schemes into a single protocol, yet maintains a relatively simple structure and requires that only a minimal amount of state information be kept by process group members. It is designed specifically for computing environments with relatively low error rates, such as local area networks, and for process groups in which communication is symmetric, that is, each group member can send messages to the group, and the source must be a member of the group.>