Faults such as link failures and high switch configuration delays can cause heavy congestion and packet loss. Because it takes time to detect and react to faults, these conditions can last long---even tens of seconds. We propose forward fault correction (FFC), a proactive approach to handling faults. FFC spreads network traffic such that freedom from congestion is guaranteed under arbitrary combinations of up to k faults. We show how FFC can be practically realized by compactly encoding the constraints that arise from this large number of possible faults and solving them efficiently using sorting networks. Experiments with data from real networks show that, with negligible loss in overall network throughput, FFC can reduce data loss by a factor of 7--130 in well-provisioned networks, and reduce the loss of high-priority traffic to almost zero in well-utilized networks.

In this paper we present a new system for making use of the cyles routinely wasted in local area networks. The Piranha system harnesses these cycles to run explicitly parallel programs. Programs written for Piranha are specializations of Linda master/worker programs [5]. We have used Piranha to run a number of production applications.

The architecture of a coprocessor that supports the communication primitives of the Linda parallel-programming environment in hardware is described. The coprocessor is a critical element in the architecture of the Linda machine, a MIMD (multiple-instruction, multiple-data-stream) parallel-processing system that is designed top-down from the specifications of Linda. Communication in Linda programs takes place through a logically shared associative memory mechanism called tuple space. The Linda machine, however, has no physically shared memory. The microprogrammable coprocessor implements distributed protocols for executing tuple-space operations over the Linda machine communication network. The coprocessor has been designed and is in the process of fabrication. The projected performance of the coprocessor is discussed and compared with software implementation of Linda.>

The Linda Machine is a parallel computer that has been designed to support the Linda parallel programming environment in hardware. Programs in Linda communicate through a logically shared associative memory called tuple space. The goal of the Linda Machine project is to implement Linda's high-level shared-memory abstraction efficiently on a nonshared-memory architecture. The authors describe the machine's special-purpose communication network and its associated protocols, the design of the Linda coprocessor, and the way its interaction with the network supports global access to tuple space. The Linda Machine is in the process of fabrication. The authors discuss the machine's projected performance and compare this to software versions of Linda.>

Symmetric Lisp is a programming language designed around first-class environments, where an environment is a dictionary that associates names with definitions or values. In this paper we describe the logical structure of the Symmetric Lisp interpreter. In other interpreted languages, the interpreter is a virtual machine that evaluates user input on the basis of its own internal state. The Symmetric Lisp interpreter, on the other hand, is a simple finite-state machine with no internal state. Its role is to attach user input to whatever environment the user has specified; such environments are transparent objects created by, maintained by and fully accessible to the user. The interpreter's semantics are secondary to the semantics of environments in Symmetric Lisp: it is the environment-object to which an expression is attached, not the interpreter, that controls the evaluation of expressions.This arrangement has several consequences. Because environments in Symmetric Lisp are governed by a parallel evaluation rule, the Symmetric Lisp interpreter is a parallel interpreter. A Symmetric Lisp environment evaluates to another environment; a session with the interpreter therefore yields a well-defined environment object as its result. Users are free to write routines that manage these interpreter-created objects - routines that list the elements of a namespace, coalesce environments, maintain multiple name definitions and so on precisely because environment objects may be freely inspected and manipulated. Because a named environment may contain other named environments as elements, interpreter-created objects may be regarded as hierarchical file systems. Because of the parallel evaluation semantics of environments, the interpreter is well-suited as an interface to a concurrent, language-based computer system that uses Symmetric Lisp as its base language. We argue that - in short - a basic semantic simplification in Symmetric Lisp promises a correspondingly basic increase in power at the user-interpreter interface.

We describe a programming language called Symmetric Lisp that treats environments as first­class objects. Symmetric Lisp allows programmers to write expressions that evaluate to environments, and to create and denote variables and constants of type environment as well. One consequence is that the roles filled in other languages by a variety of limited, special purpose environment forms like records, structures, closures, modules, classes and abstract data types are filled instead by a single versatile and powerful structure. In addition to being its fundamental structuring tool, environments also serve as the basic functional object in the language. Because the elements of an environment are evaluated in parallel, Symmetric Lisp is a parallel programming language; because they may be assembled dyamically as well as statically, Symmetric Lisp accomodates an unusually flexible and simple (parallel) interpreter as well as other history­sensitive applications requiring dynamic environments. We show that first­class environments bring about fundamental changes in a language's structure: conventional distinctions between declarations and expressions, data structures and program structures, passive modules and active processes disappear. We argue that the resulting language is clean, simple and powerful.

