Technical Reports and MS Project Reports

Mobile computing is emerging as an important new paradigm which has the potential to reshape our thinking about distributed computation. Mobility has far-reaching implications on what designers and users can assume about communication patterns, resource availability, and applciation behaviors as components move from one location to another while joining or leaving groups of other components in their vicinity. New distributed algorithms are likely to be required as the nature of applications shifts with the emergence of this new kind of computing environment. Formal methods have an important role to play ...Read More

Mobile computing represents a major point of departure from the traditional distributed computing paradigm. The potentially very large number of independent computing units, a decoupled computing style, frequent disconnections, continuous position changes, and the location-dependent nature of the behavior and communication patterns of the individual components present designers with unprecedented challenges in the areas of modularity and dependability. This paper describes two ideas regarding a modular approach to specifying and reasoning about mobile computing. The novelty of our approach rests with the notion of allowing transient interactions among programs which ...Read More

This paper describes the design of the ACE object-oriented thread encapsulation class library. The architecture of this class library is presented from an end-user and internal design perspective and several key design issues are discussed. Readers should gain an understanding of the overall design approach as well as the tradeoffs between various software quality factors such as performance, portability, and extensibility.

The algorithmic analysis, data collection, and statistical analysis required to isolate the cause of time variability observed while an Elman style recurrent neural network is trained in parallel on a twenty processor SPARCcenter 2000 is described in detail. Correlations of system metrics indicate the operating system scheduler or an interaction of kernel processes is the most probable explanation for the variability.

The Programmers' Playground is a programming environment that supports end-user construction of distributed multimedia applications. The system implements a new programming model that is based, in part, upon ideas from the formal I/O automaton model of Lynch and Tuttle. Important features of The Programmers' Playground are a separation of communication and computation and graphical support for dynamic reconfiguration. This paper provides a formal specification of the Playground programming model and runtime system in terms of the I/O automaton model on which it is based. Exploiting the compositionality properties of the ...Read More

Asynchronous Transfer Mode (ATM) network technology is expected to become a central part of the emerging global information infrastructure. ATM networks introduce a number of features that distinguish them from earlier technologies and introduce new issues in network control. This paper offers a framework for precisely defining and analyzing alternative approaches to the distributed control of ATM networks and explores some of the key design issues through a series of examples. It is hoped that it will provide a useful foundation for researchers in networking and distributed computing interested in ...Read More

This report analyzes two popular heuristics for ensuring packet integrity in ATM switching systems. In particular, we analyze the behavior of packet tail discarding, in order to understand how the packet level link efficiency is dependent on the rates of individual virtual circuits and the degre of the imposed overload. In addition, we study early packet discard and show that the queue capacity needed to achieve high efficiency under worst-case conditions grows with the number of virtual circuits and we determine the efficiency obtainable with more limited queue capacities. Using ...Read More

As ATM becomes widely accepted as the communication standard for high speed networks, the signaling system structure and protocols that support ATM become more and more important. To support existing, future and unknown applications, the signalign system has to be very flexible and efficient. In this paper we define the signaling problem, present several possible signaling system structures, compare the advantages and disadvantages of these systems, and then we propose a new signaling system structure. The fundamental idea of the new signaling system is the logical separation of the signaling ...Read More

Abstract Network signaling is the process of transferring control information among components of a communication network to establish, maintain, and release connections, and to pass the network management information. The rapid evolution in the field of telecommunications has led to the rapid evolution of network signaling. In this paper, we review the evolution of network signaling. We emphasize the concepts and protocols used in modern fast packet switching networks especially in emerging ATM networks.

We have developed and tested an automated method for simultaneous 3D tracking of numerous, flourescently-tagged cells. The procedure uses multiple thresholding to segment individual cells at a starting timepoint, and then iteratively applies a template-matching algorithm to locate a particular cell's position at subsequent time points. To speed up the method, we have developed a distributed implementation in which template matching is carried out in parallel on several different server machines. The distributed implementation showed a monotonic decrease in response time with increasing number of servers (up to 15 tested), ...Read More

