Abstract TheArjunatransaction processing system began life in the mid‐1980s as an academic research project to examine the use of object‐oriented techniques in the development of fault‐tolerant distributed systems. Thirty‐five years later, and available in open source form, it forms an integral part of various middleware products from Red Hat where it is used to provide ACID as well as non‐ACID transaction services. This journey from an academic to a commercial environment has been neither easy nor smooth but it has been interesting from many different perspectives. This article gives an overview of this journey, discusses the features ofArjunathat enables it to support a wide variety of transaction services and concludes by presenting lessons learned.

The electronic representation of a contract for a business-to-business (B2B) partnership should be such that it can be used by a monitoring service for compliance checking of B2B interactions at runtime, ensuring that the interactions match the rights and obligations that each partner has promised to honor. With this view in mind, the paper develops a model for checking contractual compliance of business interactions. Specifically, the paper develops a novel way of representing contract clauses using business rules, that is specially suited to compliance checking and describes what events need to be captured from the underlying messaging middleware and how they can be processed in a careful manner to evaluate contractual compliance.

A pay-per-use cloud service should be made available to consumers with an unambiguous resource accounting model that precisely describes all the factors that are taken into account in calculating resource consumption charges. The paper proposes the notion of consumer-centric resource accounting model such that consumers can programmatically compute their consumption charges of a remotely used service. In particular, the notion of strongly consumer-centric accounting model is proposed that requires that all the data needed for calculating billing charges can be collected independently by the consumer (or a trusted third party, TTP); in effect, this means that a consumer (or a TTP) should be in a position to run their own measurement service. Strongly consumer-centric accounting models have the desirable property of openness and transparency, since service users are in a position to verify the charges billed to them. To illustrate the ideas, the accounting model of a given cloud infrastructure service (simple storage service, S3 from Amazon) is evaluated. The exercise reveals some shortcomings which can be fixed as indicated in this paper to make Amazon's model strongly consumer-centric. Service providers can learn from this evaluation study to re-examine their accounting models and perform any amendments.

Three-tier middleware architecture is commonly used for hosting enterprise-distributed applications. Typically, the application is decomposed into three layers: front end, middle tier, and back end. Front end ("Web server") is responsible for handling user interactions and acts as a client of the middle tier, while back end provides storage facilities for applications. Middle tier ("application server") is usually the place where all computations are performed. One of the benefits of this architecture is that it allows flexible management of a cluster of computers for performance and scalability; further, availability measures, such as replication, can be introduced in each tier in an application-specific manner. However, incorporation of availability measures in a multitier system poses challenging system design problems of integrating open, nonproprietary solutions to transparent failover, exactly once execution of client requests, nonblocking transaction processing, and an ability to work with clusters. This paper describes how replication for availability can be incorporated within the middle and back-end tiers, meeting all these challenges. This paper develops an approach that requires enhancements to the middle tier only for supporting replication of both the middleware back-end tiers. The design, implementation, and performance evaluation of such a middle-tier-based replication scheme for multidatabase transactions on a widely deployed open source application server (JBoss) are presented.

The paper considers distributed applications where interactions between constituent services take place via messages in an asynchronous environment with unpredictable communication and processing delays; further, interacting parties are not required to be online at the same time. Message-oriented middleware (MoM) is commonly used for connecting such loosely coupled distributed applications. Despite loose coupling, many service interactions have temporal and message validation constraints. A failure to deliver a valid message within its time constraint could cause mutually conflicting views of an interaction (one party regarding it as timely whilst the other party regarding it as untimely) leading to application level inconsistencies. In a loosely coupled system, such inconsistencies could remain undetected for a long time, requiring costly application level recovery procedures. This paper describes how synchronisation support providing multilateral consistency guarantees can be provided using the underlying MoM to prevent inconsistencies from reaching application level.

Internet-scale distributed applications are frequently built as loosely coupled compositions of services. We would like that despite loose coupling, each constituent service has a mutually consistent view of the state of the application not withstanding software, hardware and network related problems (e.g., clock skews, unpredictable transmission delays, message loss, node crashes etc.). Some observations on how messaging middleware should be structured to accomplish this are presented.

