Computer Sciences Commons^™

Run Time Security Evaluation For Distributed Applications, Cristina Serban, Bruce M. Mcmillin

Computer Science Technical Reports

Formal security specifications for a distributed application can be checked for compliance at run-time, during the execution of the application. We propose the RunTime Security Evaluation (RTSE) method which makes use of executable security assertions, histories/traces of events, and operational evaluation in the distributed environment to ensure the security specifications regarding the confidentiality and integrity requirements for the application are fulfilled at run-time. A model problem is used to aid in developing the security requirements formally, and assessment of the RTSE method is given based on the results obtained for the implementation of the model problem. The elements necessary for …

Ffts For The 2-Sphere-Improvements And Variations, D M. Healy, D Rockmore, Sean S.B. Moore

Computer Science Technical Reports

Earlier work by Driscoll and Healy has produced an efficient algorithm for computing the Fourier transform of band-limited functions on the 2-sphere. In this paper we present a reformulation and variation of the original algorithm which results in a greatly improved inverse transform, and consequent improved convolution algorithm for such functions. All require at most 0(N log2 N) operations where N is the number of sample points. We also address implementation considerations and give heuristics for allowing reliable floating point implementations of a slightly modified algorithm at little cost in either theoretical or actual performance. These claims are supported by …

On The Existence Of Schedules That Are Near-Optimal For Both Makespan And Total Weighted Completion Time, Cliff Stein, Joel Wein

Computer Science Technical Reports

We give a simple proof that, for any instance of a very general class of scheduling problems, there exists a schedule of makespan at most twice that of the optimal possible and of total weighted completion time at most twice that of the optimal possible. We then refine the analysis, yielding variants of this theorem with improved constants, and give some algorithmic consequences of the technique.

Mobile Agents For Mobile Computing, Robert Gray, David Kotz, Saurab Nog, Daniela Rus, George Cybenko

Computer Science Technical Reports

Mobile agents are programs that can move through a network under their own control, migrating from host to host and interacting with other agents and resources on each. We argue that these mobile, autonomous agents have the potential to provide a convenient, efficient and robust programming paradigm for distributed applications, particularly when partially connected computers are involved. Partially connected computers include mobile computers such as laptops and personal digital assistants as well as modem-connected home computers, all of which are often disconnected from the network. In this paper, we describe the design and implementation of our mobile-agent system, Agent Tcl, …

Dartflow: A Workflow Management System On The Web Using Transportable Agents, Ting Cai, Peter A. Gloor, Saurab Nog

Computer Science Technical Reports

Workflow management systems help streamline business processes and increase productivity. This paper describes the design and implementation of the DartFlow workflow management system. DartFlow uses Web-browser embedded Java applets as its front end and transportable agents as the backbone. While Java applets provide a safe and platform independent GUI, the use of transportable agents makes DartFlow highly flexible and scalable. This paper describes the design and implementation of DartFlow, as well as a workflow application that exploits DartFlow's agent-based design.

The Galley Parallel File System, Nils Nieuwejaar, David Kotz

Computer Science Technical Reports

Most current multiprocessor file systems are designed to use multiple disks in parallel, using the high aggregate bandwidth to meet the growing I/O requirements of parallel scientific applications. Many multiprocessor file systems provide applications with a conventional Unix-like interface, allowing the application to access multiple disks transparently. This interface conceals the parallelism within the file system, increasing the ease of programmability, but making it difficult or impossible for sophisticated programmers and libraries to use knowledge about their I/O needs to exploit that parallelism. In addition to providing an insufficient interface, most current multiprocessor file systems are optimized for a different …

New Methods In Finite First-Order Model Search, Olga Shumsky, Fikret Ercal, Ralph W. Wilkerson

Computer Science Technical Reports

An automated first-order theorem prover, armed with appropriate strategies, will find a proof of a true conjecture, but will, in theory, run indefinitely if no proof exists. In reality, if no proof exists, the execution will be terminated by user-defined constraints, such as running time or memory usage limit. In this case the the question of validity of the conjecture remains unanswered. An automated first-order model generator gives one the ability to find counterexamples, if any exist, showing that the conjecture is invalid. A model generator also helps find the illustrations of previously proved theorems. It can be viewed as …

Application Of Neural Networks To The Non-Destructive Testing Of Aluminum Cans, B. Balasubramaniam, Daniel .. Clair

Computer Science Technical Reports

Neural Networks are used to c lassify aluminum beverage containers as acceptable or non acceptable, depending upon their wall thicknesses. For each can, the thickness of the wall of the can at different points is measured using a non-destructive, ultra-sound technique. These measureI\}ents are then applied as inputs to the networks and the classification is provided as the output Three architectures, one unsupervised and two supervised, are tested. Their performances are analyzed and compared and the paradigm best suited to the problem is selected.

