The iTrust system is a decentralized and distributed publication, search and retrieval system that makes it difficult to censor or filter information accessed over the Internet. iTrust employs a completely distributed membership algorithm, and a detection and defensive adaptation algorithm that protects against malicious nodes in the membership. These algorithms depend on information that cannot be observed or measured directly, the current size of the membership and the current proportion of malicious nodes in the membership. They use statistical estimation to approximate these network environment parameters, and then they dynamically adapt accordingly. These algorithms provide accurate and timely management of the iTrust system in the presence of membership churn and malicious nodes.

Web Services allow an enterprise to focus on its own business expertise and to employ information technology services offered by others, however, doing so exposes the enterprise to the risk of loss of service or data, if the service provider fails. The use of multiple service providers reduces the risk of failure, but it introduces the complication of incompatible service interfaces, data formats, and stored data. In this paper, we propose a conversion infrastructure that facilitates the use of multiple alternative Web Services at different service providers, to achieve high availability, even in the event of a failure or a catastrophe.

In this paper, we present a novel algorithm that finds the probability density function for the number of distinct nodes reached, within a specific number of levels of message forwarding, for a fixed size network. The algorithm also finds the expected number of distinct nodes to which a message is forwarded, within a specific number of levels of message forwarding, as the sum of the number of nodes, weighted by the probability of reaching that number of nodes. In addition, the algorithm finds the probability density function for the number of distinct nodes at a given level of message forwarding, and the expected number of distinct nodes at that level. Using the algorithm, we calculate these probability density functions and expected values for various size networks, degrees of message forwarding, probabilities of message forwarding, and levels of message forwarding. The algorithm has application to the Internet, peer-to-peer networks, ad-hoc networks, and social networks, and to multicasting, gossiping, and rumor and epidemic protocols.

The low latency fault tolerance (LLFT) system provides fault tolerance for distributed applications within a local-area network, using a leader–follower replication strategy. LLFT provides application-transparent replication, with strong replica consistency, for applications that involve multiple interacting processes or threads. Its novel system model enables LLFT to maintain a single consistent infinite computation, despite faults and asynchronous communication. The LLFT messaging protocol provides reliable, totally ordered message delivery by employing a group multicast, where the message ordering is determined by the primary replica in the destination group. The leader-determined membership protocol provides reconfiguration and recovery when a replica becomes faulty and when a replica joins or leaves a group, where the membership of the group is determined by the primary replica. The virtual determinizer framework captures the ordering information at the primary replica and enforces the same ordering of non-deterministic operations at the backup replicas. LLFT does not employ a majority-based, multiple-round consensus algorithm and, thus, it can operate in the common industrial case where there is a primary replica and only one backup replica. The LLFT system achieves low latency message delivery during normal operation and low latency reconfiguration and recovery when a fault occurs.

We present a lightweight Byzantine fault tolerance (BFT) algorithm, which can be used to render the coordination of web services business activities (WS-BA) more trustworthy. The lightweight design of the BFT algorithm is the result of a comprehensive study of the threats to the WS-BA coordination services and a careful analysis of the state model of WS-BA. The lightweight BFT algorithm uses source ordering, rather than total ordering, of incoming requests to achieve Byzantine fault tolerant, state-machine replication of the WS-BA coordination services. We have implemented the lightweight BFT algorithm, and incorporated it into the open-source Kandula framework, which implements the WS-BA specification with the WS-BA-I extension. Performance evaluation results obtained from the prototype implementation confirm the efficiency and effectiveness of our lightweight BFT algorithm, compared to traditional BFT techniques.

This paper describes the iTrust over SMS decentralized search and retrieval system for mobile networks. Any mobile device in the iTrust network can communicate with any other mobile device in the iTrust network to distribute, search for, and retrieve information. Third-party developers can use the iTrust over SMS API on the Android platform to add this search and retrieval functionality to existing applications quickly and easily. Developers of applications for other mobile device platforms can use the iTrust over SMS protocol to create compatible applications that can communicate using iTrust over SMS. In addition to the iTrust over SMS components and protocol, this paper presents a performance evaluation of the iTrust over SMS system, which shows that the probability of information retrieval is high, even if some of the mobile devices are not available. It also shows that the average search latency is consistently less if all of the participating nodes use the same mobile service provider, and is consistently more if the nodes use different mobile service providers.

The Web Services Atomic Transactions (WS-AT) specification makes it possible for businesses to engage in standard distributed transaction processing over the Internet using Web Services technology. For such business applications, trustworthy coordination of WS-AT is crucial. In this paper, we explain how to render WS-AT coordination trustworthy by applying Byzantine Fault Tolerance (BFT) techniques. More specifically, we show how to protect the core services described in the WS-AT specification, namely, the Activation service, the Registration service, the Completion service and the Coordinator service, against Byzantine faults. The main contribution of this work is that it exploits the semantics of the WS-AT services to minimize the use of Byzantine Agreement (BA), instead of applying BFT techniques naively, which would be prohibitively expensive. We have incorporated our BFT protocols and mechanisms into an open-source framework that implements the WS-AT specification. The resulting BFT framework for WS-AT is useful for business applications that are based on WS-AT and that require a high degree of dependability, security, and trust.

