Search

This note introduces the special section containing research papers on distributed computing systems, which were featured in the October 1985 issue of the periodical "IEEE Transactions on Software Engineering." It discusses the objectives of most distributed computing system work. This special section was motivated by the annual International Conference on Distributed Computing Systems. The first article is on a polynomial optimal algorithm for a special type of queries called star queries. The paper by James P. Huang shows the modeling of software partition for distributed real-time applications. The paper "A Distributed Drafting Algorithm for Load Balancing" proposes migration algorithm for load balancing which is network topology independent. The last paper is on proving liveness and termination of systolic arrays using communicating finite state machines.

A control abstraction called atomic action is a powerful general mechanism for ensuring consistent behavior of a system in spite of failures of individual computations running in the system, add in spite of system crashes. However, because of the "all-or-nothing" property of atomic actions, an important amount of work might be abandoned needlessly when an internal error is encountered. This paper discusses how implementation of resilient distributed systems can be supported using a combination of nested atomic actions and stable checkpoints. Nested atomic, actions form a free structure. When an internal atomic action terminates, its results are not made permanent until the outermost atomic action commits, but they survive local node failures. Each subtree of atomic actions is recoverable individually. A checkpoint is established in stable storage as part of a remote request so that results of such a request can be reclaimed if the requesting node fails in. the meantime. The paper shows how remote procedure call primitives with "at-most-once" semantics and recovery blocks can be built with these mechanisms. [ABSTRACT FROM AUTHOR]

Recent advances in technology have made the construction of general-purpose systems out of many small independent microprocessors feasible. One of the issues concerning distributed systems is the question of appropriate language constructs for the handling of communication and synchronization. In his paper, "Communicating sequential processes," Hoare has suggested the use of the input and output constructs and Dijkstra's guarded commands to handle these two issues. This paper examines Hoare's concepts in greater detail by concentrating on the following two issues: 1) allowing both input and output commands to appear in guards, 2) simple abstract implementation of the input and output constructs. In the process of examining these two issues we develop a framework for the design of appropriate communication and synchronization facilities for distributed systems. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of replicated service provision in distributed systems. Existing systems that follow the State Machine approach concentrate on the synchronization of the server replicas and do not consider the problem of client interaction with the server group. The paper analyzes client interaction and identifies a number of access protocols to meet a range of client requirements and system models. The paper demonstrates that protocols for the "open" group model — clients external to the group of servers — satisfy the requirements of the State Machine approach, even when replication is transparent to the clients. Experimental performance results indicate that the "open" model is clearly desirable when the service is used by a large, dynamically changing set of clients. The situation which pertains to Internet service provision. [ABSTRACT FROM AUTHOR]

Regeneration with Virtual Copies is a voting-based consistency control algorithm for replicated data objects in a distributed computing system. Proposed by Adam and Tewari, it utilizes selective regeneration and recovery mechanisms for maintaining the availability and consistency of copies. This paper describes some problems with the original paper and proposes solutions. [ABSTRACT FROM AUTHOR]

A new approach for checkpointing and rollback recovery in a distributed computing system using a common time base is proposed in this paper. First, a common time base is established in the system using a hardware clock synchronization algorithm. This common time base is coupled with the idea of pseudo-recovery points to develop a checkpointing algorithm that has the following advantages: 1) reduced wait for commitment for establishing recovery lines, 2) fewer messages to be exchanged, and 3) less memory requirement. These advantages are assessed quantitatively by developing a probabilistic model. [ABSTRACT FROM AUTHOR]