Computer Assisted Control Of Robotic Rock Drilling Equipment Using Rock Face Image Mapping, William Robert Macneil, Peter (C. Y.)(Chung You) Ho

Computer Science Technical Reports

Use of a totally unmanned mining robot is an ideal solution in removing humans from the dangerous underground mining environment. However, a complete autonomous system is a long way from reality. In the meantime, steps towards that goal can be made and integrated into current mining technology to take away some of the risk and stress from the miner making him more alert and the environment safer for those that do have to be undergroμnd. For our purposes here, the machine will be an automated robotic platform with the intelligence necessary for accurate placement of the drill tip on an …

File-Access Characteristics Of Parallel Scientific Workloads, Nils Nieuwejaar, David Kotz, Apratim Purakayastha, Carla Schlatter Ellis, Michael Best

Computer Science Technical Reports

Phenomenal improvements in the computational performance of multiprocessors have not been matched by comparable gains in I/O system performance. This imbalance has resulted in I/O becoming a significant bottleneck for many scientific applications. One key to overcoming this bottleneck is improving the performance of parallel file systems.

The design of a high-performance parallel file system requires a comprehensive understanding of the expected workload. Unfortunately, until recently, no general workload studies of parallel file systems have been conducted. The goal of the CHARISMA project was to remedy this problem by characterizing the behavior of several production workloads, on different machines, at …

A Queuing Analysis Of Bandwidth Allocation Schemes For Compressed Video, Saurab Nog, Carl J. Beckmann

Computer Science Technical Reports

Video and audio compression techniques allow continuous media streams to be transmitted at bit rates that are a function of the delivered quality of service. Digital networks will be increasingly used for the transmission of such continuous media streams. This paper describes an admission control policy in which the quality of service is negotiated at stream initiation, and is a function of both the desired quality of service and the available bandwidth resources. The advantage of this approach is the ability to robustly service large numbers of users, while providing increased quality of service during low usage periods. Several simple …

Wheels: An Automated Program Analysis Tool, Aggie Sun, Bruce Mcmillin

Computer Science Technical Reports

The understanding of program behavior is becoming vitally more important now that software is becoming an integral part of industry and everyday life. However, even the best documented code is often not sufficient enough to completely and correctly relay the actual program behavior. The problem lies beyond being familiar with the programming language and is hidden in the complex mathematics which govern the program's behavior. This behavior is not easily detected and varies from one program to the next. We propose a method for describing program behavior using two general properties of iterative programs: feasibility and progress. This method can …

The Expected Lifetime Of "Single-Address-Space" Operating Systems, David Kotz, Preston Crow

Computer Science Technical Reports

Trends toward shared-memory programming paradigms, large (64-bit) address spaces, and memory-mapped files have led some to propose the use of a single virtual-address space, shared by all processes and processors. Typical proposals require the single address space to contain all process-private data, shared data, and stored files. To simplify management of an address space where stale pointers make it difficult to re-use addresses, some have claimed that a 64-bit address space is sufficiently large that there is no need to ever re-use addresses. Unfortunately, there has been no data to either support or refute these claims, or to aid in …

An Rpc Mechanism For Transportable Agents, Saurab Nog, Sumit Chawla, David Kotz

Computer Science Technical Reports

Transportable agents are autonomous programs that migrate from machine to machine, performing complex processing at each step to satisfy client requests. As part of their duties agents often need to communicate with other agents. We propose to use remote procedure call (RPC) along with a flexible interface definition language (IDL), to add structure to inter-agent communication. The real power of our Agent RPC comes from a client-server binding mechanism based on flexible IDL matching and from support for multiple simultaneous bindings. Our agents are programmed in Agent Tcl; we describe how the Tcl implementation made RPC particularly easy to implement. …

Fast Compression Of Transportable Tcl Scripts, Robert S. Gray

Computer Science Technical Reports

An information agent is charged with the task of searching a collection of electronic resources for information that is relevant to the user's current needs. These resources are often distributed across a network and can contain tremendous quantities of data. One of the paradigms that has been suggested for allowing efficient access to such resources is transportable agents -- the agent is sent to the machine that maintains the information resource; the agent executes on this remote machine and then returns its results to the local machine. We have implemented a transportable agent system that uses the Tool Command Language …

A Performance Comparison Of Tcp/Ip And Mpi On Fddi, Fast Ethernet, And Ethernet, Saurab Nog, David Kotz

Computer Science Technical Reports