We present a novel framework for spatial routing through difficult terrains with possibly untrustworthy regions in tactical mobile ad hoc networks. We describe a protocol, named "Reliability Map Routing" (RMR), which uses end-to-end Quality of Service metrics that include spatial reliability and trust. The RMR protocol reactively discovers routes over spatial cells whose local reliabilities are distributed throughout the network via a fast dissemination algorithm. By using a spatial approach where reliability and trust are attributed to space rather than to nodes, RMR is able to find reliable routes that persist for longer durations than those discovered by node-centric protocols. Furthermore, RMR is capable of reliable geocasting with low overhead. Via QualNet simulation studies, we compare the performance of the RMR protocol in terms of packet delivery ratio, delay, and overhead, and quantify the effects of node density, velocity, and traffic load on protocol performance. Our results indicate that the RMR protocol performs well in high mobility, high density scenarios because of its controlled routing overhead and spatial approach to routing.

The Low Latency Fault Tolerance (LLFT) middleware provides fault tolerance for distributed applications deployed within a cloud computing or data center environment, using the leader/follower replication approach. The LLFT middleware consists of a Low Latency Messaging Protocol, a Leader-Determined Membership Protocol, and a Virtual Determinizer Framework. The Messaging Protocol provides are liable, totally ordered message delivery service by employing a direct group-to-group multicast where the ordering is determined by the primary replica in the group. The Membership Protocol provides a fast reconfiguration and recovery service when a replica becomes faulty and when a replica joins or leaves a group. The Virtual Determinizer Framework captures ordering information at the primary replica and enforces the same ordering at the backup replicas for major sources of non-determinism. The LLFT middleware maintains strong replica consistency, offers application transparency, and achieves low end-to-end latency.

This paper describes a Web service that automatically parses and extracts data records from Web pages containing structured data. The Web service allows multiple users to share and manage a Web data record extraction task to increase its utility. A recommendation system, based on the probabilistic latency semantic indexing algorithm, enables a user to find potentially interesting content or other users who share the same interests with the user. A distributed computing platform improves the scalability of the Web service in supporting multiple users by employing multiple server computers. A Web service interface allows users to access the Web service, and allows programmers to develop their own applications and, thus, extend the functionality of the Web service.

With the advent of the new generation of Internet-based technology, in particular, web services, the automation of business activities that are distributed across multiple enterprises becomes possible. Business activities are different from traditional transactions in that they are typically asynchronous, loosely coupled, and long running. Therefore, extended transaction protocols are needed to coordinate business activities that span multiple enterprises. Existing extended transaction protocols typically rely on compensating transactions to handle exceptional conditions. In this paper, we identify a number of issues with compensation-based extended transaction protocols and describe a reservation-based extended transaction protocol that addresses those issues. Moreover, we define a set of properties, analogous to the ACID properties of traditional transactions that are more appropriate for business activities that span multiple enterprises. In addition, we compare our reservation protocol with other extended transaction protocols for coordinating business activities and present performance analyses and results.

Web services offer great promise for integrating and automating software applications within and between enterprises over the Internet. However, ensuring that Web services are dependable, and can satisfy their clients' requests when the clients need them is a real challenge because, typically, a business activity involves multiple Web services and a Web service involves multiple components, each of which must be dependable. In this paper, we describe fault tolerance techniques, including replication, checkpointing, and message logging, in addition to reliable messaging and transaction management for which Web services specifications exist. We discuss how those techniques can be applied to the components of the Web services involved in the business activities to render them dependable.

Traditional transaction semantics are not appropriate for business activities that involve long-running transactions in a loosely-coupled distributed environment, in particular, for Web services that operate between different enterprises over the Internet. In this paper we describe a novel reservation-based extended transaction protocol that can be used to coordinate such business activities. The protocol avoids the use of compensating transactions, which can result in undesirable effects. In our protocol, each task within a business activity is executed as two steps. The first step involves an explicit reservation of resources. The second step involves the confirmation or cancellation of the reservation. Each step is executed as a separate traditional short-running transaction. We show how our protocol can be implemented as a reservation protocol on top of the Web services transaction specification or, alternatively, as a coordination protocol on top of the Web services coordination specification.

In this paper, we describe a software infrastructure that unifies transactions and replication in three-tier architectures and provides data consistency and high availability for enterprise applications. The infrastructure uses transactions based on the CORBA object transaction service to protect the application data in databases on stable storage, using a roll-backward recovery strategy, and replication based on the fault tolerant CORBA standard to protect the middle-tier servers, using a roll-forward recovery strategy. The infrastructure replicates the middle-tier servers to protect the application business logic processing. In addition, it replicates the transaction coordinator, which renders the two-phase commit protocol nonblocking and, thus, avoids potentially long service disruptions caused by failure of the coordinator. The infrastructure handles the interactions between the replicated middle-tier servers and the database servers through replicated gateways that prevent duplicate requests from reaching the database servers. It implements automatic client-side failover mechanisms, which guarantee that clients know the outcome of the requests that they have made, and retries aborted transactions automatically on behalf of the clients.

This paper discusses progress in the field of real-time fault tolerance. In particular, it considers synchronous vs. asynchronous fault tolerance designs, maintaining replica consistency, alternative fault tolerance strategies, including checkpoint restoration, transactions, and consistent replay, and custom vs. generic fault tolerance.

This paper describes a system that enables the failover of a TCP server endpoint in a manner that is transparent to the clients and to the server applications. The failover can occur at any time during the lifetime of a connection. The failover is achieved by modifying the server’s TCP/IP stack. No modifications are required to the client’s TCP/IP stack, the client application or the server application. The system supports active or semi-active replication of the server. 1.