This paper deals with the analysis of large-scale closed queueing network (QN) models which are used for the performance analysis of computer communication networks (CCN's). The computer systems are interconnected by a wide-area network. Users accessing local/remote computers are affected by the contention (queueing delays) at the computer systems and the communication subnet. The computational cost of analyzing such models increases exponentially with the number of user classes (chains), even when the QN is tractable (product-form). In fact, the submodels of the integrated model are generally not product-form, e.g., due to blocking at computer systems (multiprogramming level constraints) and in the communication subnet (window flow control constraints). Two approximate solution methods are proposed in this paper to analyze the integrated QN model. Both methods use decomposition and iterative techniques to exploit the structure of the QN model such that computational cost is proportional to the numbs of chains. The accuracy of the solution methods is validated against each other and simulation. The model is used to study the effect that channel capacity assignments, window sizes for congestion control, and routing have on system performance. [ABSTRACT FROM AUTHOR]

In his paper "Communicating Sequential Processes," bare suggested the use of the input/output construct and Dijkstra's guarded commands for handling the task of communication and synchronization in distributed systems. bare's proposal was intended for programming general parallel systems; as a result, little consideration was given by Hoare to the question of how his mechanisms could be utilized in the construction of reliable dynamic resource management schemes. In this paper, we examine this problem and propose several simple extensions to bare's constructs that will make the extended Communicating Sequential Processes concept more suitable for the handling of such management schemes. [ABSTRACT FROM AUTHOR]

In a distributed computing system made up of different types of processors each processor in the system may have different performance and reliability characteristics. In order to take advantage of this diversity of processing power, a modular distributed program should have its modules assigned in such a way that the applicable system performance index, such as execution time or cost, is optimized. This paper describes an algorithm for making an optimal module to processor assignment for a given performance criteria. We first propose a computational model to characterize distributed programs, consisting of tasks and an operational precedence relationship. This model allows us to describe probabilistic branching as well as concurrent execution in a distributed program. The computational model along with a set of seven program descriptors completely specifies a model for dynamic execution of a program on a distributed system. The optimal task to processor assignment is found by an algorithm based on results in Markov decision theory. The algorithm given in this paper is completely general and applicable to N-processor systems. [ABSTRACT FROM AUTHOR]

In database management systems and operating systems, transactions are used as units of consistency, serializability, recovery, and for deadlock control. Normally, the transactions for each of these systems are considered independently. In this paper we describe nested transactions where the transactions from one system interact with the transactions from another system. Such nested transactions can expect to become more important with the introduction of network operating systems and heterogeneous distributed database systems. Nested transactions raise additional problems for the desirability of enforcement of serializability, for the prevention and detection of deadlock, and for the consistent system state recovery from hardware and software crashes. This paper directly addresses the deadlock problems of nested transactions. In particular, we define a transaction controller (IC) that is responsible for maintaining exclusive and restricted shared access to a specific set of resources in what we call its transaction control domain (TCD). TC's are said to interact if a transaction in one controller can initiate a transaction in another controller. Three approaches to the deadlock problem of interacting TC's are described. In the first approach, TC's are tightly coupled in that they need to share transaction identifiers, resource identifiers, and use a common deadlock control mechanism. In the second approach, TC's obey protocols which ensure that if deadlock does occur it will be completely contained in one TCD. In the final approach, we resort to the currently used techniques of a timeout mechanism between interacting mutually suspicious TC's. [ABSTRACT FROM AUTHOR]

This paper introduces Triggered Message Sequence Charts (TMSCs), a graphical, mathematically well-founded framework for capturing scenario-based systems requirements of distributed systems. Like Message Sequence Charts (MSCs), TMSCs are graphical depictions of scenarios, or exchanges of messages between processes in a distributed system. Unlike MSCs, however, TMSCs are equipped with a notion of trigger that permits requirements to be made conditional, a notion of partiality indicating that a scenario may be subsequently extended, and a notion of refinement for assessing whether or not a more detailed specification correctly elaborates on a less detailed on. The TMSC rotation also includes a collection of composition operators allowing structure to be introduced into scenario specifications so that interactions among different scenarios may be studied. In the first part of this paper, TMSCs are introduced and their use in support of requirements modeling is illustrated via two extended examples. The second part develops the mathematical underpinnings of the language. [ABSTRACT FROM AUTHOR]

The development of complex distributed systems demands for the creation of suitable architectural styles (or paradigms) and related runtime infrastructures. An emerging style that is receiving increasing attention is based on the notion of event. In an event-based architecture, distributed software components interact by generating and consuming events. An event is the occurrence of some state change in a component of a software system, made visible to the external world. The occurrence of an event in a component is asynchronously notified to any other component that has declared some interest in it. This paradigm (usually called "publish/subscribe," from the names of the two basic operations that regulate the communication) holds the promise of supporting a flexible and effective interaction among highly reconfigurable, distributed software components. In the past two years, we have developed an object-oriented infrastructure called JEDI (Java Event-Based Distributed Infrastructure). JEDI supports the development and operation of event-based systems and has been used to implement a significant example of distributed system, namely, the OPSS workflow management system (WFMS). The paper illustrates the main features of JEDI and how we have used them to implement OPSS. Moreover, the paper provides an initial evaluation of our experiences in using the event-based architectural style and a classification of some of the event-based infrastructures presented in the literature. [ABSTRACT FROM AUTHOR]

There has been a lot of interest in the past decade in using timed Petri nets to model computer systems. In this paper we show how such timed Petri nets can be used to great advantage in describing and algebraically specifying communication system performance. We make use of the time parameter of timed Petri nets to model the delay in performing certain operations of a communication protocol. The specification is borrowed from the recently reported AFFIRM language, and the protocol chosen for illustration is the ECMA transfer protocol, proposed for the ISO reference model. However, the methodology can be used with other protocols as well. We also show how liveness properties can be specified easily using timed Petri nets. [ABSTRACT FROM AUTHOR]

The TABS prototype is an experimental facility that provides operating system-level support for distributed transactions that operate on shared abstract types. The facility is designed to simplify the construction of highly available and reliable distributed applications. This paper describes the TABS system model, the TABS prototype's structure, and certain aspects of its operation. The paper concludes with a discussion of the status of the project and a preliminary evaluation. [ABSTRACT FROM AUTHOR]

The concepts of system reliability, generally defined as the ability of a computer system to meet its interface specifications within a specified time limit, predate not only that of distributed computing but also that of the electronic computer itself. With the advent of the electronic computer, reliability and availability gained recognition as disciplines of intellectual challenge. The development of reliability techiques can be linked to computer hardware developments. Interest in distributed software and database systems has grown substantially.

Technological advances have nude it possible to construct systems from collections of computers connected by a network. At present, however, there is little support for the construction and execution of software to run on such a system. Our research concerns the development of an integrated language/system whose goal is to provide the needed support. This paper discusses a number of issues that must be addressed in such a language. The major focus of our work and this paper is support for the construction of robust software that survives node, network, and media failures. [ABSTRACT FROM AUTHOR]

A hierarchically organized and a distributed protocol for deadlock detection in distributed databases are presented in [1]. In this paper we show that the distributed protocol is incorrect, and present possible remedies. However, the distributed protocol remains impractical because "condensations" of "transaction-wait-for" graphs make graph updates difficult to perform. Delayed graph updates cause the occurrence of false deadlocks in this as well as in some other deadlock detection protocols for distributed systems. The performance degradation that results from false deadlocks depends on the characteristics of each protocol. [ABSTRACT FROM AUTHOR]

The problems of review and revocation of access privileges are presented in the context of the systems that use capabilities for the long-term distribution of access privileges. An approach that solves both of these problems in their most general form is presented in this paper. The approach requires that a capability propagation graph be maintained in memory spaces associated with subjects (e.g., domains, processes, etc.) that make copies of the respective capability; the graph remains inaccessible to those subjects, however. Parallel processes of the operating system update the graph as the system runs. This approach has a number of properties generally considered advantageous. It leaves capability addressing essentially unchanged, and it modifies the mechanism for capability copying only minimally. It results in insignificant increases in kernel complexity. Should revocation not include mechanisms for its automatic reversal, the review and revocation mechanisms need not even be verified formally to ensure object protection. Also, this approach is flexible, as it allows simple, practical implementation that supports only certain forms of revocation, but nevertheless supports access review. Last but not least, it leads to an implementation of "short capabilities." This approach has the disadvantage that it is somewhat vulnerable to certain kinds of hardware failures. Also, it requires that revocation be preplanned in much the same way as in other approaches to revocation. [ABSTRACT FROM AUTHOR]

In a two-processor distributed computer network, prior research showed that a maximum flow algorithm can be used to find optimal program-module-to-processor assignments to maximize the performance of distributed programs. This paper examines the sequence of optimal assignments found as the load on one processor is held fixed and the load on the other is varied. For every program module M there exists a critical load factor fM such that when the load on the processor with variable load is below fM, M is assigned to that processor by an optimal assignment, and is otherwise assigned to the other processor. This characteristic opens the possibility of doing optimal dynamic assignments in real-time. [ABSTRACT FROM AUTHOR]

It is desirable to have Distributed Database Management System whose behavior and control is as identical as possible to that used in signel site database management systems. Preserving the autonomy of sites which join a DDBMS network is essential to the peace of mind of its managers and users, and more technically, is essential in an environment where sites and communication lines fail. Redundant copies in a distributed system provide locality of reference for reads and the potential for parallel processing.

This paper deals with testing distributed software systems. In the past, two important problems have been determined for executing tests using a distributed test architecture: control/ability and observability problems. A coordinated test method has subsequently been proposed to solve these two problems. In the present article: 1) we show that controllability and observability are indeed resolved if and only if the test system respects some timing constraints, even when the system under test is non-real-time; 2) we determine these timing constraints; 3) we determine other timing constraints which optimize the duration of test execution; 4) we show that the communication medium used by the test system has not to be necessarily FIFO; and 5) we show that the centralized test method can be considered just as a particular case of the proposed coordinated test method. [ABSTRACT FROM AUTHOR]