Communication is a very important factor affecting distributed applications. Getting a close handle on network performance (both bandwidth and latency) is thus crucial to understanding overall application performance. We benchmarked some of the metrics of network performance using two sets of experiments, namely roundtrip and datahose. The tests were designed to measure a combination of network latency, bandwidth, and contention. We repeated the tests for two protocols (TCP/IP and MPI) and three networks (100 Mbit FDDI (Fiber Distributed Data Interface), 100 Mbit Fast Ethernet, and 10 Mbit Ethernet). The performance results provided interesting insights into the behaviour of these networks …

Transportable Information Agents, Robert Gray, Daniela Rus, David Kotz

Computer Science Technical Reports

We have designed and implemented autonomous software agents. Autonomous software agents navigate independently through a heterogeneous network. They are capable of sensing the network configuration, monitoring software conditions, and interacting with other agents. Autonomous agents are implemented as transportable programs, e.g., programs that are capable of suspending execution, moving to a different machine, and starting from where they left off. We illustrate the intelligent behavior of autonomous agents in the context of distributed information-gathering tasks.

Compositional Reasoning Is Not Possible In Determining The Solvability Of Consensus, Prasad Jayanti

Computer Science Technical Reports

Consensus, which requires processes with different input values to eventually agree on one of these values, is a fundamental problem in fault-tolerant computing. We study this problem in the context of asynchronous shared-memory systems. In our model, shared-memory consists of a sequence of cells and supports a specific set of operations. Prior research on consensus focussed on its solvability in shared-memories supporting specific operations. In this paper, we investigate the following general question: Let OP1 and OP2 be any two sets of operations such that each set includes read and write operations. Suppose there is no consensus protocol for N …

A 2-2/3 Approximation For The Shortest Superstring Problem, Chris Armen, Clifford Stein

Computer Science Technical Reports