Clock-related operations are one of the many sources of replica non-determinism and of replica inconsistency in fault-tolerant distributed systems. In passive replication, if the primary server crashes, the next clock value returned by the new primary server might have actually rolled back in time, which can lead to undesirable consequences for the replicated application. The same problem can happen for active replication where the result of the first replica to respond is taken as the next clock value. In this paper, we describe the design and implementation of a consistent time service for fault-tolerant distributed systems. The consistent time service introduces a group clock that is consistent across the replicas and that ensures the determinism of the replicas with respect to clock-related operations. The group clock is monotonically increasing, is transparent to the application and is fault-tolerant. The consistent time service guarantees the consistency of the group clock even when faults occur, when new replicas are added into the group and when failed replicas recover. 1

Unreliable fault detectors can be defined in terms of completeness and accuracy properties and can be used to solve the consensus problem in asynchronous distributed systems that are subject to crash faults. We extend this result to asynchronous distributed systems that are subject to Byzantine faults. First, we define and categorize Byzantine faults. We then define two new completeness properties, eventual strong completeness and eventual weak completeness. We use these completeness properties and previously defined accuracy properties to define four new classes of unreliable Byzantine fault detectors. Next, we present an algorithm that uses a Byzantine fault detector to solve the consensus problem in an asynchronous distributed system of $n$ processes in which the number $k$ of Byzantine faults satisfies $k\leq \lfloor (n-1)/3\rfloor$. We also give algorithms that implement a Byzantine fault detector in a model of partial synchrony. Finally, we prove the correctness of the consensus algorithm and analyze its complexity.

Significant efforts are now underway to develop middleware standards, within the Object Management Group (OMG), the Java Community Process and the Service Availability Forum, for the online upgrading of application software while that software continues to provide service. We highlight the main features of the proposed OMG online upgrade specification. We also present several online upgrade scenarios and give an example use case of the online upgrade specification.

Critical components of a distributed system must be replicated to achieve high availability, and fault tolerance. Current fault tolerant CORBA infrastructures have concentrated on mechanisms for object replication and recovery, while rarely considering practical issues related to the context, i.e., the CORBA middleware within the process in which the object runs. Our study shows that to replicate and recover complex CORBA applications, the behavior of the process that hosts the CORBA objects, in particular the bootstrapping of an application, must be taken into account. In this paper, we discuss the challenges that arose when bootstrapping CORBA applications in some common scenarios, and we provide strategies to handle such difficulties so that CORBA applications can be rendered fault-tolerant.

The Eternal system pioneered the interception approach to providing transparent fault tolerance for CORBA, which allows it to make a CORBA application reliable with little or no modification to the application or the ORB. The design and implementation of the Eternal system has influenced industrial practices by providing the basis for the specifications of the fault-tolerant CORBA standard that the Object Management Group adopted. We discuss our experience in developing the Eternal system, with particular emphasis on the challenges that we encountered and the lessons that we learned.

Group communication protocols greatly simplify the design of fault-tolerant distributed systems. Most of those protocols focus on node redundancy rather than on network redundancy. The totem redundant ring protocol allows the use of multiple redundant local-area networks. The partial or total failure of a network remains transparent to the application processes. The distributed system remains operational while an administrator reacts to an alarm raised by the totem redundant ring protocol. The user can choose between active, passive and active-passive replication of the network.

In this paper we describe a software infrastructure that unifies replication and transaction processing in three-tier architectures and, thus, provides high availability and fault tolerance for enterprise applications. The infrastructure is based on the Fault Tolerant CORBA and CORBA Object Transaction Service standards, and works with commercial-off-the-shelf application servers and database systems. The infrastructure replicates the application servers to protect the business logic processing. In addition, it replicates the transaction coordinator which renders the two-phase commit protocol non-blocking and, thus, avoids potentially long service disruptions caused by coordinator failure. The infrastructure handles the interactions between the application servers and the database servers through replicated gateways that prevent duplicate requests from reaching the database servers. The infrastructure implements client-side automatic failover mechanisms, which guarantees that clients know the outcome of the requests that they have made. The infrastructure starts the transactions at the application servers, and retries aborted transactions, caused by process or communication failures, automatically on the behalf of the clients.

Abstract Enterprises are increasingly involved in worldwide round‐the‐clock e‐commerce and e‐business, which requires them to be operational 24 hours per day, 7 days per week. With outages leading to loss of revenue, reputation and customers, fault tolerance becomes increasingly important. By mixing the fault tolerance logic into the application logic, existing fault tolerance practices render applications more complex, more prone to errors, and more difficult to maintain and build. The Eternal system is a component‐based middleware framework that provides transparent fault tolerance for enterprise applications, and that ensures continuous$24\times7$ operation without requiring special skills of the application programmers. The Eternal system implements the new Fault‐Tolerant CORBA standard. Copyright © 2002 John Wiley & Sons, Ltd.

The ability to perform live software upgrades is essential for long-running applications that provide critical services. Program modifications are necessary as programmer errors and new user requirements are uncovered. If software is to remain relevant, it must be upgradable. The Eternal Evolution Manager allows distributed CORBA applications to be upgraded while they continue to provide service. In addition to avoiding planned downtime, the Evolution Manager accomplishes the difficult tasks inherent to software evolution with minimal help from the application programmer. With our live upgrade techniques, and the underlying fault tolerance of the Eternal System, we can allow applications to run forever.