This paper addresses some fault-tolerant issues pertaining to hierarchically distributed systems. Since each of the levels in a hierarchical system could have various characteristics, different fault-tolerance schemes could be appropriate at different levels. In this paper, we use stochastic Petri nets (SPN's) to investigate various fault-tolerant schemes in this context. The basic SPN is augmented by parameterized subnet primitives to model the fault-tolerant schemes. Both centralized and distributed fault-tolerant schemes are considered in this paper. These two schemes are investigated by considering the individual levels in a hierarchical system independently. In the case of distributed fault-tolerance, we consider two different checkpointing strategies. This first scheme is called the arbitrary checkpointing strategy. Each process in this scheme does its checkpointing independently; thus, the domino effect may occur. The second scheme is called the planned strategy. Here, process checkpointing is constrained to ensure no domino effect. Our results show that, under certain cases, an arbitrary checkpointing strategy can perform better than a planned strategy. Finally, we have studied the effect of integration on the fault-tolerant strategies of the various levels of a hierarchy. [ABSTRACT FROM AUTHOR]

Distributed file systems nowadays need to provide for fault tolerance. This is typically achieved with the replication of files. Existing approaches to the construction of replicated file systems sacrifice strong semantics (i.e., the guarantees the systems make to running computations when failures occur and/or files are accessed concurrently). This is done mainly for efficiency reasons. This paper puts forward a replicated file system protocol that enforces strong consistency semantics. Enforcing strong semantics allows for distributed systems to behave more like their centralized counterparts-an essential feature in order to provide the transparency that is so strived for in distributed computing systems. One fundamental characteristic of our protocol is its distributed nature. Because of it, the extra cost needed to ensure the stronger consistency is kept low since the bottleneck problem noticed in primary-copy systems is avoided, load balancing is facilitated, clients can, choose physically close servers, and the work required during failure handling and recovery is reduced. Another characteristic is that instead of optimizing each operation type on its own, file system activity was viewed at the level of a file session and the costs of individual operations were able to be spread over the life of a file session. We have developed a prototype and compared the performance of the prototype to both NFS and a nonreplicated version of the prototype that also achieves strong consistency semantics. Through these comparisons the cost of replication and the cost of enforcing the strong consistency semantics are shown. [ABSTRACT FROM AUTHOR]

We have noticed two problems with viewing a process as a sequence of events: The first problem is the complete loss of information about potential intra-process concurrency for both sequential and distributed computations, and partial loss of information about potential inter-process concurrency for distributed computations. The second problem is that the resulting reasoning framework does not lend itself to refinement (from sequential computing or a given set of distributed processes) to a preferable set of distributed processes. We argue that it is more natural to view a computation, either distributed or sequential, as a partially ordered set of events. Doing so leads to a view, called passive-space and time view, which we propose in this paper. In the proposed view, a point in space is a passive entity which does not order events that occur at it, and the order is determined by the interaction among the events. We define a relation, "Affects", between pairs of events, which captures the partial order on events. To aid users of the relation "Affects" in developing algorithms, we define vector clocks, that are global logical clocks, so that the relation "Affects", and hence all potential concurrency, between events can be identified from their timestamps assigned. Since this research is motivated by the need to solve practical problems, we define passive-space and time view such that a user has control, in two ways, over the costs involved. First, a process designer may choose any granularity of events and choose any mechanism for determining partial order among events on the process. Second, a user may choose a vector clock such that the extent of potential intra-process concurrency identified depends on the costs associated with the identification. We give vector clocks which trade cost incurred and concurrency identification. We compare the proposed view with the space and time view. Finally, we give a scheme for reducing the cost of communicating timestamps. [ABSTRACT FROM AUTHOR]

This paper describes a hybrid monitor for measuring the performance and observing the behavior of distributed systems during execution. Major problems are the interference of the monitoring system with the system to be monitored and the presentation of meaningful data to users. Monitoring becomes even more difficult in distributed systems since these systems feature asynchronous concurrent activities, nondeterministic behavior and lack central control, precise global time and accurate global state. We emphasize the data collection, analysis and presentation of execution data. A special hardware support, which consists of a test and measurement processor (TMP), was designed and has been implemented in the nodes of an experimental multicomputer system consisting of eleven nodes. The operations of the TMP are completely transparent with a minimal, less than 0.1 percent, overhead to the measured system. In the experimental system, all the TMP's were connected with a central monitoring station, using an in- dependent communication network, in order to provide a global view of the monitored system. The central monitoring station displays the resulting information in easy-to-read charts and graphs. Our experience with the TMP shows that it promotes an improved understanding of run-time behavior and performance measurements, to derive qualitative and quantitative assessments of distributed systems. [ABSTRACT FROM AUTHOR]

In this paper, we investigate dynamic transaction routing strategies for locally distributed database systems in which the database is partitioned and distributed among multiple transaction processing systems, and the incoming transactions are routed by a common front-end processor. In this environment, if a transaction issues a database request referencing a nonlocal database partition, the request has to be shipped to the system owning the referenced partition for processing. Various dynamic strategies are studied. Their performance is compared with that of the optimal static strategy. A new class of dynamic transaction routing strategies which take into account routing history and minimize the estimated response time of incoming transactions is proposed and found to provide a substantial improvement over the optimal static strategy. The robustness of the strategies is further studied through sensitivity analysis over various transaction loads, communication overheads and database reference distributions. [ABSTRACT FROM AUTHOR]

This paper illustrates an application of the system entity structure, a frame-like knowledge representation scheme, to the design of local area networks. An entity structure for a data link layer protocol that unifies many possibilities from the literature is introduced. The main concepts of our design methodology are illustrated using this example entity structure, and the underlying simulation environment is briefly discussed. The methodology aims to facilitate evaluation of a wide family of design alternatives and component combinations. [ABSTRACT FROM AUTHOR]

This paper illustrates an application of the system entity structure, a frame-like knowledge representation scheme, to the design of local area networks. An entity structure for a data link layer protocol that unifies many possibilities from the literature is introduced. The main concepts of our design methodology are illustrated using this example entity structure, and the underlying simulation environment is briefly discussed. The methodology aims to facilitate evaluation of a wide family of design alternatives and component combinations. [ABSTRACT FROM AUTHOR]

The IC* project is an effort to create an environment for the design, specification, and development of complex systems such as communication protocols, parallel machines, and distributed systems. The basis of this work is the IC* model of parallel computation. In this model, a system is specified by a set of invariant expressions which describe its behavior in time. The novel features of the model include temporal and structural constraints, inherent parallelism, explicit modeling of time, nondeterministic evolution, and dynamic activation. The project also includes the construction of a parallel computer specifically designed to support the model of computation. The model of computation, the status of the project, and the user environment are the content of this paper. [ABSTRACT FROM AUTHOR]

In today's distributed computing environment, the coordination of concurrent processes and the coordination of resource sharing are of critical importance. Consequently, much effort has been focused on the modeling of problems of coordination and concurrency. In this paper we describe a software environment (SPANNER) for the specification and analysis of such problems. In the SPANNER environment, one can formally produce a specification of a distributed computing problem, and then verify its "correctness" through reachability analysis and simulation. SPANNER is based on a finite state machine model called the selection/resolution model. We illustrate the capabilities of SPANNER by specifying and analyzing two classical coordination problems: 1) the dining philosophers; and 2) Dijkstra's concurrent programming problem. In addition to discussing these specific problems, our intention is also to focus on some of the more recently implemented capabilities of the SPANNER system such as process types and cluster variables. [ABSTRACT FROM AUTHOR]

The reliability of a distributed system depends on the reliabilities of its communication links and computing elements, as well as on the distribution of its resources, such as programs and data files. A useful measure of reliability in distributed systems is the terminal reliability between a pair of nodes which is the probability that at least one communication path exists between these nodes. An interesting optimization problem is that of maximizing the terminal reliability between a pair of computing elements under a given budget constraint. Analytical techniques to solve this problem are applicable only to special forms of reliability expressions. In this paper, three iterative algorithms for terminal reliability maximization are presented. The first two algorithms require the computation of terminal reliability expressions, and are therefore efficient for only small networks. The third algorithm, which is developed for large distributed systems, does not require the computation of terminal reliability expressions; this algorithm maximizes approximate objective functions and gives accurate results. Several examples are presented to illustrate the approximate optimization algorithm and an estimation of the error involved is also given. [ABSTRACT FROM AUTHOR]

Performance analysis studies of distributed database systems in the past have assumed that the message transmission time between any two nodes of a network is constant. They disregard the effect of communication network parameters such as network traffic, network topology, and capacity of transmission channels. In this paper, an analytical model is used to estimate the delays in transmission channels of the long haul network supporting the distributed database system. The analysis shows that the constant transmission time assumption cannot he justified in many cases, and that the response time is sensitive to the parameters mentioned above. Extensions and performance analysis in the context of interconnection networks are also discussed. [ABSTRACT FROM AUTHOR]

Computations of distributed systems are extremely difficult to specify and verify using traditional techniques because the systems are inherently concurrent, asynchronous, and nondeterministic. Furthermore, computing nodes in a distributed system may be highly independent of each other, and the entire system may lack an accurate global clock. In this paper, we develop an event-based model to specify formally the behavior (the external view) and the structure (the internal view) of distributed systems. Both control-related and data-related properties of distributed systems are specified using two fundamental relationships among events: the "precedes" relation, representing time order; and the "enables" relations, representing causality. No assumption about the existence of a global clock is made in the specifications. The specification technique has a rather wide range of applications. Examples from different classes of distributed systems, include communication systems, process control systems, and a distributed prime number generator, are used to demonstrate the power of the technique. The correctness of a design can be proved before implementation by checking the consistency between the behavior specification and the structure specification of a system. Both safety and liveness properties can be specified and verified. Furthermore, since the specification technique defines the orthogonal properties of a system separately, each of them can then be verified independently. Thus, the proof technique avoids the exponential state-explosion problem found in state-machine specification techniques. [ABSTRACT FROM AUTHOR]

This paper shows that graph traversal techniques have fundamental differences between serial and distributed computations in their behaviors, computational complexities, and effects on the design of graph algorithms. It has three major parts. Section 1 describes the computational environment for the design and description of distributed graph algorithms in terms of an architectural model for message exchanges. The computational complexity is measured in terms of the number of messages transmitted. Section II presents several distributed algorithms for the pure traversal, depth-first search, and breadth-first search techniques. Their complexities are also given. Through these descriptions are brought out some of the intrinsic differences in the behaviors and complexities of the fundamental traversal techniques between a serial and a distributed computation environment. Section III gives the distributed version of the Ford and Fulkerson algorithm for the maximum flow problem by means of depth-first search, the largest-augmentation search and breadth-first search. The complexities of these methods are found to be 0(f*¦A¦), 0((1 + logM/(M-1)f*)¦V¦¦A¦) and 0(¦V¦6), respectively, where f* is the maximum flow value of the problem, M is the maximum number of arcs in a cut, ¦V¦ is the number of vertices, and ¦A¦ is the number of arcs. Lastly, it is shown that the largest augmentation search may be a better method than the other two. This is contrary to the known results in serial computation. [ABSTRACT FROM AUTHOR]

The optimal distribution of a database schema over a number of sites in a distributed network is considered. The database is modeled in terms of objects (relations or record sets) and links (predefined joins or CODASYL sets). The design is driven by user-supplied information about data distribution. The inputs required by the optimization model are: 1) cardinality and size information about objects and links, 2) a set of candidate horizontal partitions of relations into fragments and the allocations of the fragments, and 3) the specification of all important transactions, their frequencies, and theft sites of origin. The paper develops an optimization model for a nonreplicated data allocation in the form of a linear integer zero-one programming problem; the objective function is the total transaction processing cost. To reduce the complexity, a decomposition heuristic is proposed. A replicated allocation is derived as a heuristic postoptimization of the optimal solution without replication. The model is demonstrated with a small sample database. The demonstration shows not only the feasibility of the approach but also increases one's insight into the distribution issues. The results were not immediately obvious but are explained in the final discussion. [ABSTRACT FROM AUTHOR]