We first present an algorithm that uses membership and equivalence queries to exactly identify a discretized geometric concept defined by the unioin of m axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. This algorithm receives at most md counterexamples and uses time and membership queries polynomial in m and log(n) for any constant d. Furthermore, all equivalence queries can be formulated as the union of O(mdlog(m)) axis-parallel boxes. Next, we show how to extend our algorithm to efficiently learn, from only equivalence queries, ...Read More

Large scale multimedia storage servers will be an integral part of the emerging distributed multimedia computing infrastructure. However, given the modest rate of improvements in storage transfer rates, designing servers that meet the demands of multimedia applications is a challenging task that needs significant architectural innovation. Our research project, called Massively-parallel And Real-time Storage (MARS) architecture, is aimed at the design and prototype implementation of a large scale multimedia storage server. It uses some of the well-known techniques in parallel I/O, such as data striping and Redundant Arrays of Inexpensive ...Read More

This document specifies a Connection Management Access Protocol (CMAP) for call management in high-speed packet switched networks. We target CMAP to networks employing the Asynchronous Transfer Mode (ATM) communication standard. CMAP specifies the access procedues exercised by network clients to manipulate multipoint calls; it is thus a User-Network Interface (UNI) signalling protocol. We define a multipoint call as a group of multipoint connections. A multipoint connection is a communication channel between two or more clients or endpoints of the network, where all data sent by one client is received by ...Read More

The Pavane program visualization system is an implementation of the declarative paradigm of visualization. After a brief report on the status of the Pavane implementation, we present the results of an evaluation of the usability of Pavane. This evaluation is based on the use of Pavane by its developers to construct program visualizations, on its use in a classroom setting as a tool for examining executing programs, and on its application to some simple scientific visualizations.

The problem this paper addresses is how to modify an existing operating system's I/O subsystem to support new high-speed networks and high-bandwidth multimedia applications that will play an important role in future computing environments. The proposed I/O subsystem is called universal continuous media I/O (UCM I/O). This paper will cover the preliminary design of UCM I/O, some of the trade-offs and issues that need to be addressed in order to implement UCM I/O, and a summary of work in progress.

The last few years have seen network data rates skyrocket from a few Mbps to a Gbps or more. However, a lack of integration of the host-netowrk interface, the operating system, and network protocols has resulted in end-applications seeing only a small fraction of this total bandwidth being available for data transfer. The emergence of demanding applications in the realms of multimedia and virtual reality provides further impetus in the drive to overcome this problem. In this paper, we present the design of a high performance ATM host-network interface for ...Read More

In asynchronous systems, average function delays principally govern overall throughput. This paper compares the performance of six adder designs with respect to their average delays. Our results show that asynchronous addres (32 or 64-bits) with a hybrid structure (e.g., carry-select addres) run 20-40% faster than simple ripple-carry addres. Hybrid adders also outperform high-cost, strictly synchronous conditional-sum adders.

In this paper, a set of simple, general, yet practical performance models for RISC architectures are developed. These models apply to a wide range of systems that include both pipelined and superscalar systems operating in either clocked or asynchronous environments. The models permit quantitative evaluation of various design choices (e.g., the number of pipelines in the system, the pipeline depth, and the choice between clocked and asynchronous methodologies) as functions of technology parameters, environmental operating parameters, and pipeline function characteristics. Design curves are presented indicating optimal pipeline depth and number ...Read More

One view of computational learning theory is that of a learner acquiring the knowledge of a teacher. We introduce a formal model of learning capturing the idea that teachers may have gaps in their knowledge. The goal of the learner is still to acquire the knowledge of the teacher, but now the learner must also identify the gaps. This is the notion of learning from a consistently ignorant teacher. We consider the impact of knowledge gaps on learning, for example, monoton DNF and d-dimensional boxes, and show that leraning is ...Read More

