Analyzing the performance of finite buffered multistage networks has been considered a difficult task because of dynamic blocking effects due to finite sized buffers. With the multistage networks enhanced with combining capability, in which multiple requests directed to a shared location combine together to form a single request to be forwarded, the analysis becomes even more difficult due to the interactions between combining probability and queuing delay. Performance bounds for combining networks are known under two extreme assumptions: infinite combining queues and saturated finite combining queues. We analyze multistage combining networks with the consideration of blocking due to finite combining queues. Our analysis provides iterative solutions for combining probability, blocking probability, and queuing delay.>

A rollback recovery scheme for distributed systems is proposed. The state-save synchronization among processes is implemented by bounding clock drifts such that no state-save synchronization messages are required. Since the clocks are only loosely synchronized, the synchronization overhead can be negligible in many applications. An interprocess communication protocol which encodes state-save progress information within message frames is introduced to checkpoint consistent system states. A rollback recovery algorithm that will force a minimum number of nodes to roll back after failures is developed.>

The paper presents the results of an experiment measuring Ethernet performance using station monitoring. In station monitoring the network measurements are performed internal to the stations, thus enabling the collection of delay information unavailable to typical spying network monitors. The experimental measurements are compared against similar measurements made using Ethernet simulation of the same network. The data show that measured performance differs significantly from predictions made by typical analytical and simulation models. The results have implications for the underlying assumptions used in simulation and modeling and on the use of spying monitors.>

It is shown that voting can provide the maximum reliability if all nodes have reliability p>or=0.5. Thus, a system designer only needs to consider vote assignments in implementing mutual exclusion mechanisms. Some effective vote assignment algorithms are proposed. Neglecting link failures, it is found that the voting weight for each node can be determined by computing a logarithmic function of local information. Voting operations are formally defined, and an optimization objection function is formulated. A sufficient condition for optimal vote assignment and optimal sets of groups is presented, and it is shown that predefining a set of groups to achieve mutual exclusion is not feasible for a large system. Some algorithms generating optimal or suboptimal assignments for systems with perfect links are proposed. Some variations for systems with imperfect links are discussed, along with some comparisons of the new algorithms against previous algorithms proposed for the problem.>

A major obstacle in implementing a rollback recovery scheme for fault tolerance in a concurrent distributed system is the domino effect. A low overhead checkpointing scheme is proposed to prevent this effect. Each process saves its state periodically. The state-save synchronization among processes is implemented by bounding clock drifts. A communication protocol that assures that all saved states are consistent is developed.>

Majority voting is commonly used in distributed computing systems to control mutual exclusion, and in fault-tolerant computing to achieve reliability. Different vote assignments may result in different reliabilities. The authors present vote assignment algorithms aimed at maximizing the reliability. In their approach the voting weight assigned to each node is readily determined if the link failure rate is negligible. For systems having imperfect links a heuristic algorithm is proposed. Simulation studies show that the algorithm can approximate optimal assignments quite well in small systems.>

The authors consider the placement of heterogeneous modules to minimize the expected value of the distance required for an intermodule communication, where the expectation is taken with respect to a given matrix of intermodule communication probabilities. One way the placement problem could be simplified would be to select a 'footprint' with the property that all modules of the optimum placement occupy locations in the footprint, and there are no vacancies within the footprint region. If such footprints were known, they could be precomputed for each system size and the optimization problem would be reduced to a search of placements meeting the footprint constraint. However, it is shown that a footprint does not exist for the placement problem with the objective of minimizing the expected communication distance.>

Public descriptions of capability-based system designs often do not clarify the necessary details concerning the propagation of access rights within the systems. A casual reader may assume that it is adequate for capabilities to be passed in accordance with the rules for data copying. A system using such a rule cannot enforce either the military security policy or the Bell and LaPadula rules. The paper shows why this problem arises and provides a taxonomy of capability-based designs. Within the space of design options defined by the taxonomy we identify a class of designs that cannot enforce the Bell-LaPadula rules and two designs that do allow their enforcement.

Public descriptions of capability-based system designs often do not clarify the necessary details concerning the propagation of access rights within the systems. A casual reader may assume that it is adequate for capabilities to be psssed in accordance with the rules for data copying. A system using such a rule cannot enforce either the military security policy or the Bell and LaPadula rules. The paper shows why this problem arises and provides a taxonomy of capability-based designs. Within the space of design options defined by the taxonomy we identify a class of designs that cannot enforce the Bell-LaPadula rules and two designs that do allow their enforcement.

In a recent paper, Lam and Lien described an algorithm called tree-convolution that can reduce the space and computation time required for evaluating sparse multiclass, product-form queueing networks. In this paper, we develop an exact algorithm based on mean value analysis (MVA) that is the counterpart of the tree-convolution algorithm. The order of reduction in storage and computation achieved by our new Tree-MVA algorithm compared to the standard MVA algorithm is the same order of reduction obtained by the tree-convolution algorithm over that of the standard convolution algorithm. Our Tree-MVA algorithm preserves the inherent simplicity of MVA based algorithms.

We describe a new technique for accessing a shared bus in a distributed computing environment. The load balancing bus accessing scheme can be modeled by a new station type that can be incorporated in a BCMP multiple class queueing network model of the distributed system. We show one simple means of implementing the load balancing scheme.