The use of open, Internet-based communications for business-to-business (B2B) interactions requires accountability for and acknowledgment of the actions of participants. Accountability and acknowledgment can be achieved by the systematic maintenance of an irrefutable audit trail to render the interaction non-repudiable. To safeguard the interests of each party, the mechanisms used to meet this requirement should ensure fairness. That is, misbehavior should not disadvantage well-behaved parties. Despite the fact that Web services are increasingly used to enable B2B interactions, there is currently no systematic support to deliver such guarantees. This paper introduces a flexible framework to support fair non-repudiable B2B interactions based on a trusted delivery agent. A Web services implementation is presented. The role of the delivery agent can be adapted to different end user capabilities and to meet different application requirements.

To form and automatically manage partnerships within a virtual organisation, it is necessary to have an electronic representation of the contract governing business relationships that can be used to mediate the rights and obligations that each interacting entity promises to honour. The paper describes a general method of representing business interactions using a widely used modelling language Promela and discusses how to represent permissions, obligations, prohibitions, actors (agents), time constraints, and message type checking; that is, all the basic parameters that compose most typical business contracts. Two levels of contract representations are described: implementation neutral, and implementation specific, that is a refinement of the former to include technical details such as acknowledgements and synchronization messages that form an important part of any implementation.

The use of open, Internet-based communications for business-to-business (B2B) interactions requires accountability for and acknowledgment of the actions of participants. Accountability and acknowledgment can be achieved by the systematic maintenance of an irrefutable audit trail to render the interaction non-repudiable. To safeguard the interests of each party, the mechanisms used to meet this requirement should ensure fairness. That is, misbehaviour should not disadvantage well-behaved parties. Despite the fact that Web services are increasingly used to enable B2B interactions, there is currently no systematic support to deliver such guarantees. This paper introduces a flexible framework to support fair non-repudiable B2B interactions based on a trusted delivery agent. A Web services implementation is presented. The role of the delivery agent can be adapted to different end user capabilities and to meet different application requirements.

Fair exchange protocols play an important role in application areas such as e-commerce where protocol participants require mutual guarantees that a transaction involving exchange of items has taken place in a specific manner. A protocol is fair if no protocol participant can gain any advantage over an honest participant by misbehaving. In addition, such a protocol is fault-tolerant if the protocol can ensure that an honest participant does not suffer any loss of fairness despite any failures of the participant's node. This paper presents a family of fair exchange protocols for two participants which make use of the presence of a trusted third party, under a variety of assumptions concerning participant misbehavior, message, delays, and node reliability. The development is systematic, beginning with the strongest set of the assumptions and gradually weakening the assumptions to the weakest set. The resulting protocol family exposes the impact of a given set of assumptions on solving the problem of fair exchange. Specifically, it highlights the relationships that exist between fairness and assumptions on the nature of participant misbehavior, communication delays, and node crashes. The paper also shows that the restrictions assumed on a dishonest participant's misbehavior can be realized through the use of smartcards and smartcard-based protocols.

The wide variety of services and resources available over the Internet presents new opportunities to create value added, inter-organisational composite services (CSs)from multiple existing services. To preserve their autonomy and privacy, each organisation needs to regulate access both to their services and to shared information within the CS. Key mechanisms to facilitate such regulated interactions are the collection and verification of non-repudiable evidence of the actions of the parties to the CS. The paper describes how component-based middleware can be enhanced to support non-repudiable service invocation and information sharing. A generic implementation, based on a J2EE application server, is presented.

A recent trend has seen the extension of object-oriented middleware. A major advantage components offer over objects is that only the business logic of an application needs to be addressed by a programmer with support services required incorporated into the application at deployment time. This is achieved via components (business logic of an application), containers that host components and are responsible for providing the underlying middleware services required by components and application servers that host containers. Well-known examples of component middleware architectures are Enterprise Java Beans (EJBs) and the CORBA Component model (CCM). Two of the many services available at deployment time in most component architectures are component persistence and atomic transactions. This paper examines, using EJBs, how replication for availability can be supported by containers so that components that are transparently using persistence and transactions can also be made highly available.