Developing the ability to recognize a landmark from a visual image of a robot's current location is a fundamental problem in robotics. We consider the problem of PAC-learning the concept class of geometric patterns where the target geometric pattern is a configuration of k points on the real line. Each instance is a configuration of n points on the real line, where it is labeled according to whether or not it visually resembles the target pattern. To capture the notion of visual resemblance we use the Hausdorff metric. Informally, two ...Read More

Many new network applications demand interprocess communication (IPC) services that are not supported by existing transport protocol mechanisms. Large bandwidth-delay products of high-speed networks also render the existing control mechanisms such as flow and error control less efficient. In particular, new error control schemes that can provide variable degrees of error recovery according to the applications requirements are needed. This paper presents the design, evaluation, and implementation of an application-oriented error control scheme that is aimed at supporting efficient IPC in high-speed networking environments. Our results show that the proposed ...Read More

This report describes our approach towards providing quality of service (QoS) guarantees for network communication within the endsystems to support multimedia applications. We first address the problem of QoS specification by identifying a set of application classes and their QoS parameters that cover the communication requirements of most applications. We then describe the QoS mapping problem, and show how requirements for resources (such as the CPU, the network interface adaptor and network connections) can be automatically derived from the application QoS parameters. We then deal with the QoS enforcement issue ...Read More

Communication latencies and delays are a major source of performance degradation in parallel computing systems. It is importnat to "mask" these communication delays by overlapping them with useful computation in order to obtain good parallel performance. This paper proposes speculative computation as a technique to mask communication latencies. Speculative computation is discussed in the context of synchronous iterative algorithms. Processors speculate the contents of messages that are not hyet received and perform computation based on the speculated values. When the messages are received, they are compared with the speculated values ...Read More