A distributed data structure is a data structure that can be manipulated by many parallel processes simultaneously. Distributed data structures are the natural complement to parallel program structures, where a parallel program (for our purposes) is one that is made up of many simultaneously active, communicating processes. Distributed data structures are impossible in most parallel programming languages, but they are supported in the parallel language Linda and they are central to Linda programming style. We outline Linda, then discuss some distributed data structures that have arisen in Linda programming experiments to date. Our intent is neither to discuss the design of the Linda system nor the performance of Linda programs, though we do comment on both topics; we are concerned instead with a few of the simpler and more basic techniques made possible by a language model that, we argue, is subtly but fundamentally different in its implications from most others.This material is based upon work supported by the National Science Foundation under Grant No. MCS-8303905. Jerry Leichter is supported by a Digital Equipment Corporation Graduate Engineering Education Program fellowship.

Linda is a parallel programming language that differs from other parallel languages in its simplicity and in its support for distributed data structures. The S/Net is a multicomputer, designed and built at AT&T Bell Laboratories, that is based on a fast, word-parallel bus interconnect. We describe the Linda-supporting communication kernel we have implemented on the S/Net. The implementation suggests that Linda's unusual shared-memory-like communication primitives can be made to run well in the absence of physically shared memory; the simplicity of the language and of our implementation's logical structure suggest that similar Linda implementations might readily be constructed on related architectures. We outline the language, and programming methodologies based on distributed data structures; we then describe the implementation, and the performance both of the Linda primitives themselves and of a simple S/Net-Linda matrix-multiplication program designed to exercise them.

A network computer is a collection of computers designed to function as one machine. On a network computer, as opposed to a multiprocessor, constituent subcomputers are memory-disjoint and communicate only by some form of message exchange. Ensemble architectures like multiprocessors and network computers are of growing interest because of their capacity to support parallel programs, where a parallel program is one that is made up of many simultaneously-active, communicating processes. Parallel programs should, on an appropriate architecture, run faster than sequential programs, and, indeed, good speed-ups have been reported in parallel programming experiments in several domains, amongst which are AI, numerical problems, and system simulation. Our interest lies in network computers, particularly ones that range in size from several hundred nodes to several thousand.

No abstract available.

Staged circuit switching (SCS) is a message-switching technique that combines a new protocol with new communication hardware. Protocol and hardware are designed specifically for networks that are intended to function as integrated general-purpose MIMD machines, i.e., for "network computers."

Generative communication is the basis of a new distributed programming langauge that is intended for systems programming in distributed settings generally and on integrated network computers in particular. It differs from previous interprocess communication models in specifying that messages be added in tuple-structured form to the computation environment, where they exist as named, independent entities until some process chooses to receive them. Generative communication results in a number of distinguishing properties in the new language, Linda, that is built around it. Linda is fully distributed in space and distributed in time; it allows distributed sharing, continuation passing, and structured naming. We discuss these properties and their implications, then give a series of examples. Linda presents novel implementation problems that we discuss in Part II. We are particularly concerned with implementation of the dynamic global name space that the generative communication model requires.

Staged circuit switching (SCS) is a message-switching technique that combines a new protocol with new communication hardware. Protocol and hardware are designed specifically for networks that are intended to function as integrated, general-purpose MIMD machines, i.e. for "network computers".

Design and implementation of an inter-address-space communication mechanism for the SBN network computer are described. SBN's basic communication primitives appear in context of a new distributed systems programming language strongly supported by the network communication kernel. A model in which all communication takes place via a distributed global buffer results in simplicity, generality and power in the communication primitives. Implementation issues raised by the requirements of the global buffer model are discussed in context of the SBN impementation effort.

Store-and-forward deadlock (SFD) occurs in packet- switched computer networks when, among some cycle of packets buffered by the communication system, each packet in the cycle waits for the use of the buffer currently occupied by the next packet in the cycle. Several techniques for the prevention of SFD are known, but all exact some cost in terms of efficient and flexible packet handling. An ideal SFD-prevention technique is as unobtrusive as possible; it imposes no routing restrictions on packets, does not require that the buffer pool on each node grow with network size, and imposes no buffer-pool partitioning. All SFD-prevention techniques described so far lack some or all of these desirable properties. The new algorithm here described has all of them; in return, it imposes other unconventional costs. Under certain circumstances it requires that packets be rerouted around areas of potential deadlock, and one arbitrarily chosen node is required to accept within finite time any packet seeking entrance to its buffer pool, even if this requires erasing some packet. It is argued nonetheless that these costs are imposed infrequently enough and are sufficiently well manageable by heuristic techniques to make this new algorithm an attractive and practical alternative to the older techniques. An implementation designed for a microprocessor network now under construction is described.