Summary In dynamically evolving graphs, one may be interested in continuously observing certain properties of the graph. One approach for continuous monitoring is to re‐execute the graph analytics program on the entire graph after it is updated. However, this approach can lead to high computation cost and latency in case of large graphs. An alternate approach, which we present in this paper, is to execute the analytics program only initially and then perform incremental computations for supporting continuous queries as the graph is modified. The goal of our work is to develop incremental parallel computing techniques to continuously monitor a graph as it is updated to check for the properties of interest. We present the results of our investigation of utilizing a transactional model of parallel programming for supporting continuous queries on dynamic and evolving graphs. In our model, the graph updates are performed as transactions, which trigger the execution of a set of transactional tasks to perform incremental computations. In our testbed system, the graph data is stored in the RAM of cluster nodes, and continuous queries involve the parallel execution of transactional tasks on the cluster nodes. Using a set of graph problems, we illustrate this approach and evaluate its performance.

We present here the results of our investigation of a transactional model of parallel programming on cluster computing systems. This model is specifically targeted for graph applications with the goal of harnessing unstructured parallelism inherently present in many such problems. In this model, tasks for vertex-centric computations are executed optimistically in parallel as serializable transactions. A key-value based globally shared object store is implemented in the main memory of the cluster nodes for storing the graph data. Task computations read and modify data in the distributed global store, without any explicitly programmed message-passing in the application code. Based on this model we developed a framework for parallel programming of graph applications on computing clusters. We present here the programming abstractions provided by this framework and its architecture. Using several graph problems we illustrate the simplicity of the abstractions provided by this model. These problems include graph coloring, k-nearest neighbors, and single-source shortest path computation. We also illustrate how incremental computations can be supported by this programming model. Using these problems we evaluate the transactional programming model and the mechanisms provided by this framework.

We present here a scalable protocol for transaction management in key-value based multi-version data storage systems supporting partial replication of data in cloud and cluster computing environments. We consider here systems in which the database is sharded into partitions, a partition is replicated only at a subset of the nodes in the system, and no node contains all partitions. The protocol presented here is based on the Partitioned Causal Snapshot Isolation (PCSI) model and it enhances the scalability of that model. The PCSI protocol is scalable for update transactions which involve updating of only local partitions. However, it faces scalability limitations when transactions update non-local partitions. This limitation stems from the scheme used for obtaining update timestamps for remote partitions, causing vector clocks to grow with the system configuration size. We present here a new protocol based on the notion of sequence number escrow and address the underlying technical problems. Our experimental evaluations show that this protocol scales out almost linearly when workloads involve transactions with remote partition updates. We present here the performance of this protocol for three different workloads with varying mix of transaction characteristics.

We present a transaction model which simultaneously supports different consistency levels, which include serializable transactions for strong consistency, and weaker consistency models such as causal snapshot isolation (CSI), CSI with commutative updates, and CSI with asynchronous updates. This model is useful in managing large-scale replicated data with different consistency guarantees to make suitable trade-offs between data consistency and performance. Data and the associated transactions are organized in a hierarchy which is based on consistency levels. Certain rules are imposed on transactions to constrain information flow across data at different levels in this hierarchy to ensure the required consistency guarantees. The building block for this transaction model is the snapshot isolation model. We present an example of an e-commerce application structured with data items and transactions defined at different consistency levels. We have implemented a testbed system for replicated data management based on the proposed multilevel consistency model. We present here the results of our experiments with this e-commerce application to demonstrate the benefits of this model.

We address the problem of building scalable transaction management mechanisms for multi-row transactions on key-value storage systems, which are commonly termed as NoSQL systems. We develop scalable techniques for transaction management utilizing the snapshot isolation (SI) model. Because the SI model can lead to non-serializable transaction executions, we investigate two conflict detection techniques for ensuring serializability. To support scalability, we investigate system architectures and mechanisms in which the transaction management functions are decoupled from the storage system and integrated with the application-level processes. We present two system architectures and demonstrate their scalability under the scale-out model of cloud computing platforms. In the first system architecture all transaction management functions are executed in a fully decentralized manner by the application processes. The second architecture is based on a hybrid approach in which the conflict detection functions are performed by a dedicated service. We perform a comparative evaluation of these architectures using the TPC-C benchmark and demonstrate their scalability.

