Digital Commons Network^™

Reliable Distributed Sorting Through The Application-Oriented Fault Tolerance Paradigm, Bruce M. Mcmillin, L. M. Ni

Computer Science Faculty Research & Creative Works

The design and implementation of a reliable version of the distributed bitonic sorting algorithm using the application-oriented fault tolerance paradigm on a commercial multicomputer is described. Sorting assertions in general are discussed and the bitonic sort algorithm is introduced. Faulty behavior is discussed and a fault-tolerant parallel bitonic sort developed using this paradigm is presented. The error coverage and the response of the fault-tolerant algorithm to faulty behavior are presented. Both asymptotic complexity and the results of run-time experimental measurements on an Ncube multicomputer are given. The authors demonstrate that the application-oriented fault tolerance paradigm is applicable to problems of …

A Definition Optimization Technique Used In A Code Translation Algorithm, David M. Dejean, George Winston Zobrist

Computer Science Faculty Research & Creative Works

Data flow analysis is used to optimize variable definitions in a program that translates microprocessor object code to a higher order language. © 1989, ACM. All rights reserved.

Personal Computing For The Visually Impaired, Bruce M. Mcmillin, P. Y. Mcmillin

Computer Science Faculty Research & Creative Works

The problem of providing feedback from the computer to a visually impaired user is examined. The use of traditional tactile input and output (Braille) is described. The limitations of voice output are discussed, and difficulties posed by complicated screen formats and screen review are considered.

Safe Computing, Bruce M. Mcmillin, T. L. Casavant

Computer Science Faculty Research & Creative Works

So-called worms, viruses, and Trojan horses that attack computer systems are defined. The vehicle that allows these attacks to occur, namely, the open computer internetwork, is examined. The problem of providing protection against attack in an internetwork environment is discussed. The need for professional responsibility on the part of the scientific and engineering community in enforcing strong ethical practices and neither tolerating nor condoning such practices is stressed.

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The best previous …

Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k, there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.

Fault Diagnosis Using First Order Logic Tools, Ralph W. Wilkerson, Barbara A. Smith

Computer Science Faculty Research & Creative Works

An automated circuit diagnostic tool implementing R. Reiter's theory of diagnosis (1987) based on deep knowledge (i.e. knowledge based on certain design information) and using first-order logic as the representation language is discussed. In this approach, the automated diagnostician uses a description of the system structure and observations describing its performance to determine if any faults are apparent. If there is evidence that the system is faulty, the diagnostician uses the system description and observations to ascertain which component(s) would explain the behavior. In particular, Reiter's method finds all combinations of components which explain this behavior.

Automatically Generating Functional Tests From Specifications - A Knowledge Based Constraint Logical Programming Approach, Ji Chen

Computer Science Theses & Dissertations

Recent experimental results indicate that functional testing is one of the most effective methods in detecting certain classes of faults. Very little work has been done in automating functional testing. This thesis research develops a method, called hierarchical partition, for automating functional testing. The key to our approach is the utilization of a pre-existing knowledge base about the domain of discourse. Several approaches to knowledge organiza­tion are discussed along with the resulting effects on the quantity and quality of functional tests produced. This research is an application and development of Generic Constraint Logic Programming and the Knowledge Driven …

A Theory Of Testability With Application To Fault Coverage Analysis, Sharad C. Seth, Vishwani Agrawal, Hassan Farhat

School of Computing: Faculty Publications

When test vectors are applied to a circuit, the fault coverage increases. The rate of increase, however, could be circuit-dependent. In fact, the actual rise of fault coverage depends on the characteristics of vectors, as well as, on the circuit. The paper shows that the average fault coverage can be computed from circuit testability. A relationship between fault coverage and circuit testability is derived. The mathematical formulation allows computation of coverage for deterministic and random vectors. Applications of this analysis include: determination of circuit testability from fault simulation, coverage prediction from testability analysis, prediction of test length, and test generation …

Machine Knowledge Maniputation Issues In Parallel Compilers, Ko-Yang Wang, Dennis Gannon, Piyush Mehrotra

Department of Computer Science Technical Reports

No abstract provided.

Elliptic Expert: The Design Of An Expert System For Elliptic Partial Differential Equations, Wayne R. Dyksen, Carl R. Gritter

Department of Computer Science Technical Reports

No abstract provided.

Hermite Interpolation Of Rational Space Curves Using Real Algebraic Surfaces, Chanderjit Bajaj, Insung Ihm

Department of Computer Science Technical Reports

No abstract provided.

Effects Of Autonomy On Maintaining Global Serializability In Heterogeneous Database Systems, W. Du, Ahmed K. Elmagarmid, Y. Leu, S. F. Ostermann

Department of Computer Science Technical Reports

No abstract provided.

Quasi Serializability: A Correctness Criterion For Interbase, Ahmed K. Elmagarmid

Department of Computer Science Technical Reports

No abstract provided.

Distributed Operation Language For Specification And Processing Of Multidatabase Applications, Marek Rusinkiewicz, Kanchei Loa, Ahmed K. Elmagarmid

Department of Computer Science Technical Reports

No abstract provided.