We introduce a scheme for passive node-level fault detection in a distributed system. With each system node associate a low-cost, low-complexity observer which monitors the pattern of incoming and outgoing messages and compares it against an abstracted model of the node's behavior. We develop a fault detection procedure, which is probabilistic because of nondeterminism in the simplified node model. Abstraction reduces model complexity, but renders some errors undetectable by the observer. In the paper we characterize these undetectable errors. Succeeding studies show how to select model abstractions to lower the number of undetectable errors.

Consider a queueing system in which customers (or jobs) arrive to one of Q separate queues to await service from one of S identical servers (Figure 1). Once a job enters a queue it does not leave that queue until it has been selected for service. Any server can serve any job from any queue. A job selected for service cannot be preempted. In this paper we consider jobs to be in a single class; for the multiple class result see [AFSH81a]. We assume once a queue has been selected, job scheduling from that queue is fair. In particular, our results hold for first come first serve as well as random selection [SPIR79] and, for that matter, any fair nonpreemptive scheduling policy within a queue. We assume that arrivals to each queue follow a Poisson process with the mean arrival rate to queue q being λq. The S identical exponential servers are each processing work at a mean rate of μ.

This paper discusses the issues involved in building a real-time control system using a message-directed distributed architecture. We begin with a discussion of the nature of real-time soft ware, including the viability of using hierarchical models to organize the software. Next we discuss some realistic design objectives for a distributed real-time system including fault isolation, independent module verification, context independence, decentralized control and partitioned system state. We conclude with some observations concerning the general nature of distributed system software.

This paper describes the kernel of an Executive being implemented for the Honeywell Experimental Distributed Processor (HXDP) -- a vehicle for research in distributed computers for real-time control. The kernel provides message transmission primitives for use by application programs or higher level executive functions. In the paper we describe the message transmission primitives provided by the kernel and the rationale for their selection based upon the objectives and constraints described in a companion paper.

M3 is intended for research into unconventional special purpose stored program elements of computer systems (for example, a distributed computer Bus Interface Unit). The principal requirements for such a machine are flexibility and modularity. M3 consists of an application independent Kernel Machine to which application-dependent Functional Modules are attached. The Kernel Machine is vertically microprogrammed; it includes highly capable microinstruction sequencing logic which facilitates structured microprogramming. The Functional Modules contain the operand registers and the operators (e.g., adders, shifters, etc.) needed by the specific application. The operators may be invoked not only by the Kernel Machine but also by one another; control may be passed among operators in a sequential or hierarchical fashion; operators may execute concurrently with each other and with the Kernel Machine; operators may be re-entrant or recursive; operators may activate themselves, or cause microcode interrupt routines to be executed in the Kernel Machine.

The designer of a virtual memory system can obtain accurate estimates of the average memory requirements of programs running in the system by weighting the average allocation during execution intervals with the average allocation during page waiting intervals. We show how to combine the averages, how to use the measure to determine the size of primary memory while achieving system balance between memory and processor demands, and how to partially order the performance of paging algorithms.

Analytic models are developed to evaluate the performance of a multiprocessor computer system. Markov chain techniques are used to model memory conflicts when the memory is modularized. The instruction execution rate (IER) is chosen as the measure of performance. The performance is studied with different storage allocations for instructions and data and with interleaving in the instruction space.

Efficient memory management is important for optimizing computer usage. Intuition, simulation, experience, and analysis have contributed to the design of space management algorithms. Analytical models require accurate and concise descriptions of the system's environment. The referencing pattern, describing the sequence of memory addresses, is the environment for memory management problems. One referencing model assigns probabilities to positions in an LRU stack of memory pages. “Local” behavior is easily described using this model. However, the distinctly different behavior among instruction and data references is lost. In this paper we generalize the LRU stack model to an arbitrary number of memory spaces which are selected by the transitions of a Markov chain. The additional detail affects the behavior of the models for a working set management strategy.

The techniques for switching circuit synthesis rely heavily on the representations of the signals in the network. In this note a field-element representation and some synthesis techniques are discussed. An advantage of using field-element representations is that algebraic manipulations can be performed on the descriptions, simplifying some minimization problems. The networks which are minimized use components which perform operations on field elements. This representation may be useful for describing some of the problems which arise in larger interconnections of logical circuits.

Hughes [1] presented some curves relating the mean performance of a pattern classifier averaged over all pattern recognition problems of given complexity, when there are two classes of patterns to be distinguished. In this correspondence the mean recognition probability is computed for the case ofqpattern classes when the a priori probabilities of the classes are equal. When the a priori probabilities are unequal, the mean performance will improve over the performance with equal a priori probabilities, so these curves provide a lower bound to the performance of recognizers with more than two pattern classes. Some comments on the appropriateness of these statistics to common recognition problems are made.

IN this paper we will describe an algorithm for the decomposition of UP-DOWN counters. The constituents of the decomposed counters will be UP-DOWN counters of small modulus and small amounts of combinatorial logic. The main advantage accruing from this decomposition technique is that only a small number of building blocks is required to build counters with any modulus. We will begin the discussion by developing analysis techniques for particular interconnections of UP-DOWN counters. Following this, a general technique for the synthesis of an UP-DOWN counter with any modulus will be given. Only binary and ternary UP-DOWN counters and a small amount of combinatorial logic will be required.