This paper describes a method for the detection of properties of general graphs in an environment in which each node can be considered an autonomous processor, interacting with its neighbors by passing messages. These algorithms are decentralized in that they depend on no central controlling process nor on global storage. No node is required to know the configuration or extent of the graph, and no global clock is required. The algorithms are inherently asynchronous, and in general require execution time proportional to the diameter of the graph. [ABSTRACT FROM AUTHOR]

It is essential to assess the reliability of digital computer systems used for critical real-time control applications (e.g., nuclear power plant safety control systems). This involves the assessment of the design correctness of the combined hardware/software system as well as the reliability of the hardware. In this paper we survey methods of determining the design correctness of systems as applied to computer programs. Automated program proving techniques are still not practical for realistic programs. Manual proofs are lengthy, tedious, and error-prone. Software reliability provides a measure of confidence in the operational correctness of the software. Since the early 1970's several software reliability models have been proposed. We classify and discuss these models using the concepts of residual error size and the testing process used. We also discuss methods of estimating the correctness of the program and the adequacy of the set of test cases used. These methods are directly applicable to assessing the design correctness of the total integrated hardware/software system which ultimately could include large complex distributed processing systems. [ABSTRACT FROM AUTHOR]

The approach to requirements specification for embedded systems described in this paper is called "operational" because a requirements specification is an executable model of the proposed system interacting with its environment. The approach is embodied by the language PAISLey, which is motivated and defined herein. Embedded systems are characterized by asynchronous parallelism, even at the requirements level; PAISLey specifications are constructed by inter- acting processes so that this can be represented directly. Embedded systems are also characterized by urgent performance requirements, and PAISLey offers a formal, but intuitive, treatment of performance. [ABSTRACT FROM AUTHOR]