We present here a transaction management protocol using causal snapshot isolation in partially replicated multi-version databases. We consider here replicated databases consisting of multiple disjoint data partitions. A partition is not required to be replicated at all database sites, and a site may contain replicas for any number of partitions. Transactions can execute at any site and read or write data from any subset of the partitions, and its updates are propagated asynchronously to other sites. The protocol ensures that the snapshot observed by a transaction contains data versions that are causally consistent. The protocol requires propagating updates only to the sites replicating the updated items. In developing this protocol, we address the issues that are unique in supporting transactions with causal consistency together with the snapshot isolation model in partially replicated databases. Through experimental evaluations, we demonstrate the scalability of this model and its performance benefits over full replication models.

We present here a system architecture and its underlying mechanisms for building autonomically scalable and resilient services on cooperatively shared computing platforms. Specifically, our focus is on utilizing computing platforms exhibiting the following characteristics. The resources at a node in such platforms are allocated to competing users on fair-share basis, without any reserved resource capacities for any user. There is no platform-wide resource manager for the placement of users on different nodes. The users independently select nodes for their applications. Moreover, a node can become unavailable at any time due to crashes or shutdowns. Building scalable services in such environments poses unique challenges due to node-level fluctuations in the available resource capacities and node crashes. The service load may surge in a short time due to flash crowds. Autonomic scaling of service capacity is performed by dynamic control of the degree of service replication based on the estimated service capacity and the observed load. We present here models for estimating the service capacity at a node under fluctuating operating conditions. Furthermore, we develop adaptive and agile load distribution mechanisms for distributing load among replicas based on their time-varying service capacities. We present the results of our evaluations of these mechanisms on PlanetLab, which exemplifies the platform level characteristics considered here.Copyright © 2013 John Wiley & Sons, Ltd.

The focus of our work is on studying the resource availability characteristics of large-scale, cooperatively pooled, shared computing platforms. Our focus is on platforms in which resources at a node are allocated to competing users on fair-share basis, without any reserved resource capacities for any user, and there is no platform-wide resource manager for the placement of users on different nodes. The users independently select nodes for their applications. Our study is focused on the PlanetLab system which exemplifies such platforms. The goal of our study is to develop heuristics based on the observed resource availability characteristics for selecting nodes for deploying applications. Our approach uses the notion of eligibility period, which represents a contiguous duration for which a node satisfies a given resource requirement. We study the characteristics of the eligibility periods of Planetlab nodes for various resource capacity requirements. Based on this study we develop heuristics for identifying nodes that are likely to satisfy a given requirement for long durations. We also develop an online model for predicting the idle resource capacity that is likely to be available on a node over a short term. We evaluate and demonstrate the performance benefits of the node selection techniques and the prediction model using the PlanetLab node utilization data traces collected at different intervals over an extended period of several months.

We address the problem of building scalable transaction management mechanisms for multi-row transactions on key-value storage systems. We develop scalable techniques for transaction management utilizing the snapshot isolation (SI)model. Because the SI model can lead to non-serializable transaction executions, we investigate two conflict detection techniques for ensuring serializability under SI. To support scalability, we investigate system models and mechanisms in which the transaction management functions are decoupled from the storage system and integrated with the application-level processes. We present two system models and demonstrate their scalability under the scale-out paradigm of Cloud computing platforms. In the first system model, all transaction management functions are executed in a fully decentralized manner by the application processes. The second model is based on a hybrid approach in which the conflict detection techniques are implemented by a dedicated service. We perform a comparative evaluation of these models using the TPC-C benchmark and demonstrate their scalability.