Abstract Although it has long been realized that ACID (atomicity, consistency, isolation, durability) transactions by themselves are not adequate for structuring long‐lived applications and much research work has been done on developing specific extended transaction models, no middleware support for building extended transactions is currently available and the situation remains that a programmer often has to develop application specific mechanisms. The CORBA Activity Service Framework described in this paper is a way out of this situation. The design of the service is based on the insight that the various extended transaction models can be supported by providing a general purpose event signalling mechanism that can be programmed to enable activities—application specific units of computations—to coordinate each other in a manner prescribed by the model under consideration. The different extended transaction models can be mapped onto specific implementations of this framework, permitting such transactions to span a network of systems connected indirectly by some distribution infrastructure. The framework described in this paper is an overview of the OMG's (Object Management Group) Additional Structuring Mechanisms for the OTS standard. Through a number of examples the paper shows that the framework has the flexibility to support a wide variety of extended transaction models. Although the framework is presented here in CORBA specific terms, the main ideas are sufficiently general, so that it should be possible to use them in conjunction with other middleware. Copyright © 2003 John Wiley & Sons, Ltd.

Organisations increasingly use the Internet to offer their own services and to utilise the services of others. This naturally leads to information sharing across organisational boundaries. However, despite the requirement to share information, the autonomy and privacy requirements of organisations must not be compromised. This demands the strict policing of inter-organisational interactions. Thus there is a requirement for dependable mechanisms for information sharing between organisations that do not necessarily trust each other. The paper describes the design of a novel distributed object middleware that guarantees both safety and liveness in this context. The safety property ensures that local policies are not compromised despite failures and/or misbehaviour by other parties. The liveness property ensures that, if no party misbehaves, agreed interactions will take place despite a bounded number of temporary network and computer related failures. The paper describes a prototype implementation with example applications.

Bloom filters make use of a ‘probabilistic’ hash-coding method to reduce the amount of space required to store a hash set. A Bloom filter offers a trade-off between its size and the probability that the filter returns the wrong result. It does this without storing the entire set, at the cost of occasionally incorrectly answering yes to the question ‘is $x$ a member of $s$?’. How Bloom filters can be used to speed up the name to location resolution process in large-scale distributed systems is discussed. The approach presented offers trade-offs between performance (the time taken to resolve an object's name to its location) and resource utilization (the amount of physical memory to store location information and the number of messages exchanged to obtain the object's address).

Workflow management systems are required to provide flexible ways of managing workflows as the business processes they represent frequently require changes over time. Provision of flexibility features in workflow management systems is very much a research issue as workflow systems in use today have been found lacking in such features. Two approaches to achieving flexibility in workflows have been identified, namely flexibility by selection and flexibility by adaptation. Flexibility by selection is achieved by ensuring that there are a number of execution paths through the workflow process, such that key decision making points are well represented. This allows the appropriate path to be selected on a per-instance basis to take account of the prevailing circumstances. Flexibility by adaptation permits dynamic changes to workflows to include one or more new execution paths. The paper describes how flexibility is supported in the OPENflow distributed workflow system. In particular, it describes high level tool support for performing dynamic changes to a workflow. In OPENflow, dynamic reconfiguration mechanisms have been provided by making use of atomic transactions to add and remove one or more tasks and to allow the addition and removal of dependencies between tasks from a running workflow. Use of transactions ensures that changes are carried out atomically with respect to normal processing. An example application is described to illustrate flexible workflow management.

The paper develops a distributed systems architecture for dependable Internet based online auctions, meeting the requirements of data integrity, responsiveness, fairness and scalability. It is well known that a tree-based, recursive design approach caters well for scalability requirements. With this observation in mind, the paper develops an approach that permits an auction service to be mapped on to globally distributed auction servers. The paper selects a suitable auction model that treats sellers and buyers symmetrically. This symmetry enables a computational node to play at one level of the tree the role of a seller by dealing with a group of potential buyers as well as to play the role of a potential buyer at the next higher level. Such a symmetric auction (also known as a double auction) is used for supporting a standard auction to be carried out in a hierarchic manner. An architecture is developed and basic algorithms and protocols are presented.