Given a collection of strings S={s_1, ..., s_n} over an alphabet \Sigma, a superstring \alpha of S is a string containing each s_i as a substring; that is, for each i, 1<=i<=n, \alpha contains a block of |s_i| consecutive characters that match s_i exactly. The shortest superstring problem is the problem of finding a superstring \alpha of minimum length. The shortest superstring problem has applications in both data compression and computational biology. In data compression, the problem is a part of a general model of string compression proposed by Gallant, Maier and Storer (JCSS '80). Much of the recent interest in the problem is due to its application to DNA sequence assembly. The problem has been shown to be NP-hard; in fact, it was shown by Blum et al.(JACM '94) to be MAX SNP-hard. The first O(1)-approximation was also due to Blum et al., who gave an algorithm that always returns a superstring no more than 3 times the length of an optimal solution. Several researchers have published results that improve on the approximation ratio; of these, the best previous result is our algorithm ShortString, which achieves a 2 3/4-approximation (WADS '95). We present our new algorithm, G-ShortString, which achieves a ratio of 2 2/3. It generalizes the ShortString algorithm, but the analysis differs substantially from that of ShortString. Our previous work identified classes of strings that have a nested periodic structure, and which must be present in the worst case for our algorithms. We introduced machinery to descibe these strings and proved strong structural properties about them. In this paper we extend this study to strings that exhibit a more relaxed form of the same structure, and we use this understanding to obtain our improved result.

Information Retrieval, Information Structure, And Information Agents, Daniela Rus, Devika Subramanian

Computer Science Technical Reports

This paper presents a customizable architecture for software agents that capture and access information in large, heterogeneous, distributed electronic repositories. The key idea is to exploit underlying structure at various levels of granularity to build high-level indices with task-specific interpretations. Information agents construct such indices and are configured as a network of reusable modules called structure detectors and segmenters. We illustrate our architecture with the design and implementation of smart information filters in two contexts: retrieving stock market data from Internet newsgroups, and retrieving technical reports from Internet ftp sites.

An Api For Choreographing Data Accesses, Elizabeth A.M. Shriver, Leonard F. Wisniewski

Computer Science Technical Reports

Current APIs for multiprocessor multi-disk file systems are not easy to use in developing out-of-core algorithms that choreograph parallel data accesses. Consequently, the efficiency of these algorithms is hard to achieve in practice. We address this deficiency by specifying an API that includes data-access primitives for data choreography. With our API, the programmer can easily access specific blocks from each disk in a single operation, thereby fully utilizing the parallelism of the underlying storage system. Our API supports the development of libraries of commonly-used higher-level routines such as matrix-matrix addition, matrix-matrix multiplication, and BMMC (bit-matrix-multiply/complement) permutations. We illustrate our API …

Complexity Analysis Of Two Permutations Used By Fast Cosine Transform Algorithms, Sean S.B. Moore, Leonard F. Wisniewski

Computer Science Technical Reports

Recently developed fast cosine transform (FCT) algorithms require fewer operations than any other known general algorithm. Similar to related fast transform algorithms (e.g., the FFT), these algorithms permute the data before, during, or after the computation of the transform. The choice of this permutation may be an important consideration in reducing the complexity of the permutation algorithm. In this paper, we derive the complexity to generate the permutation mappings used in these FCT algorithms for power-of-2 data sets by representing them as linear index transformations and translating them into combinational circuits. Moreover, we show that one of these permutations not …

Finding Real-Valued Single-Source Shortest Paths In O(N^3) Expected Time, Stavros G. Kolliopoulos, Clifford Stein

Computer Science Technical Reports

Given an $n$-vertex directed network $G$ with real costs on the edges and a designated source vertex $s$, we give a new algorithm to compute shortest paths from $s$. Our algorithm is a simple deterministic one with $O(n^2 \log n)$ expected running time over a large class of input distributions. The shortest path problem is an old and fundamental problem with a host of applications. Our algorithm is the first strongly-polynomial algorithm in over 35 years to improve upon some aspect of the running time of the celebrated Bellman-Ford algorithm for arbitrary networks, with any type of cost assignments.

Formal Methods: How, When, And Why They Are Used, Beth Arrowsmith, Bruce Mcmillin, Ralph Wilkerson

Computer Science Technical Reports

Formal methods, theoretically a wonderful concept for ensuring a program's correctness, are not widely used in practice. This dichotomy between what theory advocates and practice might be due to programmers' lack of experience with formal methods. To determine if this was the case, a module on Formal Methods was introduced into a graduate course on distributed systems. This module first introduced the students to the theory of formal methods and then required students to program a distributed problem in CCSP, a subset of CSP, using formal methods. The results were abysmal. Students avoided using formal methods. When they did use …

Interfaces For Disk-Directed I/O, David Kotz

Computer Science Technical Reports

In other papers I propose the idea of disk-directed I/O for multiprocessor file systems. Those papers focus on the performance advantages and capabilities of disk-directed I/O, but say little about the application-programmer's interface or about the interface between the compute processors and I/O processors. In this short note I discuss the requirements for these interfaces, and look at many existing interfaces for parallel file systems. I conclude that many of the existing interfaces could be adapted for use in a disk-directed I/O system.

Structured Permuting In Place On Parallel Disk Systems, Leonard F. Wisniewski

Computer Science Technical Reports

The ability to perform permutations of large data sets in place reduces the amount of necessary available disk storage. The simplest way to perform a permutation often is to read the records of a data set from a source portion of data storage, permute them in memory, and write them to a separate target portion of the same size. It can be quite expensive, however, to provide disk storage that is twice the size of very large data sets. Permuting in place reduces the expense by using only a small amount of extra disk storage beyond the size of the …

Process Migration For Heterogeneous Distributed Systems, Matt Bishop, Mark Valence, Leonard F. Winiewski

Computer Science Technical Reports

The policies and mechanisms for migrating processes in a distributed system become more complicated in a heterogeneous environment, where the hosts may differ in their architecture and operating systems. These distributed systems include a large quantity and great diversity of resources which may not be fully utilized without the means to migrate processes to the idle resources. In this paper, we present a graph model for single process migration which can be used for load balancing as well as other non-traditional scenarios such as migration during the graceful degradation of a host. The graph model provides the basis for a …

Fast Spherical Transforms On Distance Transitive Graphs, J R. Driscoll, D M. Healy Jr, D Rockmore

Computer Science Technical Reports

No abstract provided.

Matching And Indexing Techniques In Rules, Madhav Moganti

Computer Science Technical Reports

Rules are widely used in present-day intelligent systems for modeling intelligent behavior, building expert systems, database rule systems, and advanced document retrieval systems. Most rule-based system programs are extremely computation-intensive and run quite slowly. This problem may get still worse when a rulebase does not fit into primary memory completely. This article reviews currently existing rule matching and indexing techniques. This report is organized into two parts. Part I presents the well known rule matching algorithms, Rete and TREAT, along with their performance evaluations. Part II presents rule indexing techniques for large scale rulebases. Here two sources of indexing are …

Parallel Fast Multipole Algorithm Using Mpi, Daniel Okunbor, Eric Jui-Lin Lu

Computer Science Technical Reports

The simulation of many-body, many-particle system has a wide range of applications in area such as biophysics, chemistry, astrophysics, etc. It is known that the force calculation contributes ninety percent of the simulation time. This is mainly due to the fact that the total number of interactions in the force is 0( N 2 ), where N is the number of particles in the system. The fast multipole algorithm, proposed by Greengard and Rokhlin, reduces the time complexity of the force calculation to O(N). We implement the fast multipole algorithm, using MPI, based on optimal communication scheme which minimizes the …