The Eternal system provides transparent fault tolerance for CORBA applications, without requiring the modification of either the application or the ORB. Eternal replicates the application objects, and ensures strong replica consistency by employing reliable totally-ordered multicast messages for conveying the IIOP messages of the application. To maintain replica consistency even as replicas fail and are recovered, Eternal ensures the retrieval, assignment and transfer of the three kinds of state, application-level, ORB/POA-level and infrastructure-level state, that are associated with each replicated object. Eternal's mechanisms for recovery include the synchronization of the the state retrieval and the state assignment messages, as well as the logging and replay of messages and checkpoints.

An ad hoc mobile network is a collection of nodes, each of which communicates over wireless channels and is capable of movement. Wireless nodes have the unique capability of transmission at different power levels. As the transmission power is varied, a tradeoff exists between the number of hops from source to destination and the overall bandwidth available to individual nodes. Because both battery life and channel bandwidth are limited resources in mobile networks, it is important to ascertain the effects different transmission powers have on the overall performance of the network. This paper explores the nature of this transmission power tradeoff in mobile networks to determine the optimum node density for delivering the maximum number of data packets. It is shown that there does not exist a global optimum density, but rather that, to achieve this maximum, the node density should increase as the rate of node movement increases.

Complex distributed object systems require dynamic migration algorithms that allocate and reallocate objects to respond to changes in the load or in the availability of the resources. We present the Cooling and Hot-Spot migration algorithms that reallocate objects when the load on a processor is high or when the latency of a task is high. The algorithms have been implemented as a feedback loop in the Eternal Resource Management System where information obtained from monitoring the behavior of the objects and the usage of the processors' resources is used to dynamically balance the load on the processors and improve the latency of the tasks. The cost of moving an object is justified by amortization over many method invocations, and constrains the rate at which objects are moved. The experimental results show that our algorithms guarantee steady flow of operation for the tasks and gracefully migrate objects from the processors when processor overloads and high task latencies are detected.

In a distributed system, software modification to correct programmer errors and to enhance functionality is often necessary, but incurring the downtime required to perform software upgrades can be prohibitively expensive or logistically infeasible. The Eternal Evolution Manager addresses this problem by enabling CORBA applications to be upgraded while they continue to provide service. The off-line analysis in preparation for the live upgrade is largely automatic, and the upgrade itself is fully automatic. The Eternal Evolution Manager insulates the application programmer from the difficult problems inherent to software evolution.

In this paper we describe an infrastructure that provides increased reliability for three-tier applications, transparently, using commercial off-the-shelf application servers and database systems. In this infrastructure the application servers are actively replicated to protect the business logic processing. Replicating the transaction coordinator renders the two-phase commit protocol non-blocking and, thus, avoids potentially long service disruptions caused by coordinator failure. A thin interpositioning library provides client-side automatic failover, so that clients know the outcome of their requests. The interaction between the application servers and the database servers is handled through replicated gateways that prevent duplicate requests from reaching the database servers. Aborted transactions, caused by process or communication faults, are automatically retried on the client's behalf.

Abstract Multicast group communication is needed for fault‐tolerant distributed systems and, in particular, for the new Fault Tolerant CORBA standard, to maintain strong replica consistency. However, different multicast group communication protocols are appropriate for different environments, which makes it difficult to define a single standard multicast protocol. In this paper, we present a multicast group communication engine and bridge for CORBA that allows multiple group communication protocols to be used concurrently. We also present the Fault Tolerant Multicast Protocol, a group communication protocol that allows different fault tolerance systems to interoperate. The group communication engine and bridge places Lamport timestamps on messages, and multicasts messages to groups, using one or more group communication protocols. The group communication protocols reliably deliver the timestamped messages in timestamp order to the group communication engine, which integrates these streams of messages into a single stream for delivery in timestamp order. The Fault Tolerant Multicast Protocol operates over IP Multicast, and consists of the Reliable Multicast Protocol which provides reliable source‐ordered message delivery, the Reliable Ordered Multicast Protocol which provides reliable totally ordered message delivery, and the Host Group Membership Protocol which provides host group membership services. Copyright © 2001 John Wiley & Sons, Ltd.

Abstract An interceptor is a software mechanism that provides the hooks that are needed to introduce additional code dynamically into the execution path of an application. By exploiting interceptors, developers can enhance and potentially modify the behavior of an application at runtime without having to revise or recompile the application code. We have identified three distinct interception points for the Java Remote Method Invocation (JavaRMI) model, at the proxy level, the transport level and the shared library level of the JavaRMI model. The interceptors implemented at these interception points employ the DynamicProxy API, the RMISocketFactory API, and a library mediation approach, respectively. Our interceptor implementations are novel in that they are transparent to the application, add nominal latency overheads and are easy to deploy, requiring only minimal modifications to the application. We describe how the interceptors can be exploited to introduce additional services (such as logging and profiling mechanisms) to the JavaRMI runtime. In particular, we describe the use of interceptors in the Aroma System to enhance the existing JavaRMI model with support for fault‐tolerance through the consistent replication of JavaRMI objects. Copyright © 2001 John Wiley & Sons, Ltd.

Secure reliable group communication protocols can facilitate the development of survivable distributed systems that are able to remain correct and reliable despite intrusions that cause some nodes to behave in an arbitrary or malicious manner. However, the development of such protocols is itself difficult, and prior systems have exhibited high overheads, primarily due to the cost of digital signatures. The SecureRing group communication system provides secure, reliable, totally-ordered message delivery and group membership services despite the malicious corruption of a constant fraction of the processors within the system. The network is assumed not to partition, and persistent communication faults are handled as processor faults. The SecureRing message delivery protocol makes use of message digests in a signed token to allow a single digital signature to cover multiple messages, and to avoid the need for multiple rounds of message exchange in normal operation. While these techniques mean that messages are not authenticated in real time, they enable the SecureRing protocols to achieve high throughput and reasonable latency.