We propose a Snapshot Isolation based transaction execution and consistency model, referred to as causally coordinated snapshot isolation, for geographically replicated data. The data replication is managed through asynchronous update propagation. Our approach provides snapshot-isolation model over multiple sites and ensures causal ordering of transactions. We present here an efficient protocol for precisely capturing the causal data dependencies of transactions and ensuring the causal ordering based on these dependencies when applying transactions' updates at remote sites. Through experimental evaluations, we demonstrate the benefit of this protocol over an alternative approach for providing causal consistency for georeplicated data. We further extend this model to support session consistency guarantees such as read-your-writes and monotonic reads. Additionally, we provide a notion of group-session where a group of users are involved in a collaborative session. We provide various group-session consistency guarantees for users collaborating in a group. We present the mechanisms for providing these session consistency guarantees and evaluate their performance.

We present a programming framework based on the paradigm of generative application development for building context-aware collaborative applications. In this approach, context-aware applications are implemented using a domain-specific design model, and their execution environment is generated and maintained by the middleware. The key features of this design model include support for context-based service discovery and binding, context-based access control, context-based multiuser coordination, and context-triggered automated task executions. The middleware uses the technique of policy-based specialization for generating application-specific middleware components from the generic middleware components. Through a case-study example, we demonstrate this approach and present the evaluations of the design model and the middleware.

We present here mechanisms and models for building autonomically scalable and resilient services on wide-area shared computing platforms in which resources at a node are allocated to competing users on fair-share basis. There is no platform-wide resource manager for the placement of users on different nodes. Building scalable services in such environments poses unique challenges due to fluctuations in the available resource capacities and node crashes. The service load may surge in a short time due to flash crowds. We present here models for estimating the service capacity under varying operating conditions. Autonomic scaling of service capacity is performed by dynamic control of the degree of service replication based on the estimated service capacity and the observed load. Furthermore adaptive load distribution mechanisms are needed because of the varying service capacities of the individual replicas. We present the results of our evaluations of these mechanisms on Planet Lab.

In order to utilize the semantics of object methods to ensure cached object consistency, method group commutativity specifies the conditions under which a group of methods will commute. Method group commutativity is determined using a semantic specification of object methods, provided in terms of logical expressions, to create commutativity conjectures that are analyzed using the PVS theorem prover. This analysis results in the creation of a method commutativity specification (MCS), which is used by a distributed caching system to ensure the consistency of method invocations. For greater commutativity, weaker consistency requirements can be specified in the MCS. This base approach is enhanced by optimizations that consider a client's sequential execution of methods and that reduce the amount of data cached by the client. The effectiveness of method group commutativity and associated optimizations is evaluated using Java RMI application benchmarks.

In this paper, we present a forward recovery model for programming robust context-aware applications. The mechanisms devised as part of this model fall into two categories: asynchronous event handling and synchronous exception handling. These mechanisms enable designing recovery actions to handle different kinds of failure conditions arising in context-aware applications. These include service discovery failures, service binding failures, exceptions raised by a service, and context invalidations. This model is integrated in the high-level programming framework that we have designed for building context-aware collaborative (CSCW) applications. In this paper, we demonstrate the capabilities of this model for programming various kinds of recovery patterns in context-aware applications.

In this paper, multiuser collaboration systems are categorized into two groups-computer-supported cooperative work (CSCW) and workflow systems-based on a historic perspective of their introduction and on their emphasis on user- or process-centric interactions. The goal of the survey is to identify distinct security requirements-related to availability, integrity, confidentiality and privacy, and access leakage-of these systems. Existing role-based security models and their limitations to express security policies in distributed CSCW and workflow systems are presented. Last, we present an overview of a framework that we have developed to specify, verify, and enforce security policies in distributed CSCW systems.

In this paper we present the design and evaluation of a system for deploying highly available and migratable services in shared infrastructures, such as the PlanetLab, where the available resource capacities at a node can fluctuate significantly. A migratable service can monitor its operating conditions and autonomously relocate itself to another node when the available resource capacities at the current node fall below certain acceptable limits. We utilize the autonomous mobile agent paradigm for building such migratable services. Such agents can monitor their operating conditions and follow various migration policies. We investigate here the mechanisms for service relocation, and client-side protocols to access migratory services. The "blackout periods'', i.e. the time during which the clients are unable to access a migrating service, need to be minimized and kept within some tolerable limits for services required to be highly available. We first present the design of a migratable service implemented using a mobile agent, and evaluate its performance in terms of the blackout periods and the service agent's abilities to autonomously migrate in the network. We replicate service agents to reduce the blackout periods, and develop the coordination protocols for autonomous agent migration in a group of service agents. We also present here our work for monitoring PlanetLab nodes for their available resource capacities in order to assist a migratory service in selecting a target node for relocation.