Distributed computing systems represent a wide variety of computer systems, ranging from a centralized star network to a completely decentralized computer system. The design of software for distributed computing systems is more complicated due to many design constraints and interactions of software components of the system. In this paper, the framework of an approach for developing the design specifications for a distributed software system is presented. In this approach, the data and functional components are considered separately and all interactions among the functional components are allowed only through the access of shared resources. A precise description of all aspects of software design, including the data and functional components, their structural relations, and interactions, is developed. A possible way of estimating the performance of the resultant software is suggested. Various examples are given to illustrate this approach. [ABSTRACT FROM AUTHOR]

The problem of system simulation is typically solved in a sequential manner due to the wide and intensive sharing of variables by all parts of the system. We propose a distributed solution where processes communicate only through messages with their neighbors; there are no shared variables and there is no central process for message routing or process scheduling. Deadlock is avoided in this system despite the absence of global control. Each process in the solution requires only a limited amount of memory. The correctness of a distributed system is proven by proving the correctness of each of its component processes and then using inductive arguments. The proposed solution has been empirically found to be efficient in preliminary studies. The paper presents formal, detailed proofs of correctness. [ABSTRACT FROM AUTHOR]

In a distributed computing system a modular program must have its modules assigned among the processors so as to avoid excessive interprocessor communication while taking advantage of specific efficiencies of some processors in executing some program modules. In this paper we show that this program module assignment problem can be solved efficiently by making use of the well-known Ford-Fulkerson algorithm for finding maximum flows in commodity networks as modified by Edmonds and Karp, Dinic, and Karzanov. A solution to the two-processor problem is given, and extensions to three and n-processors are considered with partial results given without a complete efficient solution. [ABSTRACT FROM AUTHOR]