The Totem single-ring protocol provides reliable totally ordered multicasting of messages to processes in process groups over a single local-area network (LAN) using a logical token-passing ring. The protocol provides two levels of message delivery: delivery in agreed order and delivery in safe order. This paper presents the probability density functions (PDFs) for the latency to message delivery for the Totem single-ring protocol for these two levels of service in the presence of both message loss and token loss. These PDFs are calculated by repeated convolutions of the PDFs for the various components of the latency. The analysis shows that the mean latency to safe delivery is greater than the mean latency to agreed delivery and that the tail of the latency distribution for safe delivery is longer. It also shows that a deterministic arrival process for message generation exhibits lower mean latencies and shorter tails of the latency distribution than a Poisson arrival process.

Reliable many-to-many multicasting of messages is an integral part of group communication systems. Such systems typically employ a reliable multicast protocol that operates below the causal or total ordering layer of the protocol stack. In this paper, we present ARMP, a reliable many-to-many multicast protocol for group communication over wide-area ATM networks. We describe how the ATM environment affects the design of ARMP, which differs significantly from the design of reliable multicast protocols intended for other environments.

Distributed real-time applications require flexible and dynamic scheduling mechanisms to provide timeliness guarantees to application objects. In this paper we present a new scheduling algorithm that exploits the task laxities and the object importance to make effective scheduling decisions. The algorithm uses current timing and resource measurements to determine the feasibility of the tasks and to distribute the objects to the processors. A task's timing parameter (laxity value) is carried, from one processor to another, with the object invocations, yielding a system-wide scheduling strategy that requires only local computations. The algorithm aims to ensure that a low importance object does nor delay the execution of a high importance task.

Distributed method invocations require dynamic scheduling algorithms and efficient resource projections to provide timeliness guarantees to application objects. In this paper, we present a dynamic scheduling algorithm that examines the computation times, real times and resource requirements of the application tasks to determine a feasible schedule for the method invocations. The schedule is driven by the laxities of the tasks and the importance that the tasks have to the system. Tasks span processor boundaries, and request messages carry scheduling parameters (laxity values) from one processor to another, yielding a system-wide scheduling algorithm that requires only local computations. Experimental results validate our scheduling algorithm, and show that it has minimal overhead.

The Eternal system supports networked enterprise applications that must operate continuously 24 hours per day, 7 days per week. Based on the CORBA standard, Eternal provides object replication not only for fault tolerance but also for live software upgrades, as well as resource management facilities. Through the use of interceptors, Eternal renders the object replication transparent to the application, as well as to the ORB and to the operating system. Thus, Eternal works with commercial off-the-shelf CORBA ORBs and standard unmodified operating systems. Eternal handles the difficult issues of object replication, fault tolerance, live upgrades and resource management, thereby allowing the application programmers to focus on the applications.

The Immune system aims to provide survivability to CORBA applications, enabling them to continue to operate despite malicious attacks, accidents or faults. Every object within the CORBA application is actively replicated by the Immune system, with majority voting applied on incoming invocations and responses to each replica of the object. Secure multicast protocols are employed to enable the majority voting to be effective, even when processors within the network and objects within the application become corrupted.

Complex soft real time distributed object systems require object profiling, scheduling and migration algorithms to respond to transient changes in the load or in the availability of the resources. We have developed a resource management system for a soft real time distributed object system that is based on a three level feedback loop which employs a profiling algorithm that monitors the usage of the resources, a least laxity scheduling algorithm that schedules the tasks, and hot spot and cooling algorithms that allocate and migrate objects to balance the load on the resources. The resource management system consists of a single (but possibly replicated and distributed) resource manager, and profilers and schedulers located on each of the processors in the distributed system.

In CORBA-based applications that depend on object replication for fault tolerance, inconsistencies in the states of the replicas of an object can arise when concurrent threads within those replicas perform updates in different orders. By imposing a single logical thread of control on every replicated multithreaded CORBA client or server object, and by providing deterministic scheduling of threads and operations a cross the replicas of each object, the Eternal system achieves consistent object replication. The Eternal system does this transparently, with no modification to the application, the ORB, or the concurrency model employed by the ORB.

Electronic commerce technology offers the opportunity to integrate and optimize the global production and distribution supply chain. The computers of the various corporations, located throughout the world, will communicate with each other to determine the availability of components, to place and confirm orders, and to negotiate delivery timescales. We describe MAgNet, a system for networked electronic trading that is based on the Java mobile agent technology, called aglets. Aglets are dispatched by the buyer to the various suppliers, where they negotiate orders and deliveries, returning to the buyer with their best deals for approval. MAgNET handles the deep supply chain, where a supplier may need to contact further suppliers of subcomponents in order to respond to an enquiry. Experimental results demonstrate the feasibility of using the Java aglet technology for electronic commerce.