In this paper we present a context-aware RBAC (CARBAC) model for pervasive computing applications. The design of this model has been guided by the context-based access control requirements of such applications. These requirements are related to users' memberships in roles, permission executions by role members, and context-based dynamic integration of services in the environment with an application. Context information is used in role admission policies, in policies related to permission executions by role members, and in policies related to accessing of dynamically interfaced services by role members. The dynamic nature of context information requires model-level support for revocations of role memberships and permission activations when certain context conditions fail to hold. Based on this model we present a programming framework for building context-aware applications, providing mechanisms for specifying and enforcing context-based access control requirements.

We identify here various kinds of failure conditions and robustness issues that arise in context-aware pervasive computing applications. Such conditions are related to failures in an application's interactions with ambient services, failures in resource discovery and binding, and invalidation of context conditions during the execution of an application task. In this paper we present an exception handling model for integrating forward error recovery mechanisms in the designs of such applications. This model is integrated in a role-based framework and supported by a programming environment for construction of such applications.

Abstract Remote Method Invocation (RMI), a mechanism to access remote objects in Java‐based distributed applications, uses network communication for each method invocation. Consequently, using RMI in a wide‐area environment can cause poor application performance. One solution to improve performance is to cache the objects such that network communication is not necessary for each method invocation. In this paper, we present mechanisms to transparently add object caching to RMI. These mechanisms are compatible with existing RMI applications and use an event‐based model to support different consistency policies. The mechanisms also include the ability to adaptively select the consistency policy for an object based on its usage pattern. A novel feature of our mechanisms is the use of a ‘reduced object’, which is a partial representation of the RMI object. We experimentally evaluate and demonstrate the benefits of our mechanisms. Copyright © 2006 John Wiley & Sons, Ltd.

Abstract In this paper we present a framework for building policy‐based autonomic distributed agent systems. The autonomic mechanisms of configuration and recovery are supported through a distributed event processing model and a set of policy enforcement mechanisms embedded in an agent framework. Policies are event‐driven rules derived from the system's functional and non‐functional requirements. Agents in the network monitor the system state for policy violation conditions, generate appropriate events, and communicate them to other agents for cooperative filtering, aggregation, and handling. A set of agents perform policy enforcement actions whenever events signifying any policy violation conditions occur. Policies are defined using a specification framework based on XML. The policy enforcement agents interpret the policies given in XML. We illustrate the utility of this framework in the context of an agent‐based distributed network monitoring application. We also present an experimental evaluation of our approach. Copyright © 2006 John Wiley & Sons, Ltd.

We present, in this paper, a role-based model for programming distributed CSCW systems. This model supports specification of dynamic security and coordination requirements in such systems. We also present here a model-checking methodology for verifying the security properties of a design expressed in this model. The verification methodology presented here is used to ensure correctness and consistency of a design specification. It is also used to ensure that sensitive security requirements cannot be violated when policy enforcement functions are distributed among the participants. Several aspect-specific verification models are developed to check security properties, such as task-flow constraints, information flow, confidentiality, and assignment of administrative privileges.

This work presents an abstraction called guardian for exception handling in distributed and concurrent systems that use coordinated exception handling. This model addresses two fundamental problems with distributed exception handling in a group of asynchronous processes. The first is to perform recovery when multiple exceptions are concurrently signaled. The second is to determine the correct context in which a process should execute its exception handling actions. Several schemes have been proposed in the past to address these problems. These are based on structuring a distributed program as atomic actions based on conversations or transactions and resolving multiple concurrent exceptions into a single one. The guardian in a distributed program represents the abstraction of a global exception handler, which encapsulates rules for handling concurrent exceptions and directing each process to the semantically correct context for executing its recovery actions. Its programming primitives and the underlying distributed execution model are presented here. In contrast to the existing approaches, this model is more basic and can be used to implement or enhance the existing schemes. Using several examples we illustrate the capabilities of this model. Finally, its advantages and limitations are discussed in contrast to existing approaches.