In distributed databases, deadlocks may Occur due to conflicts in data file lockings. A system is in a deadlock if and only if there is a directed cycle in its demand graph. However, due to the inherent communication delay in a distributed system, it is not easy to construct a consistent demand graph for a distributed system. In this paper, three deadlock detection protocols are discussed. The first protocol uses two communication phases. The second protocol uses a single communication phase. Based on the second protocol, a one- phase hierarchical deadlock detection protocol is developed. [ABSTRACT FROM AUTHOR]

To provide continuity of operations in automated systems, there is a need to develop techniques that can make them reliable. Many systems such as used in space programs, air traffic control, nuclear plant monitors, ballistic missile defense and other demand robust operation. There is a need for research effort in the investigation of algorithms and system structures that make error/failure detection, reconfiguration, recovery and restart of a system feasible with the least amount of interruptions. A distributed system consists of a set of computers located in different sites connected by means of communications network.

The paper deals with the problem of scheduling the transmission of periodic processes in a distributed FieldBus system, defining the conditions guaranteeing correct transmission. The scheduling of periodic processes fixes the transmission times for each process in a table, whose length is equal to the Least Common Multiple (LCM) of all the periods. This involves great memorization problems when some periods are relatively prime. The authors identify the theoretical conditions which allow the length of the scheduling table to be drastically reduced, but still guarantee correct transmission. On the basis of the theoretical conditions given, the authors present a pre-run-time scheduling algorithm which determines a transmission sequence for each producing process within the desired scheduling interval. An online scheduling algorithm is also proposed to schedule new transmission requests which are made while the system is functioning. The reduction in the schedule length may increase the number of transmissions, thus reducing the effective bandwidth and increasing the communication overload. In order to make as complete an analysis as possible of the scheduling solution, the authors also present an analysis of both the computational complexity of the algorithms proposed and the communication overload introduced. [ABSTRACT FROM AUTHOR]

