PROTOB: An object-oriented case tool for modelling and prototyping distributed systems

The PROTOB object-oriented methodology for the executable specification of large-scale event-driven systems is introduced and described. Two supporting features of PROTOB are also presented: the graphic and textual language that formally describes the behaviour of objects, which is based on high-level Petri nets called “PROT nets” and which is demonstrated to be more powerful than SA/RT dataflows; and a CASE environment with tools for specification, modelling, simulation and prototyping. Use of PROTOB is illustrated by discussion of the automated generation of distributed systems running on a network of VMS and UNIX computers.     

DeViouS: A distributed environment for computer vision

Computer vision, owing to the size and complexity of its tasks and its importance to industrial and economic growth, was selected as one of the grand challenge problems by the U.S. Federal High Performance Computing Program. Integration of vision operations is identified as a key element of the challenge. A system to integrate computer vision in a distributed environment is presented here. This system, called DeViouS, is based on the client/server model and runs in a heterogeneous environment of Unix workstations. Modern computing environments include large numbers of high-powered workstations connected by a very fast network. Many of these computers are idle most of the time. DeViouS takes advantage of this feature of computing environments to distribute the execution of vision tasks. Two primary goals of DeViouS are to provide a practical distributed system and a research environment for vision computing. DeViouS is based on a modular design that allows experimentation in various aspects of algorithm design, scheduling and network programming. It can make use of any existing computer vision packages with very minor changes to DeViouS. DeViouS has been tested in an environment of SUN and Digital workstations and has shown substantial improvements in speed over sequential computing with negligible overhead.     

An environment for distributed prototyping of real time systems

Designing and reasoning about real-time systems are difficult activities, in which timing and reactive behaviour requirements add significant complexity to system validation. In this paper, a new technique for distributed prototyping of real-time systems is presented. It enables system prototypes to be concurrently developed and tested by a geographically distributed team, in such a way that each developer can validate his or her part of the system against the other parts which are being built in other development sites. A set of tools has been implemented that supports validation of functional and time behaviour through distributed animation of graphical prototypes with a consistent vision of simulated time.     

A distributed development environment for embedded software

The HAGAR project is building a high-performance disk controller. It is an embedded system for which many hundreds of thousands of lines of embedded software will have to be developed concurrently with the development of the hardware. We found existing methods for embedded software development, such as simulation and remote cross development, to be inadequate for us. To meet our special needs, we developed a distributed development environment that combines and extends the capabilities of existing methods while fixing their drawbacks. Our environment is based on a processor-pool architecture, in which multiple hardware sets are pooled and managed systematically. It supports embedded software development for many programmers at different sites. It allows for the emulation of non-existing hardware adaptor cards and for the integration of embedded software testing with hardware simulation. The environment provides a single system image, hiding many hardware and configuration details from its users. From the perspective of the programmers, our environment makes developing embedded software for special hardware systems as easy as developing application programs for a UNIX workstation.     

Abstractions for distributed programming

The StarMod language is designed to provide its users with abstractions for distributed computations. The language is based on Wirth's definition of a “module” as impiemented in Modula. The paper discusses abstraction mechanisms for distributed access control and scheduling: in addition, several examples are used to illustrate these concepts.     

An implementation of distributed shared memory

Shared memory is a simple yet powerful paradigm for structuring systems. Recently, there has been an interest in extending this paradigm to non-shared memory architectures as well. For example, the virtual address spaces for all objects in a distributed object-based system could be viewed as constituting a global distributed shared memory. We propose a set of primitives for managing distributed shared memory. We present an implementation of these primitives in the context of an object-based operating system as well as on top of Unix.     

The new mexico state university ring-star system: A distributed unix environment