The focus of this paper is on a specification model for defining security and coordination policies for distributed collaboration and workflow systems. This work is motivated by the objective to build distributed collaboration systems from their high level specifications. We identify here unique requirements for secure collaboration, specifically role admission and activation constraints, separation of duties, dynamic access control, and a model for multiuser participation in a role. We present a role-based model for specifying coordination and dynamic security requirements in collaboration systems. It also supports hierarchical structuring of a large collaboration environment using the concept of activities, which define a naming scope and a protection domain to specify security and coordination policies. We have implemented this specification model in XML and used it to construct the runtime environments for distributed collaboration systems using a policy based middleware.

In this paper, we present static verification of security requirements for CSCW systems using finite-state techniques, i.e., model checking. The coordination and security constraints of CSCW systems are specified using a role based collaboration model. The verification ensures completeness and consistency of the specification given global requirements. We have developed several verification models to check security properties, such as task-flow constraints, information flow or confidentiality, and assignment of administrative privileges. The primary contribution of this paper is a methodology for verification of security requirements during designing collaboration systems.

We present the execution model of policy-driven middleware for building secure distributed collaboration systems from their high level specifications. Our specification model supports nested collaboration activities, and uses role-based security policies and event count based coordination specification. From the specifications of a collaboration environment, appropriate policy modules are derived for enforcing security and coordination requirements. Policy-driven distributed middleware provides services to users to join roles in an activity, perform role specific operations, or create new activities. We describe the design challenges for middleware and present the run-time structures and protocols supported by it for creating activities, roles, and objects.

We present here a framework together with a set of paradigms for mobile agent based active monitoring of network systems. In our framework mobile agents are used to perform remote information filtering and control functions. Such agents can detect basic events or correlate existing events that are stored in a database to enforce system policies. A system administrator can securely modify the monitoring policies and information filtering functions of its agents, or install new agents at a node. The framework presented here includes monitor, subscriber, auditor and inspector agents. The policies and itineraries of these agents can be modified dynamically. In response to certain trigger events agents may change their itineraries to correlate event data. We present here a set of experiments that we have conducted using the Ajanta mobile agent system to evaluate and demonstrate the capabilities of our mobile agent framework.

We present an abstraction called guardian for exception handling in distributed systems. The guardian can solve several limitations with existing distributed exception handling techniques. To understand these limitations, we analyze distributed exception handling with respect to sequential exception handling and identify the significant differences between them. This leads to the fundamental problem with distributed exception handling, which is invoking the semantically correct exception handlers in all the distributed processes that are required to participate in the recovery. The guardian model addresses this problem. It introduces a set of programming primitives and a global exception handler. Finally, using a primary-backup example we illustrate how the guardian model is used for global exception handling in a distributed system.

Abstract A mobile agent is an object which can autonomously migrate in a distributed system to perform tasks on behalf of its creator. Security issues in regard to the protection of host resources, as well as the agent themselves, raise significant obstacles in practical applications of the agent paradigm. This article describes the security architecture of Ajanta, a Java‐based system for mobile agent programming. This architecture provides mechanisms to protect server resources from malicious agents, agent data from tampering by malicious servers and communication channels during its travel, and protection of name service data and the global namespace. We present here a proxy based mechanism for secure access to server resources by agents. Using Java's class loader model and thread group mechanism, isolated execution domains are created for agents at a server. An agent can contain three kinds of protected objects: read‐only objects whose tampering can be detected, encrypted objects for specific servers, and a secure append‐only log of objects. A generic authentication protocol is used for all client–server interactions when protection is required. Using this mechanism, the security model of Ajanta enforces protection of namespaces, and secure execution of control primitives such as agent recall or abort. Ajanta also supports communication between agents using RMI, which can be controlled if required by the servers' security policies. Copyright © 2001 John Wiley & Sons, Ltd.