Distributed applications should be able to make use of an object group service in a number of application specific ways. Three main modes of interactions can be identified; (i) request-reply; a client issues a request to multiple servers and waits for their replies; this represents a commonly occurring scenario when a service is replicated; (ii) group-to-group request-reply; a generalisation of the previous case, where clients are themselves groups; and (iii) Peer Participation: here all the members are regularly multicasting messages (asynchronous invocation); this represents a commonly occurring scenario when the purpose of an application is to share information between members, (e.g., a teleconferencing application). Customisation within each class of interaction is frequently required for obtaining better performance. This paper describes the design and implementation of a flexible CORBA object group service that supports the three types of interactions and enables application specific customisation. Performance figures collected over low latency LAN and high latency WAN are presented to support the case for flexibility.

The design and implementation of a dependable system that provides a composition and execution environment for distributed applications whose executions could span arbitrarily large durations is described. The objective is to create a framework for complex service provisioning. By complex service provisioning we primarily mean the ability to compose a given service out of existing ones as well as the ability to exercise dynamic control over the execution of the service. The approach taken is centred around building middleware services based on integration of workflow and agent technologies. The platform enables these two systems to interact via CORBA services. Service behaviour and service deployment are represented as workflow processes. Individual tasks that make up the workflow would be legacy applications, specially created tasks, and agent applications. Agents are able to create workflow instances, receive results from workflow and send inputs to workflows. This enables agents to act as user agents capable of managing workflows on behalf of users.

There is growing interest in providing computer support for an organisation's business processes such as customer order processing, product support, stock taking and so forth. Workflow systems are normally used for this purpose to co-ordinate and monitor execution of multiple tasks arranged to form business processes. In this context, computer support for work activity co-ordination will be taken to mean tools and services made available to the employees of an organisation to enable them to carry out their tasks that form the part of these workflows. The paper illustrates how a transactional workflow system can be augmented with support for reliable management of worklists in an arbitrarily distributed environment. Ideally, the workflow enactment service should be neutral to the types of work activity coordination services to be made available to users. In this way, the needs of a wide variety of organisations can be supported by building organisation specific services. The approach taken here is to separate organisational aspects of workflow management from the workflow enactment service as much as possible.

In a distributed system, replication of components, such as objects, is a well known way of achieving availability. For increased availability, crashed and disconnected components must be replaced by new components on available spare nodes. In this context, we address the problem of reconfiguring a group after the group as an entity has failed. Such a failure is termed a group failure which, for example, can be the crash of every component in the group or the group being partitioned into minority islands. The solution assumes crash-proof storage, and eventual recovery of crashed nodes and healing of partitions. It guarantees that: (i) the number of groups reconfigured after a group failure is never more than one, and (ii) the reconfigured group contains a majority of the components which were members just before the group failed, so that the loss of state information due to group failure is minimal. The protocol is efficient in terms of communication rounds and use of stable store, during both normal operations and reconfiguration after a group failure.

Object replication and cacheing have been used individually in distributed systems for many years. There are benefits from being able to support both: replication for availability, and cacheing for performance. Although both involve handling multiple copies of objects, there are sufficient differences between the two to make the design of an integrated approach a challenging exercise. In this paper, we describe a design that provides the benefits of both replication and cacheing by allowing both types of protocols to co-exist within the same application. We do not propose a new replication or cacheing protocol, but rather a way in which existing implementations can be combined.

The paper presents the design of a software infrastructure that can support negotiation and competition among buyers and sellers of goods (auctioning) over the Internet. The goals of data integrity, responsiveness, and scalability have been achieved by replicating the auction service across a number of auction servers.