A distributed version of the UNIX operations system is currently under development through a joint effort of New Mexico State University and the Hebrew University of Jerusalem. A microprocessor version of the UNIX kernel has been developed which will run on any PDP-11 or LSI-11 based processing element and allows processes to run in a UNIX ‘look-alike’ environment. Each process is fully transportable among all processors in the system. Although the preliminary version of the system was built in a star configuration, the system is currently being upgraded by the addition of a communication ring with 8-bit microprocessors as ring interface units. The current paper describes the software structure, the hardware structure and the communication protocol of the system.     

Remote database access in the distributed computing environment

This paper describes the design, implementation and testing of a set of software modules that are used for remote database access in a distributed computing environment. The goal of our research and development is to implement a client server model using Structured Query Language (SQL) functions in the Open Software Foundation's (OSF) distributed computing environment (DCE). This design is compared with another which simply uses the sockets application programming interface (API), running over the transmission control protocol/internet protocol (TCP/IP), and is implemented in subroutines that act similar to the remote procedure call (RPC) generated stub code. The prototypes for the remote SQL access project are implemented using an IBM RISC System/6000 (the client) running the AIX operating system and an IBM AS/400 (the server) running the OS/400 operating system. We selected the AS/400 for its database abilities, and the RISC System/6000 since the DCE software is available for it.     

Communication infrastructure in distributed scheduling

The emergence of distributed artificial intelligent (DAI) introduced a new approach to solve scheduling problems by a set of scheduling systems that interact with each other in the problem-solving process. In this paper, we describe a communication infrastructure to handle connection and communication between distributed Internet scheduling systems for distributed applications. First, we present an agent model of distributed scheduling systems where agents can communicate and coordinate activities with each other via an agent communication language. Then, we define the syntax and semantics for the agent communication languages, and negotiation mechanism. Following that, we discuss the design and development of the prototype for the multi-agent scheduling systems. We conclude with a discussion of communication issues for heterogeneous agent-based scheduling systems to solve distributed scheduling problems.     

Module reuse by interface adaptation

This paper describes a language called Nimble that allows designers to declare how the actual parameters in a procedure call are to be transformed at run time. Normally, programmers must edit an application's source in order to adapt it for reuse in some new context where the interfaces fail to match exactly (e.g. the parameters may appear in a different order, data types may not exactly match, and some data may need to be either initialized or masked out when the reusable module is integrated within a new application.) But Nimble allows programmers to adapt the interfaces of existing software without having to operate on the source manually. As a result, existing software may be easily reused in a broader range of applications, and software libraries do not need to store many variants of a component that differ only in how the interfaces are used. Nimble has been implemented on a variety of Unix hosts, and is part of a broader reuse project at the University of Maryland. Our current system is suitable for use either in conjunction with existing module interconnection languages, or stand-alone with C, Pascal and Ada source programs.     

An experiment in language design for distributed systems

This paper describes a recent experiment in the design, implementation and application of a programming language designed specifically for distributed systems. The fundamental nature of such systems is used in the derivation of an experimental language, which is described and illustrated. Having outlined an implementation, the project is evaluated and some of the more significant findings are reported. In particular, the paper discusses (and argues for) an explicit language facility for expressing the distribution of a program over an actual system.     

Markov-chain based reliability analysis for distributed systems

In a typical distributed computing system (DCS), nodes consist of processing elements, memory units, shared resources, data files, and programs. For a distributed application, programs and data files are distributed among many processing elements that may exchange data and control information via communication link. The reliability of DCS can be expressed by the analysis of distributed program reliability (DPR) and distributed system reliability (DSR). In this paper, two reliability measures are introduced which are Markov-chain distributed program reliability (MDPR) and Markov-chain distributed system reliability (MDSR) to accurately model the reliability of DCS. A discrete time Markov chain with one absorbing state is constructed for this problem. The transition probability matrix is employed to represent the transition probability from one state to another state in a unit of time. In addition to mathematical method to evaluate the MDPR and MDSR, a simulation result is also presented to prove its correction.     

An interpreter for LOTOS,a specification language for distributed systems