A mobile agent represents a computation that can autonomously migrate in a network to perform tasks on behalf of its creator. This paper describes the security architecture of Ajanta, a Java-based system for mobile agent programming. This architecture provides mechanisms to protect server resources from malicious agents, agent data from tampering by malicious servers, and to protect the system infrastructure itself. An agent can carry three kinds of protected data: read-only objects, objects visible only to specific servers, and a secure append-only list of objects. Agents' access to server resources is controlled using a proxy-based mechanism. A generic authentication protocol is used for all sensitive client-server interactions. Ajanta also supports communication between remote agents using RMI, which can be controlled by the servers' security policies.

THE importance of exception handling is well-recognized by system designers and software engineers. Exception handing is very often the most important part of the system because it deals with abnormal situations. The goal of

1 THE ARTICLES THE second part of this special issue on Current Trends in Exception Handling includes four papers which primarily deal with exception handling in human-centered systems such as workflow, requirements specification, and new interactive programming models such as spreadsheets. These research contributions demonstrate that exceptions are not restricted to programming languages, but occur in many, if not most, real-world situations. These papers also reflect that exceptions can be deviations from normal conditions and may not necessarily imply errors. This is similar to Goodenough's observations in his classic paper in the 1970s [1]. These papers lead us to observe that anything that has an algorithmic flow, whether it be workflow or a design process or a program, has a pervasive exception handling need. Programming may be the ultimate in an algorithm, so many of the problems encountered there have analogies in other areas. Moreover, the computation model presented by programming languages tends to be relatively more simple in regard to handling of exceptions in contrast to dealing with such problems in large-scale systems such as enterprise-wide workflow. In those environments, it is not simply exception handling language constructs that are needed, but a methodology on how to use exception handling. The programming model of spreadsheet systems raises many unique issues related to exception handling. This is a widely used model of programming by end users through the use of many commercial products. In the paper aException Handling in the Spreadsheet Paradigm,o Margaret Burnett, Anurag Agrawal, and Pieter van Zee discuss these issues and present an approach for handling exceptions in this programming paradigm. Many spreadsheet programs can be quite large and complex and, therefore, both reliability as well maintainability of such programs becomes an issue when exception handling is introduced. The authors present their experience with and analysis of the error value models for spreadsheet programs. Achieving a high level of fault tolerance is one of the main concerns in developing modern workflow systems due to many factors: Distributed environment, long duration of activities, and complexity of the software involved are among them. The paper aException Handling in Workflow Management Systemso by Clause Hagen and Gustavo Alonso describes an advanced fault tolerance mechanism for incorporating both transactions and exception handling into such systems. The approach is unique for workflow systems as it treats workflow support as a programming environment and relies on general research on developing fault-tolerant software. The authors use fundamental research on linguistic issues of exception handling and propose simple ways of applying these concepts to transactional workflow management. The modeling language incorporates special features for error detection and handling which are conceptually similar to exception handling features found in programming languages. Another important way in which this approach is new is how it combines transaction atomicity and exception handling. A validation technique is developed to make it possible to assess the correctness of workflow specification in situations when exceptions are raised and handled. In the paper aHandling of Irregularities in Human Centered Systems: A Unified Framework for Data Processes,o Takahiro Murata and Alex Borgida address exception handling problems in human-centered systems. In such systems, exception handling is required for dealing with errors, as well as deviations, in data as well as processes, from their normal constraints. The paper focuses on exception handling in enterprise workflow systems. Generally, in enterprise systems, process models are used for describing the dynamic nature of activities of humans and semi-automated system entities. Most often, such models do not capture many unanticipated deviations. Sometimes such deviations have to be corrected and other times they are to be tolerated. This paper presents a unified model for handling errors and deviations, which are treated as exception conditions resulting from violations of some specified constraints. When permitting deviations to persist, it relies on runtime checks for assessing their consequences. Axel van Lamsweerde and Emmanuel Letier address the issues of aHandling Obstacles in Goal-Oriented Requirements Engineering.o The requirements elicitation process often results in goals, requirements, and assumptions about the desired system that are too idealized and that do not take into account the various kinds of problems that can occur. Not anticipating exceptional behaviors results in unrealistic, unachievable, or incomplete requirements specifications. This, in turn, leads to systems that are not robust enough and which may fail at critical times, perhaps with critical consequences. The authors present formal techniques for IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 26, NO. 10, OCTOBER 2000 921