This paper describes the design of a scripting language aimed at expressing task (unit of computation) composition and inter-task dependencies of distributed applications whose execution could span arbitrary large durations. This work is motivated by the observation that an increasingly large number of distributed applications are constructed by composing them out of existing applications and are executed in an heterogeneous environment. The resulting applications can be very complex in structure, containing many notification and dataflow dependencies between their constituent applications. The language enables applications to be structured with the properties of modularity, interoperability, dynamic reconfigurability and fault-tolerance.

Traditionally transactions have been single-threaded. In such an environment the thread terminating the transaction is, by definition, the thread which performed the work. Therefore, transaction termination is implicitly synchronised with the completion of the transactional work. With the increased availability of both software and hardware multi-threading, transaction services are being required to allow multiple threads to be active within a transaction. In these systems it is important to guarantee that all threads have completed when a transaction is terminated otherwise some work may not be performed transactionally. In this paper we present a protocol for the enforcement of checked transactional behaviour within an asynchronous environment. We illustrate the use of the protocol within a proposed implementation for a CORBA-compliant Object Transaction Service intended for a soft real-time application which makes extensive use of concurrency and asynchronous message passing.

There are many techniques supporting execution of large computations over a network of workstations (NOW) but data intensive computations are usually run on high performance parallel machines. A NOW comprising individual user's machines typically has a low performance interconnect and suffers arbitrary changes of availability. Exploiting such resources to execute data intensive computations is difficult but even in a more constrained environment there is an unfulfilled need for fault-tolerance. The structuring approach presented fulfills this need. Performance exceeding 100 Mflop/s is demonstrated for large fault-tolerant out of core examples of matrix multiplication and Cholesky factorisation using five 133 MHz Pentium compute machines.

A fail-silent node is a self-checking node that either functions correctly or stops functioning after an internal failure is detected. Such a node can be constructed from a number of conventional processors. In a software-implemented fail-silent node, the nonfaulty processors of the node need to execute message order and comparison protocols to "keep in step" and check each other, respectively. In this paper, the design and implementation of efficient protocols for a two processor fail-silent node are described in detail. The performance figures obtained indicate that in a wide class of applications requiring a high degree of fault tolerance, software-implemented fail-silent nodes constructed simply by utilizing standard "off-the-shelf" components are an attractive alternative to their hardware-implemented counterparts that do require special-purpose hardware components, such as fault-tolerant clocks, comparator, and bus interface circuits.

A general purpose group communication protocol suite called Newtop is described. It is assumed that processes can simultaneously belong to many groups, group size could be large, and processes could be communicating over the Internet. Asynchronous communication environment is therefore assumed where message transmission times cannot be accurately estimated, and the underlying network may well get partitioned, preventing functioning processes from communicating with each other. Newtop can provide causality preserving total order delivery to members of a group, ensuring that total order delivery is preserved for multi-group processes. Both symmetric and asymmetric order protocols are supported, permitting a process to use say symmetric version in one group and asymmetric version in other.

The object-oriented approach to system structuring has found widespread acceptance among designers and developers of robust computing systems. The authors propose a system structure for distributed programming systems that support persistent objects and describe how properties such as persistence and recoverability can be implemented. The proposed structure is modular, permitting easy exploitation of any distributed computing facilities provided by the underlying system. An existing system constructed according to the principles espoused here is examined to illustrate the practical utility of the proposed approach to system structuring.>

Presents a general model for persistent replicated object management and identify what metainformation about objects needs to be maintained by a naming and binding service to ensure that objects named by application programs are bound to only those object replicas which are in a mutually consistent state. These ideas are developed within the framework of a distributed system in which application programs are composed of atomic actions (atomic transactions) manipulating persistent (long-lived) objects.>

Abstract An examination of the structure of fault‐tolerant systems incorporating backward error recovery indicates a partitioning into two broad classes. Two canonical models, each representing a particular class of systems, have been constructed. The first model incorporates objects and actions as the entities for program construction whereas the second model employs communicating processes and conversations. Applications in areas such as office information and banking systems are typically described and built in terms of the first model whereas applications in the area of process control are usually described and built in terms of the second model. The paper claims that the two models are duals of each other and presents arguments and examples to substantiate this claim. It will be shown that the techniques that have been developed within the context of one model turn out to have interesting and hitherto unexplored duals in the other model.