LOTOS is an executable specification language for distributed systems currently being standardized within ISO as a tool for the formal specification of open systems interconnection protocols and services. It is based on an extended version of Milner's calculus of communicating systems (CCS) and on ACT ONE abstract data type (ADT) formalism. A brief introduction to LOTOS is given, along with a discussion of LOTOS operational semantics, and of the executability of LOTOS specifications. Further, an account of a prototype LOTOS interpreter is given, which includes an interactive system that allows the user to direct the execution of a specification (for example, for testing purposes). The interpreter was implemented in YACC/LEX, C and Prolog. The following topics are discussed: syntax and static semantics analysis; translation from LOTOS external format to internal representation; evaluation of ADT value expressions and extended CCS behaviour expressions. It is shown that the interpreter can be used in a variety of ways: to recognize whether a given sequence of interactions is allowed by the specification; to generate randomly chosen sequences of interactions; in a user-guided generation mode, etc.     

An efficient distributed algorithm for finding all hinge vertices in networks

Let G=(V, E) be a graph with vertex set V of size n and edge set E of size m. A vertex v∈V is called a hinge vertex if there exist two vertices in V\{v} such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O(n ²) time complexity and O(m) message complexity. In particular, the total messages exchanged during the algorithm are at most 2m(log n+nlog n+1) bits.     

Beyond network simulators: Fostering novel distributed applications and protocols through extendible design

Simulation has been of paramount importance to the development of novel Internet protocols. Such an approach typically focuses on one of three domains: wireless and other link-layer technologies, routing protocols, and transport-layer mechanisms and protocols. Existing techniques can tackle well simulation at layers 2, 3 and 4 of the TCP/IP architecture, but are not flexible enough to appropriately deal with application-layer protocols. These require simulators that support the modeling of networks and components with different levels of abstraction. Simmcast is an object-oriented framework that focuses on the necessary flexibility for application-layer protocol research. A simulation can be developed by the simple extension of building blocks that closely resemble components of a real network such as hosts, links and routers. The internal complexity of these components, however, is hidden from the user, so he/she can focus on the implementation of the desired protocol characteristics. This paper describes the flexible simulation architecture proposed and instantiated through Simmcast, and draws lessons from our experience in designing, implementing and deploying it. We also present framework instances used to evaluate application-layer protocols, exemplifying how different kinds of simulations can be developed with Simmcast.     

Adaptive resource management for dynamic distributed real-time applications

The dynamic distributed real-time applications run on clusters with varying execution time, so re-allocation of resources is critical to meet the applications’s deadline. In this paper we present two adaptive recourse management techniques for dynamic real-time applications by employing the prediction of responses of real-time tasks that operate in time sharing environment and run-time analysis of scheduling policies. Prediction of response time for resource reallocation is accomplished by historical profiling of applications’ resource usage to estimate resource requirements on the target machine and a probabilistic approach is applied for calculating the queuing delay that a process will experience on distributed hosts. Results show that as compared to statistical and worst-case approaches, our technique uses system resource more efficiently.     

An environment for integrated development and evaluation of real-time distributed database systems

Real-time database systems must maintain consistency while minimizing the number of transactions that miss the deadline. To satisfy both the consistency and real-time constraints, there is the need to integrate synchronization protocols with real-time priority scheduling protocols. One of the reasons for the difficulty in developing and evaluating database synchronization techniques is that it takes a long time to develop a system, and evaluation is complicated because it involves a large number of system parameters that may change dynamically. This paper describes an environment for investigating distributed real-time database systems. The environment is based on a concurrent programming kernel that supports the creation, blocking, and termination of processes, as well as scheduling and interprocess communication. The contribution of the paper is the introduction of a new approach to system development that utilizes a module library of reusable components to satisfy three major goals: modularity, flexibility, and extensibility. In addition, experiments for real-time concurrency control techniques are presented to illustrate the effectiveness of the environment.This work was supported in part by ONR contract # NOOO14-88-K-0245, by DOE contract # DEFG05-88-ER25063, by CIT contract # CIT-INF-90-011, and by IBM Federal Systems Division.     