The paper gives an overview of Ajanta, a Java based system for mobile agent programming. We outline the Ajanta architecture, and discuss the basic elements that comprise an agent based application. Ajanta's programming environment is defined in terms of a set of primitive operations for agent creation, dispatch, migration and remote control. Agents can access server resources using a proxy based access control mechanism. We describe a scheme for agent migration based on the composition of some basic migration patterns which incorporate exception handling mechanisms. Finally, we present two agent based distributed applications implemented using the Ajanta system. One is a middleware which supports file sharing over the Internet and the other is a distributed calendar manager.

This paper describes the design of an RPC system for building object-oriented distributed software systems. The general requirements for such a system are to provide mechanisms for supporting inheritance, polymorphism, dynamic binding, and modular development in implementing distributed software systems. This paper presents the functionalities of this RPC system to support these general requirements. It also briefly describes the experiences with two previous versions of this system and how they led to the design of the final system. This system was implemented as a part of the programming environment of the Nexus distributed operating system. © 1998 John Wiley & Sons, Ltd.

The performance of a local adaptive protocol for distributed discrete event simulation is evaluated. This protocol allows each process to adapt at runtime to its environment on a per channel basis with the possible range of behavior varying from conservative to optimistic. This evaluation includes a comparison of the performance of the algorithm with that of both a conservative and an optimistic protocol, as well as, an examination of a number of unique characteristics of the algorithm. Results from simulations using a network of workstations on a closed queueing system are presented. The results demonstrate the importance of various protocol features and show that it performs better than either the conservative or optimistic protocols in certain simulations.

Abstract The paper describes the approach taken for configuration management in the Nexus distributed operating system. Nexus uses kernel‐level support for monitoring the failure or termination status of distributed components of an application. Periodic user‐level messages are not required for status monitoring. Group and dependency relationships between such components can be defined by the programmer for the purpose of configuration monitoring and management. An object belonging to a distributed application can be monitored by its host kernel for system‐defined exception conditions. When any of these conditions arise, other objects are notified through signals or messages, as specified by the programmer.

Undertakes a comparative study of two important interconnection network topologies: the star graph and the hypercube, from the graph theory point of view. Topological properties are derived for the star graph and are compared with the corresponding properties of the hypercube. Among other results, the authors determine necessary and sufficient conditions for shortest path routing and characterize maximum-sized families of parallel paths between any two nodes of the star graph. These parallel paths are proven of minimum length within a small additive constant. They also define greedy and asymptotically balanced spanning trees to support broadcasting and personalized communication on the star graph. These results confirm the already claimed topological superiority of the star graph over the hypercube.>

This paper describes the approach taken for configuration management in the Nexus distributed operating system. Nexus uses kernel-level support for monitoring status of distributed components of an application. Periodic user-level messages are no longer required for status monitoring. Group and dependency relationships between such components can be defined by the programmer for the purpose of configuration monitoring and management. An object belonging to a distributed application can be monitored by its host kernel for some system-defined exception conditions. When any of these conditions arise, other objects are notified through signals or messages, as specified by the programmer.>

The use of a new topology, called the arrangement graph, as a viable interconnection scheme for parallel and distributed systems, has been recently proposed and examined. The arrangement graphs represent a rich class of generalized star graphs with many attractive properties, In this paper we obtain (1) unit expansion embeddings of a variety of multi-dimensional grids, (2) dilation 1, 2, 3, and 4 embeddings of hypercubes and (3) hierarchical and greedy spanning trees to support broadcasting and personalized communication in arrangement graphs.