Advances in fiber-optic and VLSI technology are leading to the development of multi-gigabit wide-area networks based on asynchronous transfer mode (ATM). The Thunder and Lightning network project at the University of California, Santa Barbara, is building a high-speed ATM switch in which each link operates at 40 gigabits per second. The instant start protocol, developed for the Thunder and Lightning network, maximises throughput by allowing transmission to begin without a reservation while guaranteeing lossless communication even when the network cannot handle the initial rate of transmission. Instant start is able to provide this behavior with the use of first-in first-out (FIFO) buffers. This paper discusses the problems of exercising flow control in the high-speed Thunder and Lightning network and describes the techniques used by the instant start protocol to overcome them.

Advances in fiber-optic and VLSI technology have led to the emergence of very high-speed networks based on asynchronous transfer mode (ATM). The time required to transmit the data into the network at the source is small compared to the delay to propagate the data from source to destination. Cell loss is also a major concern in ATM networks because waiting for the retransmission of lost cells delays the delivery of cells and requires substantial buffer space. The instant start protocol eliminates the costly bandwidth reservation delay before transmission can begin. Simultaneously, it provides lossless transmission even when the network cannot handle the offered rate of transmission. Unlike other lossless protocols, instant start requires relatively little special control hardware or processing at each switch.

The Totem multiple-ring protocol provides reliable totally ordered delivery of messages across multiple local-area networks interconnected by gateways. This consistent message order is maintained in the presence of network partitioning and remerging, and of processor failure and recovery. The protocol provides accurate topology change information as part of the global total order of messages. It addresses the issue of scalability and achieves a latency that increases logarithmically with system size by exploiting process group locality and selective forwarding of messages through the gateways. Pseudocode for the protocol and an evaluation of its performance are given. —Authors' Abstract

Multicast group communication protocols provide a foundation on which distributed systems can be built. The performance of these protocols is, however, not easy to characterize or to analyze. This research determines probability density functions for the latency to message delivery for the Totem multicast protocols, which provide reliable totally ordered delivery of multicast messages across single and multiple local-area networks (LANs). Totem uses a logical token-passing ring on each LAN with gateways that forward messages selectively between LANs. Comparing the performance of single-ring, two-ring and four-ring networks shows that, with message filtering in the gateways, multiple-ring networks can achieve lower mean latency, less variability in the latency, and shorter tails of the latency distribution than an equivalent single-ring network.

Concurrent real-time systems are among the most difficult systems to design because of the many possible interleavings of events and because of the timing requirements that must be satisfied. We have developed a graphical environment based on Real-Time Graphical Interval Logic (RTGIL) for specifying and reasoning about the designs of concurrent real-time systems. Specifications in the logic have an intuitive graphical representation that resembles the timing diagrams drawn by software and hardware engineers, with real-time constraints that bound the durations of intervals. The syntax-directed editor of the RTGIL environment enables the user to compose and edit graphical formulas on a workstation display; the automated theorem prover mechanically checks the validity of proofs in the logic; and the database and proof manager tracks proof dependencies and allows formulas to be stored and retrieved. This article describes the logic, methodology, and tools that comprise the prototype RTGIL environment and illustrates the use of the environment with an example application.

We present an innovative totally ordered multicast protocol that is based on reservation of buffers at the destinations and intermediate network bridges, rather than on an acknowledgment strategy. By introducing timestamps into the packets and by using a buffer reservation retract scheme, our protocol not only produces a global total order of packets but also solves the deadlock and starvation problems to which reservation-based protocols are vulnerable. A discrete event simulation demonstrates the high throughput and low latency of the protocol.

Communication protocol designers are facing new challenges due to the development of high-speed networks and to the increasing demands of network applications. Gigabit networks pose a challenge to flow control techniques developed for traditional acknowledgment-based, and typically packet-switched, lower-speed networks. Network applications such as distributed databases, groupware and distributed multimedia, all of which require multicasting, have rendered insufficient existing point-to-point flow control methodologies. We examine the problem of flow control for multicasting in gigabit networks. Instead of feedback or rate adaptation techniques, we employ more active flow control mechanisms that use traffic information in protocol control frames. These techniques are very effective for the totally ordered multicast protocol we have developed for the QuickRing gigabit local-area network.

We present-the Totem multiple-ring protocol, a novel reliable ordered multicast protocol for multiple interconnected local-area networks. The protocol exhibits excellent performance and maintains a consistent network-wide total order of messages despite network partitioning and remerging, or processor failure and recovery with stable storage intact. The Totem protocol is designed for fault-tolerant distributed systems, which replicate data to guard against failures and must ensure that replicated data remain consistent despite failures. The network-wide total order of messages provided by Totem simplifies the maintenance of consistency of replicated data, and, thus, eases the development of fault-tolerant distributed systems.

Interval logic has been introduced as a temporal logic that provides higher-level constructs and an intuitive graphical representation, making it easier in interval logic than in other temporal logics to specify and reason about concurrency in software and hardware designs. In this paper we present axiomatizations for two propositional interval logics and relate these logics to Until Temporal Logic. All of these logics are discrete linear-time temporal logics with no next operator. The next operator obstructs the use of hierarchical abstraction and refinement, and makes reasoning about concurrency difficult.

Fault-tolerant distributed systems are becoming more important, but in existing systems, maintaining the consistency of replicated data is quite expensive. The Totem single-ring protocol supports consistent concurrent operations by placing a total order on broadcast messages. This total order is derived from the sequence number in a token that circulates around a logical ring imposed on a set of processors in a broadcast domain. The protocol handles reconfiguration of the system when processors fail and restart or when the network partitions and remerges. Extended virtual synchrony ensures that processors deliver messages and configuration changes to the application in a consistent, systemwide total order. An effective flow control mechanism enables the Totem single-ring protocol to achieve message-ordering rates significantly higher than the best prior total-ordering protocols.