An optimal algorithm for distributed snapshots with causal message ordering

We present an optimal distributed algorithm to record a global state of a distributed system with causally ordered message delivery. The message complexity of our algorithm is O(n) bits where n is the number of processes in the system.     

Programming languages for distributed applications

Much progress has been made in distributed computing in the areas of distribution structure, open computing, fault tolerance, and security. Yet, writing distributed applications remains difficult because the programmer has to manage models of these areas explicitly. A major challenge is to integrate the four models into a coherent development platform. Such a platform should make it possible to cleanly separate an application’s functionality from the other four concerns. Concurrent constraint programming, an evolution of concurrent logic programming, has both the expressiveness and the formal foundation needed to attempt this integration. As a first step, we have designed and built a platform that separates an application’s functionality from its distribution structure. We have prototyped several collaborative tools with this platform, including a shared graphic editor whose design is presented in detail. The platform efficiently implements Distributed Oz, which extends the Oz language with constructs to express the distribution structure and with basic primitives for open computing, failure detection and handling, and resource control. Oz appears to the programmer as a concurrent object-oriented language with dataflow synchronization. Oz is based on a higher-order, state-aware, concurrent constraint computation model. Seif Haridi, Ph.D.: He received his Ph.D. in computer science in 1981 from the Royal Institute of Technology, Sweden. After spending 18 months at IBM T. J. Watson Research Center, he moved to the Swedish Institute of Computer Science (SICS) to form a research lab on logic programming and parallel systems. Dr. Haridi is currently the research director of the Swedish Institute of Computer Science. He has been an active researcher in the area of logic and constraint programming and parallel processing since the beginning of the eighties. His earlier work includes contributions to the design of SICStus Prolog, various parallel Prolog systems and a class of scalable cache-coherent multiprocessors known as Cache-Only Memory Architecture (COMA). During the nineties most of his work focused on the design of multiparadigm programming systems based on Concurrent Constraint Programming (CCP). Currently, he is interested in programming systems and software methodology for distributed and agent-based applications. Peter Van Roy, Ph.D.: He obtained an engineering degree from the Vrije Universiteit Brussel (1983), Masters and Ph.D. degrees from the University of California at Berkeley (1984, 1990), and the Habilitation à Diriger des Recherches from Paris VII Denis Diderot (1996). He has made major contributions to logic language implementation. His research showed for the first time that Prolog can be implemented with the same execution efficiency as C. He was principal developer or codeveloper of Aquarius Prolog, Wild_Life, Logical State Threads, and FractaSketch. He joined the Oz project in 1994 and is currently working on Distributed Oz. His research interests are motivated by the desire to provide increased expressivity and efficiency to application developers. Per Brand: He is a researcher at the Swedish Institute of Computer Science. He has previously worked on the design and implementation of OR-parallel Prolog (the Aurora project) and optimized compilation techniques for Concurrent Constraint Programming Languages (in particular, AKL). He has been a member of the Distributed Oz design team since the project began. His research interests are focused on techniques, languages, and methodology for distributed programming. Christian Schulte: He studied computer science at the University of Karlsruhe, Germany, from 1987 to 1992 where he received his diploma. Since 1992 he has been a member of the Programming Systems Lab at DFKI. He is one of the principal designers of Oz. His research interests include design, implementation, and application of concurrent and distributed programming languages as well as constraint programming.     

Concurrent intelligent rapid prototyping environment

Rapid prototyping technology enables rapid production of complex objects directly from a computer-aided design model without involving any tooling or conventional part programming. This has created a new set of problems associated with part design, process planning, support design and value engineering analysis of rapid prototyping parts. In this paper, a methodology for resolving these problems is described, which uses concurrent engineering, distributed blackboard, value engineering, knowledge-based and feature-based technologies. The functionality, design methodology and knowledge representation techniques of a concurrent intelligent rapid prototyping system for stereolithography form the main focus of this paper.