Arrangement graphs have been proposed as an attractive interconnection topology for large multiprocessor systems. The authors study these graphs by proving the existence of Hamiltonian cycles in any arrangement graph. They also prove that an arrangement graph contains cycles of all lengths ranging between 3 and the size of the graph. They show that an arrangement graph can be decomposed into node disjoint cycles in many different ways.>

The concepts of the PMC and BGM self-diagnosing system models of F. P. Preparata et al. (1967) and F. Barsi et al. (1976), respectively, including the notions of fault sets, consistency, and diagnosability number, are reviewed. Two one-step diagnosability algorithms are applied, one to the PMC model and the other to the BGM model. In both models, one-step diagnosability refers to a system's ability to determine all the faulty units from single collection of test results. Using the letters n, m, and tau to denote the number of units, the number of tests, and the diagnosability number, respectively, it is shown that in the BGM model the algorithm has a complexity of O(n tau /sup 2//log tau ), and, in the PMC model, the algorithm has a complexity of O(n tau /sup 2.5/).>

F.P. Preparata et al. (1967) introduced a graph-theoretical model for fault diagnosis called the PMC model. The question of determining the sequential diagnosability number of a system in the PMC model has remained open. The authors formalize the notion of sequential diagnosability. The question of determining the sequential diagnosability number of a system is addressed by showing that the appropriate decision problem is co-NP complete. The problem is also shown to be co-NP complete even when restricted to planar graphs both in the weighted and the BGM models.>

Abstract The concept of atomic actions has been a useful and powerful abstraction in designing concurrent and fault‐tolerant systems. Nested atomic actions are used in hierarchically structured systems where an atomic action may itself be composed of other atomic actions. This paper presents a semaphore‐based protocol for synchronizing a set of concurrently executing nested atomic actions. The approach followed consists of first designing a protocol for synchronizing non‐nested actions, and then extending it to the nested case. The paper also details the difficulties involved in integrating deadlock resolution algorithms into the synchronization protocol. Both deadlock‐prevention and deadlock‐detection schemes for handling deadlocks are discussed.

Abstract SINA is an object‐oriented language for distributed and concurrent programming. The primary focus of this paper is on the object‐oriented concurrent programming mechanisms of SINA and their implementation. This paper presents the SINA constructs for concurrent programming and inter‐object communication, some illustrative examples and a message‐based implementation model for SINA that we have used in our current implementation.

Nexus is a distributed operating system designed to support experimental research in fault-tolerance techniques and object-oriented programming in distributed systems. The Nexus programming environment consists of objects, which are instances of abstract data types. Inheritance of types and multiple implementations for a type are supported by the system. Operations on objects are invoked, based on the remote-procedure-call paradigm and executed as atomic actions with provisions for application-controlled checkpointing and restart within actions. Nexus also supports parallel remote procedure calls. Interobject communication and location transparency in accessing objects is supported by the Nexus kernel.>

Nexus is an object-oriented distributed operating system for local-area networks of heterogeneous workstations. The authors present the salient features of the Nexus design and its type management system. The Nexus design explicitly provides mechanisms for type inheritance and for simultaneously supporting different versions for a given abstract type in the network. A functional view of the type management system is considered.>

This paper describes a new data abstraction mechanism in an object-oriented model of computing. The data abstraction mechanism described here has been devised in the context of the design of Sina/st language. In Sina/st no language constructs have been adopted for specifying inheritance or delegation, but rather, we introduce simpler mechanisms that can support a wide range of code sharing strategies without selecting one among them as a language feature. Sina/st also provides a stronger data encapsulation than most of the existing object-oriented languages. This language has been implemented on the SUN 3 workstation using Smalltalk.

This paper presents a formal scheme for addressing base and apex nodes in SW-banyan networks. This scheme is used for routing packets in the network. Packet-switching, in conjunction with the the circuit-switch mode of operation, offers a very flexible and powerful mechanism for interprocess communication in the multiprocessor architectures based on the banyan networks. Finally, a fault-tolerent scheme for re-routing the packets in the network is presented, in case the packet encounters a faulty node in its path.