We formulate a model of extended virtual synchrony that defines a group communication transport service for multicast and broadcast communication in a distributed system. The model extends the virtual synchrony model of the Isis system to support continued operation in all components of a partitioned network. The significance of extended virtual synchrony is that, during network partitioning and remerging and during process failure and recovery, it maintains a consistent relationship between the delivery of messages and the delivery of configuration changes across all processes in the system and provides well-defined self-delivery and failure atomicity properties. We describe an algorithm that implements extended virtual synchrony and construct a filter that reduces extended virtual synchrony to virtual synchrony.>

Introduction The development of communication protocols is significantly more difficult than the development of sequential programs. Communication protocols are harder to develop because of the many possible executions and ordering of events, the difficulty of recording the history of an execution, the inability to stop the system so that its state can be examined, the difficulty of injecting a stimulus or fault at exactly the right moment, and the lack of reproducibility. Fault-tolerance presents additional problems, particularly the need to recover correctly from rare failure modes and the appearance of correct operation even though the system contains serious defects. The protocol development environment presented here was designed to aid in the development of the Totem reliable ordered broadcast protocol, but its concepts are also applicable to other communication protocols. The development environment is a distributed discrete-event simulator designed to provide a testbed

For fault-tolerant real-time distributed systems, the probability that a message is not delivered within its real-time deadline must be small enough that it does not adversely affect system reliability. The authors investigate the delivery of messages for the totem protocol, a reliable ordered broadcast protocol that the authors have developed for fault-tolerant distributed systems with physical broadcasts over a local-area network. The total order on broadcast messages, constructed by the totem protocol, supports the maintenance of consistency of replicated information as, for example, in a replicated database. The authors present a methodology for determining the probability of satisfying bounds on the latency from message origination to ordered delivery in the presence of communication faults.>

We present axiomatizations for Until Temporal Logic (UTL) and for Since/Until Temporal Logic (SUTL). These logics are intended for use in specifying and reasoning about concurrent systems. They employ neither a next nor a previous operator, which obs

This article describes a graphical interval logic that is the foundation of a tool set supporting formal specification and verification of concurrent software systems. Experience has shown that most software engineers find standard temporal logics difficult to understand and use. The objective of this article is to enable software engineers to specify and reason about temporal properties of concurrent systems more easily by providing them with a logic that has an intuitive graphical representation and with tools that support its use. To illustrate the use of the graphical logic, the article provides some specifications for an elevator system and proves several properties of the specifications. The article also describes the tool set and the implementation.

Presents protocols for determining processor membership in asynchronous distributed systems that are subject to processor and communication faults. These protocols depend on the placement of a total order on broadcast messages. The types of systems for which each of these protocols is applicable are characterized by the properties of the communication mechanisms and by the availability of stable storage. In the absence of stable storage or of a mechanism for distinguishing promptly delivered messages, the authors show that no membership protocol can exist. They also discuss their experience in implementing these membership protocols.>

The Totem protocol supports consistent concurrent operations by placing a total order on broadcast messages. This total order is achieved by including a sequence number in a token circulated around a logical ring that is imposed on a set of processors in a broadcast domain. A membership algorithm handles reconfiguration, including restarting of a failed processor and remerging of a partitioned network. Effective flow-control allows the protocol to achieve message ordering rates two to three times higher than the best prior protocols. The single-ring total ordering protocol of Totem provides fault-tolerant agreed and safe delivery of messages within a broadcast domain.>

Real-Time Future Interval Logic (RTFIL) is a visual logic with formulae that resemble timing diagrams. It is a dense real-time temporal logic that is based on two simple temporal primitives: interval modalities for the purely qualitative part and duration predicates for the quantitative part. We present the logic, and illustrate its use in specifying the railroad crossing example and in proving some of its properties. The logic is decidable by reduction to the emptiness problem of Timed Buchi Automata. An automated theorem prover based on this decision procedure has been implemented as part of a graphical proof environment. The proofs of the railroad crossing example have been verified using this theorem prover. An automated theorem prover and a graphical specification language greatly facilitate the task of verifying real-time proofs. This convenience apart, RTFIL is invariant under real-time stuttering and does not admit instantaneous states. These properties facilitate proof methods based on abstraction and refinement.>

Two novel efficient algorithms for placing a total order on messages in an asynchronous fault-tolerant distributed system are presented. The algorithms are resilient to fewer than ${n / 3}$ and ${n / 2}$ faulty processes in an n-process system. Partial correctness and probabilistic termination are demonstrated; it is also shown that there does not exist a total ordering algorithm that is guaranteed to terminate. A comparison of the complexity of the algorithms is given.

We present a description of a graphical interval logic that is the foundation of a toolset we are developing to support formal specification and verification of concurrent software systems. Experience has shown that most software engineers find standard temporal logics difficult to under- stand and to use. Our objective is to enable software engineers to specify and reason about temporal properties of concurrent systems more easily by providing them with a logic that has an intuitive graphical representation and with tools that support its use. To illustrate the use of our graphical interval logic, we provide a specification for a readers/writers database system and prove several properties of the specification.