A VOLTAN node is composed of a number of conventional processors on which application-level processes are replicated to achieve fault-tolerance. The architecture of a family of such nodes with differing functionalities is presented. These include failure-masking, fail-signal, and fail-silent nodes. The software architectures of a three-processor failure-masking and a two-processor fail-silent node are discussed in detail. The suitability of VOLTAN nodes as building blocks of reliable distributed systems is also discussed.>

An object-oriented model is developed for structuring distributed real-time applications. Atomic atoms (atomic transactions) and exception handling techniques are used to introduce fault tolerance. Additional techniques are then developed to permit application and device specific commit and abort processing. Objects can be replicated to increase their availability. The authors examine the reasons why some of the previous real-time object models are not suitable for active replication and why the model proposed represents an improvement. Realistic examples are used to illustrate the practical utility of the approach.>

The function of a garbage collector in a computer system is to reclaim storage that is no longer in use. Developing a garbage collector for a distributed system composed of autonomous computers (nodes) connected by a communication network poses a challenging problem: optimising performance whilst achieving fault-tolerance. The paper presents the design and implementation of a reference-count garbage collection scheme which is both efficient and fault-tolerant. A distributed object-based system is considered where operations on remote objects are invoked via remote procedure calls. The orphan treatment scheme associated with remote procedure calls has been enhanced to enable the collection of garbage arising from node crashes.

The authors develop some control structures suitable for composing fault-tolerant distributed applications using atomic actions (atomic transactions) as building blocks. The authors describe how such structures may be implemented using the concept of multicolored actions. The reasons why other control structures, in addition to nested and concurrent atomic actions, are desirable and are identified, and three structures are proposed: serializing actions, glued actions, and top-level independent actions. A number of examples are used to illustrate their usefulness. A technique based on the concept of multicolored actions is presented as a uniform basis for implementing all of the three action structures presented.>

Replicated execution of distributed programs, which provides a means of masking hardware (processor) failures in a distributed system, is discussed. Application-level entities (processes, objects) are replicated to execute on distinct processors. Such replica entities communicate by message passing. Nondeterminism within the replicas could cause messages to be processed in nonidentical order, producing a divergence of state. Possible sources of nondeterminism are identified, and a generic mechanism for ensuring that nonfaulty replicas process messages in identical order, thereby preventing state divergence among such replicate entities, is presented.>

A distributed system in which a job can be broken into a number of subjobs which are processed sequentially at various processors is considered. The performance of such a system is then compared to the replicated (triple modular redundant, or TMR) version of the system in which each subjob will require concurrent replicated processing with majority voting. The effect of voting times and processor failure rates on the performance of the system is investigated with analytical approximations and computer simulations. The accuracy of the former is examined. The results indicate the possible existence of a threshold voting time, below which the TMR system performs better than the unreplicated one, and above which the situation is reversed. Such thresholds are observed, where possible, in systems with repairable servers, as well as in those with nonrepairable servers.>

Replicated processing with majority voting is a well known method of achieving fault tolerance. We consider the problem of constructing a distributed system composed of an arbitrarily large number of N-modular redundant (NMR) nodes, where each node itself is composed of N, N = 2m + 1 and m ≥ 1, processing and voting elements. Advanced microprocessors, such as Inmos Transputers, provide fast serial communication links for inter-processor communication, making it possible to construct large networks of processors. We describe how replicated processing with majority voting can be achieved for such processor networks. This paper will present the overall systems architecture, including voting and NMR synchronization algorithms specially developed to exploit fast point to point communication facilities.

Arjuna is a programming system which provides a set of tools for constructing fault-tolerant distributed applications. It supports an object-oriented model of computation in which atomic actions (atomic transactions) control sequences of operations invoked upon persistent objects. Persistent objects outlive the applications that create them and this paper concentrates on the mechanisms within Arjuna that are concerned with their management. The paper describes how these mechanisms are related to the other Arjuna mechanisms required by atomic actions for the distribution, concurrency control, recovery and commitment of persistent objects.