Convex Decompositions Of Simple Polyhedra, Chanderjit Bajaj, Tamal K. Dey

Department of Computer Science Technical Reports

No abstract provided.

A System For The Diagnosis Of Faults Using A First Principles Approach, Barbara A. Smith, Ralph W. Wilkerson

Computer Science Technical Reports

One of the primary areas of application of Artificial Intelligence is diagnosis. Diagnosis from first principles is a diagnostic technique which uses knowledge of the designed structure and function of a device to determine the possible causes of the malfunction.

This work builds on the foundation of a theory of diagnosis by implementing and extending the theory. A correction to the algorithm which defines the theory is presented. The theory is extended for multiple sets of observations of the system and measurement data.

A fundamental problem in diagnosis is selecting the measurement which will be of the most benefit in …

Parallel (//) Ellpack: An Expert System For Parallel Processing Of Partial Differential Equations, Elias N. Houstis, John R. Rice, T. S. Papatheodorou

Department of Computer Science Technical Reports

No abstract provided.

A White Paper On High-Speed Network Architecture, Douglas E. Comer, John M. Steele, Raj Yavatkar

Department of Computer Science Technical Reports

No abstract provided.

Imacs Conference On Expert Systems For Numerical Computing, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.

On The Sorting Of Points Along An Algebraic Curve, John K. Johnstone, Chanderjit Bajaj

Department of Computer Science Technical Reports

No abstract provided.

The Internet Worm Program: An Analysis, Eugene H. Spafford

Department of Computer Science Technical Reports

No abstract provided.

On The Geometry Of Dupin Cyclides, V. Chandru, D. Dutta, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.

The Ipe-Pc Integrated Programming Environment, Nurcan Coskun, Thomas J. Sager

Computer Science Technical Reports

An Integrated Programming Environment, IPE-PC, that supports pseudo-code development has been designed and implemented. This environment is based on a Pascal-like language which is designed according to the requirements of a language-based environment. The nucleus of IPE-PC is a language-based editor which represents programs as graphs internally. The same representation is used in every mode of the environment (i.e., editing, compilation, execution, debugging and translation). The system provides facilities to take advantage of both top-down and bottom-up programming. Stepwise refinement has been supported by providing comment structures that can be transformed into procedures. Bottom-up programming is supported because it is …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, November 1988, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A fourteen page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Transformation Based Endorsement Systems, Thomas Sudkamp

Computer Science and Engineering Faculty Publications

Evidential reasoning techniques classically represent support for a hypothesis by a numeric value or an evidential interval. The combination of support is performed by an arithmetic rule which often requires restrictions to be placed on the set of possibilities. These assumptions usually require the hypotheses to be exhausitive and mutually exclusive. Endorsement based classification systems represent support for the alternatives symbolically rather than numerically. A framework for constructing endorsement systems is presented in which transformations are defined to generate and update the knowledge base. The interaction of the knowledge base and transformations produces a non-monotonic reasoning system. Two endorsement based …

Mulch: A Multi-Layer Channel Router Using One, Two, And Three Layer Partitions, Ronald I. Greenberg, Alex T. Ishii, Alberto L. Sangiovanni-Vincentelli

Computer Science: Faculty Publications and Other Works

Chameleon, a channel router for three layers of interconnect, has been implemented to accept specification of an arbitrary number of layers. Chameleon is based on a strategy of decomposing the multilayer problem into two- and three-layer problems in which one of the layers is reserved primarily for vertical wire runs and the other layer(s) for horizontal runs. In some situations, however, it is advantageous to consider also layers that allow the routing of entire nets, using both horizontal and vertical wires. MulCh is a multilayer channel router that extends the algorithms of Chameleon in this direction. MulCh can route channels …

An Event-Action Model And Associated Architecture For Monitoring Parallel And Distributed Systems, Dan C. Marinescu, James E. Lumpp, Thomas L. Casavant, Howard Jhay Siegel

Department of Computer Science Technical Reports

No abstract provided.

Implementing Educational Software And Evaluating Its Academic Effectiveness: Part Ii, Karen Jolicoeur, Dale E. Berger

CGU Faculty Publications and Research

In Part I, published last month, we presented a successful classroom implementation plan for integrating educational software into elementary school classrooms. Implementing educational software successfully into classrooms is an essential prerequisite to achieving the second goal of the present research-evaluating how much students learned by using specific software programs. In Part II, we will measure how effective eight software programs were at teaching fifth grade students new fraction concepts and spelling words. In addition, we will examine the validity of teacher and student software ratings based on the effectiveness of each program.

Comments On Proposed Transport Protocols, Anil Bhatia, James Sterbenz, Gurudatta M. Parulkar

All Computer Science and Engineering Research

Over the last few years, a number of research groups have made considerable progress on the design of high speed networks- on the order of a few hundred Mbps to the few Gbps. The emphasis of this work has been on the design of packet switches and on the design of network access protocols. However, this work has not yet addressed the internetworking and transport level issues in the high speed internet. As part of our effort on the design of VHSI model, we considered the appropriateness of recently proposed transport protocols, NETBLT and VMTP, as candidates for the transport …