Distributed applications written in Hermes typically consist of a large number of sequential processes. The use of a hierarchy of process clusters can facilitate the debugging of such applications. Ideally, such a hierarchy should be derived automatically. This paper discusses two approaches to automatic process clustering, one analyzing runtime information with a statistical approach and one utilizing additional semantic information. Tools realizing these approaches were developed and a quantitative measure to evaluate process clusters is proposed. The results obtained under both approaches are compared, and indicate that the additional semantic information improves the cluster hierarchies derived. We demonstrate the value of automatic process clustering with an example. It is shown how appropriate process clusters reduce the complexity of the understanding process, facilitating program maintenance activities such as debugging. [ABSTRACT FROM AUTHOR]

In this paper we are concerned with the problem of determining the potential for load balancing in a distributed computing system. We define a precise measure, called the Number of Sharable Jobs, of this potential in terms of the number of jobs that can usefully be transferred across sites in the system. Properties of this measure are derived, including a general formula for its probability distribution, independent of any particular queuing discipline. A normalized version of the number of sharable jobs, called the Job Sharing Coefficient, is defined. From the general formula, the probability distribution of the number of sharable jobs is computed for three important queuing models and exact expressions are derived in two cases. For queuing models in which an exact expression for the probability distribution of the number of sharable jobs is difficult to obtain, two methods are presented for numerical computation of this distribution. The job sharing coefficient is plotted against traffic intensity for various values of system parameters. Both of these measures are shown to be useful analytic tools for understanding the characteristics of load sharing in distributed systems and can aid in the design of such systems. [ABSTRACT FROM AUTHOR]