Rajdoot is a remote procedure call (RPC) mechanism with a number of fault tolerance capabilities. A discussion is presented of the reliability-related issues and how these issues have been dealt with in the RPC design. Rajdoot supports exactly-once semantics with call nesting capability, and incorporates effective measures for orphan detection and killing. Performance figures show that the reliability measures of Rajdoot impose little overhead.>

In this correspondence we describe the design of a reliable Remote Procedure Call mechanism intended for use in local area networks. Starting from the hardware level that provides primitive facilities for data transmission, we describe how such a mechanism can be constructed. We discuss various design issues involved, including the choice of a message passing system over which the remote call mechanism is to be constructed and the treatment of various abnormal situations such as lost messages and node crashes. We also investigate what the reliability requirements of the Remote Procedure Call mechanism should be with respect to both the application programs using it and the message passing system on which it itself is based.

An object-oriented multilevel model of computation is used to discuss recoverability and crash resistance issues in distributed systems. Of particular importance are the issues that are raised when recoverability and crash resistance properties are desired from objects whose concrete representations are distributed over several nodes. The execution of a program at a node of the system can give rise to a hierarchy of processes executing various parts of the program at different nodes. Recoverability and crash resistance properties are needed to ensure that such a group of processes leave the system state consistent despite faults in the system.

Abstract The programming language Concurrent Pascal has been extended to include some language features that facilitate the writing of fault‐tolerant software. As a result, it is possible now to (1) write operating systems with a measure of fault‐tolerance, and (2) for such an operating system to support fault‐tolerant user programs. The paper describes these language features and illustrates their use with the help of a few working examples.

Abstract The implementation of backward error recovery features requires the support of a run time subsystem (called the recovery system) that is responsible for performing the task of state restoration. The recovery system implemented to support the recovery features of Concurrent Pascal includes, for each process, a recovery cache for recording appropriate recovery data. This paper describes the details of the recovery system that was implemented as a part of the interpreter of Brinch Hansen's Concurrent Pascal system.

Abstract A total of 64 references to papers, books and conference proceedings on the subject of software reliability have been selected. Each of these references is provided with an annotation consisting of a paragraph of commentary. Sections of the bibliography are devoted to requirements definition, programming methodology, certification, fault‐tolerance and reliability modelling.

Abstract The programming language Sequential Pascal has been extended to include recovery blocks. This paper describes the modifications made to the kernel and interpreter of Brinch Hansen's Pascal system to support recovery blocks and the associated recovery caches needed for state restoration.

Backward error recovery (that is, resetting an erroneous state of a system to a previous error-free state) is an important general technique for recovery from faults in a system, especially those faults which were not foreseen. However, the provision of backward error recovery can be complex, particularly if the implementation of the system is "multilever" and recovery is to be provided at a number of these levels. This paper discusses two distinct categories of multilevel system, and then examines in detail the issues involved in providing backward error recovery in both types of system.

Basic error recovery problems between interacting processes are first discussed and the desirability of having separate recovery mechanisms for cooperation and competition is demonstrated. The paper then concentrates on recovery mechanisms for processes competing for the use of the shared resources of a computer system. Appropriate programming language features are developed based on the class and inner features of SIMULA, and on the structuring concepts of recovery blocks and monitors.

Abstract This paper applies the technique of systematic (or structured) programming for programming scheduling algorithms as encountered in operating system design. Monitors are used for structuring scheduling algorithms and a synchronizing method is proposed for process scheduling. Some fairly difficult scheduling problems are solved systematically to illustrate the usefulness of the monitor concepts and the synchronizing method. Certain implementation aspects are also discussed.

This paper reviews some important ideas which have emerged from the work of Dijkstra. In particular it examines his technique of structuring programs so that the process scheduling algorithms are easy to understand and verify. The paper then reviews some synchronisation techniques and presents the reasons for favouring the techniques that neatly exploit Dijkstra's work. The paper is expository rather than original.