We investigate the problem of transforming one binary tree into another by rotatoins, subject to certain weight ocnstraints on the nodes of the trees. These constraints arise in the problem of "morphing" one simple polygon to another simple polygon by continuous deformatinos (translations and scalings) that preserve the turn angles and the simplicity of the polygon; the two polygons must have the same sequence of turn angles. Our main theorem is that two arbitrary n-leaf binary trees satisfying our weight constraint can be morphed into each other with O(n log ...Read More

We propose a n extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions. Given a convex polytope P with n vertices and two points p,q on its surface, let dp (p,q) denote the shortest path distance between p and q on the surface of P. Our algorithm produces a path of length at most 2 × dp(p,q) in time O(n). Extending this results, we can also compute ana pproximation of the shortest path tree rooted at an arbitrary point χ Є ...Read More

TRAINREC is a system for training feedforward and recurrent neural networks that incorporates several ideas. It uses the conjugate-gradient method which is demonstrably more efficient than traditional backward error propagation. We assume epoch-based training and derive a new error function having several desirable properties absent from the traditional sum-of-squared-error function. We argue for skip (shortcut) connections where appropriate and the preference for a sigmoidal yielding values over the [-1,1] interval. The input feature space is often over-analyzed, but by using singular value decomposition, input patterns can be conditioned for better ...Read More

Traditional computation models such as Turing machines, lambda-calculus, Markov's normal algorithms, are not suitable models for visual programming languages because they are all based on one-dimensional text strings and visual programming uses two-dimensional graphic diagrams. We propose a two-dimensional computation model, called Boxgraph, that requires no text. The syntax of the model consists of nested boxes connected by arrows, and the semantics consists of dataflow and the concept of consistency. The expressive power of the model is demonstrated by constructing representations of a binary full adder, the Fibonacci function, and ...Read More

We consider the concept classes of DNF formulas and unions of discretized, axis-parallel d-dimensional boxes in discretized d-dimensional space with respect to several different learning models. In the model of learning with queries we present an algorithm to learn unions of boxes. We introduce a model of teaching that prevents illicit communication between the teacher and the leaner but that captures the intuitive aspect of teaching: a learner should perform at least as well with a cooperative teacher as with an adversarial teacher. We propose the study of teaching of ...Read More

Two concurrent implementations of the method of conjugate gradients for training Elman networks are discussed. The parallelism is obtained in the computation of the error gradient and the method is therefore applicable to any gradient descent training technique for this form of network. The experimental results were obtained on a Sun Sparc Center 2000 multiprocessor. The Sparc 2000 is a shared memory machine well suited to coarse-grained distributed computations, but the concurrency could be extended to other architectures as well.

We present a visual specification language for constructing distributed applications and their direct manipulation graphical user interfaces. Each distributed application consists of a collection of independent modules and a configuration of logical connections that define communication among the data interfaces of the modules. Our specification language uses a single visual mechanism that allows end-users to define interprocess communication among distributed modules and to define intraprocess communication among objects within a module. This seamless specification provides a general encapsulation/abstraction mechanism and is designed to support dynamic change to the communication structure. ...Read More

The Washington University MultiMedia eXplorer (MMX) is a complete, host-independent multimedia system capable of transmitting and receiving JPEG-compressed video, CD-quality audio, and high-resolution radiographic images over the Washington University broadband ATM network. If the host is equipped with an ATM interface card, normal network traffic can be supported via an ATM extension port on the MMX. The major components of the MMX are an ATMizer and three multimedia channels. The ATMizer implements the host interface, the interface to the ATM network, and hte interface to the three multimdeia channels. This ...Read More

Formal methods hold the promise for high dependability in the design of critical software. However, software engineers who employ formal methods need to communicate their design decisions to users, customers, managers, and collegues who may not be in a position to acquire a full understanding of the formal notation being used. Visualizations derived from formal specifications and designs must be able to convey the required information precisely and reliably without the use of formal notation. This paper discusses a design methodology which attempts to integrate a design methodology based upon ...Read More

The Programmer's Playground takes a new approach to simplifying and supporting the construction of distributed applications. The approach, called I/O abstraction, separates the description of a system's communication structure from the descriptions of its computational components so that software modules written in existing programming languages cna be integrated flexibly and dynamically by both programmers and end-users. This separation is achieved by estabishing logical connectinos among the data interfaces of independent software modules. The logical connections provide a uniform high-level view of communication for both discrete and continuous data. The I/O ...Read More

This paper describes a distributed algorithm for computing the biconnected components of a dynamically changing graph. Our algorithm has a worst case communication complexity of O(b + c) messages for an edge insertion and O(b' + c) messages for an edge removal, and a worst case time complexity of O(c) for both operations, where c is the maximum number of biconnected components in any of the connected components during the operation, b is the number of nodes in the biconnected component containing the new edge, and bprime is the number ...Read More

Distributed multimedia computing and communiation systems combine computer systems, networks and distributed software to facilitate applications that enable and enhance collaborative work, direct interpersonal communication, remote access to information and real-time presentation of information from a variety of sources. Over the next decade, we expect such systems to become central to the infrastructure of our increasingly information-driven society. This prospectus describes a program of research being pursued within the Computer and Communications Research Center of Washington University and the Departments of Computer Science and Electrical Engineering. This program seeks to ...Read More

In 1993, APRA funded a major program at Washingotn University to create gigabit networking technology and create a gigabit testbed based on this technology. This program is now nearing the end of its first year and is making excellent proress towards its research and technical objectives. This note a proposes a program that would lead to the export of this technology to research groups in networking and gigabit applications with an interest in using it to further their own research activities.

A useful way to design simple and robust protocols is to make them self-stabilitizing. We describe a simple technique for self-stabilization called counter flushign which is applicable to a number of distributed algorithms. A randomized version of counter flushing is shown to have extremely small expected stabilization time. We show how our technique helps to crisply understand and improve some previous distributed algorithms. Then we apply it to a variety of total algorithms for deadlock detection, propagation of information with feedback, resets and snapshots. Our stabilizing snapshot protocol has much ...Read More

In high speed networks, packet processing is relatively expensive while bandwidth is cheap. This begs the question: what fields can be added to packets to make packet processing easier? By exploring this question, we device a number of novel mechanisms to speed up packet processing. With the advent of new standards for hte Data Link, Network, and Transport lyaers, we believe there is an opportunity to apply these techniques to improve the performance of real protocols. First, we suggest adding a data manipulation header to an easily accessible portion of ...Read More

Fair queuing is a technique that allows each flow passing through a network device to have fair share of network resources. previous schemes for fair queuing that achieved nearly perfect fairness were expensive to implement: specifically, the work required to process a packet in these schemes was O(log(n)), where n is the number of active flows. This is expensive at high speeds. On the other hand, cheaper approximations of fair queuing that have been reported in the literature exhibit unfair behavior. In this paper, we describe a new approximation of ...Read More

The current trend toward portable computing systems (e.g., cellular phones, laptop computers) brings with it the need for a new paradigm for thinking about designing distributed applications. We introduce the term mobile to refer to distributed systems that include moving, autonomous agents which loosely cooperate to accomplish a tastk. The fluid nature of hte interconnections between components in a mobile system provides new challenges and new opportunities for the research community. While we do not propsoe to have fully grasped the consequences of these systems, we believe that the notions ...Read More

We report the results of an experiment comparing the merits of the pen and the mouse as drawing devices. For this study a pen-based graphic diagram editor equipped with a shape recognition algorithm was developed on GO's PenPoint operating system. A commercially available drawing program on NeXT was used for mouse-based editing. Twelve CS students were chosen as subjects and asked to draw four different diagrams of similar complexity: two with a pen and the other two with a mouse. The diagrams are chosen from the categories of dataflow visual ...Read More

The analysis of human conversations has revealed that the design of interfaces using spoken dialogue must differ radically from those using written communication. Such characteristics as prosody, confirmations, echoes, and other speech phenomena must be considered. This work is a step in that direction. Prosodic, syntactic and semantic information from actual human dialogues has been used to build a turn-taking model empirically for dydadic telephone dialogues. The ability to predict completion of turns has been the biggest motivating factor in the development of this model. The design and evaluation of ...Read More

This paper explores the architectural requirements for computers to be able to process multimedia data streams such as video and audio. The I/O subsystem is shown to be a bottleneck, and a network backplane approach is suggested to alleviate this. The need to provide end-to-end performance guarantees requires predictable performance of intra-machine communication, and a schedulable bus with reservation is proposed to achieve this. In addition this requires operating system (OS) mechanisms to negotiate and enforce QoS requirements of applications. A real-time microkernel executive is proposed for each autonomous unit. ...Read More

Visual programming is the specification of computational processes using diagrams and icons. Traditional computation models such as Turing machines and lambda-calculus, which are based on one-dimensional text strings, are not suitable for visual programming languages. We propose a two-dimensional computation model that requires no text. We also prove that the model is computationallhy complete, i.e., that the model has the same computational power as Turing machines.

A number of efficient learning algorithms achieve exact identification of an unknown function from some clas using membership and equivalence queries. Using a standard transformation such algorithms can easily be converted to on-line learning algorithms that use membership queries. Under such a transformation the number of equivalence queries made by the query algorithm directly corresponds to the number of mistakes made by the on-line algorithm. In this paper we consider several of the natural classes known to be learnable in this setting, and investigate the minimum number of equivalence queries ...Read More

Declarative visualization is a paradigm in which the process of visualization is treated as a mapping from some domain (typically a program) to an image. One means of declaring such mappings is through the use of rules which specify the relationship between the domain and the image. This paper examines the computational power of such rule-based mappings. Computational power is measure using three separate criteria. The first of these uses the Chomsky hierarchy, in which computational power is treated as string-acceptance; with this criterion we are able to show that ...Read More

Recently, Static Single Assignment Form and Sparse Evaluation Graphs have been advanced for the efficient solution of program optimization problems. Each method is provided with an initial set of flow graph nodes that inherently affect a problem's solution. Other relevant nodes are those where potentially disparate solutions must combine. Previously, these so-called {phi}-nodes were found by computing the iterated dominance frontiers of the initial set of nodes, a process that could take worst case quadratic time with respect to the input flow graph. In this paper we present an almost-linear ...Read More