Existing technology is quite successful at preventing direct unauthorized communication in multilevel secure computer systems, but is almost completely ineffective at protecting such systems against covert storage and timing channels. In a covert channel, one process transmits secret information by modulating its rate of use of a shared resource, while another program detects that modulation by monitoring the responsiveness of the resource. The proposed protection technique involves screening all programs in a system by a data dependency analysis procedure that determines whether the results of those programs depend on the relative timing of operations within the system. Programs containing such timing dependencies are denied access to the system until certified by other means. The approach is reasonably inexpensive and completely rigorous and, when strictly applied, precludes all communication over covert storage and timing channels.>

Algorithms for solving the processor membership problem in asynchronous distributed systems that are subject to processor and communication faults are presented. These algorithms are based on the placement of a total order on broadcast messages. The types of systems for which each of these algorithms is appropriate are characterized in terms of the properties of the communication mechanisms and the availability of stable storage. In the absence of stable storage or a mechanism for distinguishing promptly delivery messages, it is shown that no membership algorithm exists.>

The Trans protocol is a communications protocol that exploits the broadcast capability of local area networks. Classical Markov models and queueing theory are used to analyze the performance of components of this protocol, but cannot be applied directly to determine the performance of the protocol as a whole. Instead, Laplace transforms of the distributions for the components are first derived and then combined into a transform for the entire protocol. This transform is evaluated by contour integration to yield the latency for the protocol.

We present a method of analyzing the performance of weighted voting algorithms in a fault-tolerant distributed system. In many distributed systems, some processors send messages more frequently than others and all processors share a common communication medium, such as an Ethernet. Typical fault-tolerant voting algorithms require that a certain minimum number of votes be collected from different processors. System performance is significantly affected by the time required to collect those votes. We formulate the problem of weighted voting in terms of probabilistic languages and then use the calculus of generating functions to compute the expected delay to collect that number of votes. An application of the method to a particular voting algorithm, the Total protocol, is given.

Abstract We describe our practical experience in the use of formal verification to obtain increased confidence in the design of safety‐critical systems. The experiment involved demonstrating the consistency of the design specifications of SIFT, a software‐implemented fault‐tolerant operating system for aircraft flight control. Specifications were written at successive levels of abstraction from the most abstract requirements definition down to the detailed level of program code. Consistency of the successive levels of specification was demonstrated using the enhanced HDM verification system. Formal verification is currently feasible only for carefully simplified systems, but there appears to be no alternative method that can meet the extreme safety requirements for safety‐critical systems.

An innovative approach is presented to the design of fault-tolerant distributed systems that avoids the several rounds of message exchange required by current protocols for consensus agreement. The approach is based on broadcast communication over a local area network, such as an Ethernet or a token ring, and on two novel protocols, the Trans protocol, which provides efficient reliable broadcast communication, and the Total protocol, which with high probability promptly places a total order on messages and achieves distributed agreement even in the presence of fail-stop, omission, timing, and communication faults. Reliable distributed operations, such as locking, update, and commitment, typically require only a single broadcast message rather than the several tens of messages required by current algorithms.>

Distributed systems present problems of maintaining consistency of distributed data in the presence of faults. These problems are currently solved by agreement protocols that require many messages to be exchanged between processors with adverse effects on system performance. An approach is presented to the design of fault-tolerant distributed systems that avoids this message exchange, resulting in systems that are substantially more efficient. This approach is based on broadcast communication over a local area network such as the Ethernet, and on two novel protocols: the Trans protocol which provides efficient reliable broadcast communication, and the Total protocol which, with high probability, promptly takes a total order on messages and achieves distributed agreement even in the presence of a fault. Reliable distributed operations, such as locking, update, and commitment, require only a single broadcast message rather than the several tens of messages required by current algorithms.>

Algorithms are described for maintaining clock synchrony in a distributed multiprocess system where each process has its own clock. These algorithms work in the presence of arbitrary clock or process failures, including “two-faced clocks” that present different values to different processes. Two of the algorithms require that fewer than one-third of the processes be faulty. A third algorithm works if fewer than half the processes are faulty, but requires digital signatures.

An informal description is given of three fault-tolerant clock-synchronization algorithms. These algorithms work in the presence of arbitrary kinds of failure, including “two-faced” clocks. Two of the algorithms are derived from Byzantine Generals solutions.

During the last several years, we have explored temporal logic as a framework for specifying and reasoning about concurrent programs, distributed systems, and communications protocols. Previous papers[Schwartz/Melliar-Smith81, 82, Vogt82a,b] report on our efforts using temporal reasoning primitives to express very high-level abstract requirements that a program or system is to satisfy. Based on our experiences with those primitives, we have developed an interval logic more suitable for expressing higher-level temporal properties.

This paper describes the formal specification and proof methodology employed to demonstrate that the SIFT computer meets its requirements. The hierarchy of design specifications is shown, from very abstract descriptions of system function down to the implementation. The most abstract design specifications are simple and easy to understand, almost all details of the realization having been abstracted out, and can be used to ensure that the system functions reliably and as intended. A succession of lower level specifications refine these specifications into more detailed and more complex views of the system design, culminating in the Pascal implementation. The paper describes the rigorous mechanical proof that the abstract specifications are satisfied by the actual implementation.

This paper attempts to lend perspective to several different methods that have been employed for specifying computer communication protocols by comparing a spectrum of specification techniques. The paper characterizes specification languages such as state transition diagrams, variants of temporal logic approaches, and sequence expressions by the extent to Which information is encoded as properties of a single state versus properties of a history of the entire computation state sequence. Taking the prototypical alternating bit protocol as an example, each method is used to specify the requirements for the send process of the distributed system.