Distributed computing systems are attractive due to the potential improvement in availability, fault-tolerance, performance, and resource sharing. Modeling and evaluation of such computing systems is an important step in the design process of distributed systems. In this paper, we present a two-level hierarchical model to analyze the availability of distributed systems. At the higher level (user level), the availability of the tasks (processes) is analyzed using a graph-based approach. At the lower level (component level), detailed Markov models are developed to analyze the component availabilities. These models take into account the hardware/software failures, congestion and collisions in communication links, allocation of resources, and the redundancy level. A systematic approach is developed to apply the two-level hierarchical model to evaluate the availability of the processes and the services provided by a distributed computing environment. This approach is then applied to analyze some of the distributed processes of a real distributed system, Unified Workstation Environment (UWE), that is currently being implemented at AT&T Bell Laboratories. [ABSTRACT FROM AUTHOR]

Replication techniques for transaction-based distributed systems generally achieve increased availability but with a significant performance penalty. We present a new replication paradigm, the location-based paradigm, which addresses availability and other performance issues. It provides availability similar to quorum-based replication protocols but with transaction-execution delays similar to one-copy systems. The paradigm further exploits replication to improve performance in two instances. First, it takes advantage of local or nearby replicas to further improve the response time of transactions, achieving smaller execution delays than one-copy systems. Second, it takes advantage of replication to facilitate the independent crash recovery of replica sites-a goal which is unattainable in one-copy systems. In addition to the above the location-based paradigm avoids bottlenecks, facilitates load balancing, and minimizes the disruption of service when failures and recoveries occur. In this paper we present the paradigm, a formal proof of correctness, and a detailed simulation study comparing our paradigm to one-copy systems and to other approaches to replication control. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the issues that must be addressed in the specification and generation of synthetic workloads for distributed real-time systems. We describe a synthetic workload specification language (SWSL) that defines a workload in a form that can be compiled by a synthetic workload generator (SWG) to produce an executable synthetic workload. The synthetic workload is then downloaded to the target machine and executed while performance and dependability measurements are made. SWSL defines the workload at the task level using a data flow graph, and at the operation level using control constructs and synthetic operations taken from a library. It is intended to be easy to use, flexible, and capable of creating synthetic workloads that are representative of real-time workloads. It provides a compact, parameterized notation. It supports automatic replication of objects to facilitate the specification of large workloads for distributed real-time systems. It also provides extensive support for the experimentation process. [ABSTRACT FROM AUTHOR]

In this paper we propose a dynamic load-balancing policy with a central job dispatcher called the LBC policy for distributed systems. The design of this policy is motivated by the operation of a single-queue multiserver queueing system. The average job response time of this policy is the same as that of a single-queue multiserver system, which is the best achievable performance when the communication delay is reduced to zero. Hence this policy is expected to provide near-minimum average job response time for distributed systems with high- speed communication subnets. The performance of this policy is studied for systems with non-negligible job transfer delays in the following three aspects: average job response time, overhead due to information exchanges, and sensitivity to heterogeneous load. Our results show that: (i) the average job response time of the LBC policy is near minimum when the mean job transfer delay is small (less than or equal to 5% of the mean job service time); (ii) the overhead due to exchanging information incurred by the LBC policy is comparable to that incurred by simple distributed load- balancing policies; and (iii) the performance of the LBC policy is insensitive to a heterogeneous load and therefore can adapt to changing load naturally. The commonly used decomposition technique fails to provide reasonable estimates of the average job response times for the LBC policy. A modified MIM/N model is developed to estimate the performance. This model gives accurate estimates (within 2%) of the average response times for mean job transfer delay up to 20% of the mean job service time. [ABSTRACT FROM AUTHOR]