leff@smu.UUCP (Laurence Leff) (05/11/89)
DEPARTMENT OF COMPUTER SCIENCES
TECHNICAL REPORT CENTER
TAYLOR HALL 2.124
THE UNIVERSITY OF TEXAS AT AUSTIN
AUSTIN, TEXAS 78712-1188
(512) 471-9595
ELECTRONIC MAIL ADDRESS: trcenter@cs.utexas.edu
TECHNICAL REPORTS, JANUARY 1989 - APRIL 1989
PREPAYMENT IS REQUIRED.
Please make U.S. bank checks or international money orders payable to
"The University of Texas."
[] TR-88-23 (Revision) $1.50
[] TR-89-01 $1.50 [] TR-89-06 $1.50
[] TR-89-02 $1.50 [] TR-89-07 $1.50
[] TR-89-03 $1.50 [] TR-89-08 $1.50
[] TR-89-04 $3.00 [] TR-89-09 $1.50
[] TR-89-05 $1.50 [] TR-89-10 $1.50
[] TR-89-11 $2.00
---------------------------------------------------------------------------
TR-88-23 A NEW EXPLANATION OF THE GLITCH PHENOMENON
James H. Anderson and Mohamed G. Gouda
March 1989 (Revision)
18 pages
ABSTRACT: We consider a discrete model for asynchronous cir-
cuits and show that, under very mild restrictions, this model
excludes the existence of glitch-free arbiters. This result
contradicts a long standing conjecture that the nonexistence of
glitch-free arbiters is due to the continuous nature of such
circuits.
Keywords: arbiter, asynchronous circuit, atomicity, glitch,
history, interleaving semantics, metastability, nondeterminism,
waiting.
TR-89-01 ILLUMINATION NETWORKS: FAST REALISTIC RENDERING WITH ARBITRARY
REFLECTANCE FUNCTIONS
Chris Buckalew and Donald Fussell
January 1989
8 pages
ABSTRACT: We present a technique for modeling global illumina-
tion which allows a wide variety of reflectance functions.
Scene coherence is exploited in a preprocessing step in which
the geometry is analyzed using iterative techniques. Memory is
traded for speed, in anticipation of the high memory capacities
of workstations of the future. The algorithm operates well
over a wide range of time and image quality constraints: real-
istic results may be produced very quickly while very accurate
results may be produced given more time and space. The method
can be extended for animation and parallelization.
Keywords: Computer Graphics, Picture/Image generation - display
algorithms, three-dimensional graphics and realism, global
illumination, radiosity, ray tracing, memory, specular, dif-
fuse, data structure, incremental, ray space.
TR-89-02 BLOCK ACKNOWLEDGEMENT: REDESIGNING THE WINDOW PROTOCOL
G. M. Brown, M. G. Gouda, and R. E. Miller
March 1989
16 pages
ABSTRACT: We describe a new version of the window protocol
where message sequence numbers are taken from a finite domain
and where both message disorder and loss can be tolerated.
Most existing window protocols achieve only one of these two
goals. Our protocol is based on a new method of acknowledge-
ment, called block acknowledgement, where each acknowledgement
message has two numbers m and n to acknowledge the reception of
all data messages with sequence numbers ranging from m to n.
Using this method of acknowledgement, the proposed protocol
achieves the two goals while maintaining the same data
transmission capability of the traditional window protocol.
Keywords: Computer networks, communication protocols, window
protocol, protocol verification, message sequence numbers,
transmission errors.
TR-89-03 TOPOLOGICAL TESTING
Miroslaw Malek, Antoine Mourad, and Mihir Pandya
March 1989
22 pages
ABSTRACT: A concept of topological testing is introduced and
its applications are presented. Topological testing uses graph
theoretic optimization methods such as the Traveling Salesman
Problem, the Chinese Postman Problem, path covering and parti-
tioning to minimize the test time. The topological testing
techniques can be applied to each level of system hierarchy,
namely, circuit, logic, register transfer, instruction and
processor-memory-switch levels. Specifically, the topological
testing approach is demonstrated by developing tests for the
multistage interconnection network and the hypercube network.
Time optimization for the testing of these networks gives very
promising results by taking advantage of inherent parallelism
and removing test redundancy. Three orders of magnitude
improvement is achieved by applying topological testing tech-
niques to the testing of an existing multistage interconnection
network.
Keywords: Testing, graph theory, optimization methods, multis-
tage interconnection networks, hypercube.
TR-89-04 DISTRIBUTED FILE SYSTEMS
Eliezer Levy and Abraham Silberschatz
March 1989
54 pages
ABSTRACT: Distributed File Systems are essential for sharing of
data and storage space in a distributed system. A viewpoint
that emphasizes the dispersed structure and decentralization of
both data and control in the design of such systems is esta-
blished. The concepts of location transparency, fault tolerance
and scalability are defined and discussed in the context of
Distributed File Systems. It is claimed that the principle of
distributed operation is fundamental for a fault tolerant and
scalable Distributed File System. Alternatives for the seman-
tics of sharing and methods for providing access to remote
files are also presented. A survey of current systems, namely
Unix United, Locus, Sprite, Sun's Network File System, and
ITC's Andrew, illustrates the discussed concepts and demon-
strates various implementations and design alternatives. Based
on the assessment of these systems, a point is made that a
departure from the approach of extending centralized file sys-
tems over the network is necessary to accomplish sound Distri-
buted File System design.
Keywords: Distributed systems, networks, file systems, fault
tolerance, scalability.
TR-89-05 A FRAMEWORK FOR THE PARALLEL PROCESSING OF DATALOG QUERIES
Sumit Ganguly, Avi Silberschatz, and Shalom Tsur
March 1989
17 pages
ABSTRACT: This paper presents several schemas for the parallel,
bottom-up evaluation of a class of Datalog queries. Our method
is presented in three steps: A rewrite step that renders an
equivalent program to the original one, explicitly amenable to
parallel execution; an assignment step that assigns the rules
and data of the rewritten program to processors and an execu-
tion step that performs the computation, either with or without
processor intercommunication.
The schemas obtained demonstrate trade-offs between redundancy
(duplication of computation by processors) and interprocessor-
communication. We introduce the notion of a discriminating
predicate by which the computation is partitioned among the
processors and parallelism is achieved.
Keywords: Parallelization, datalog, bottom-up evaluation.
TR-89-06 A HYBRID ALGORITHM TECHNIQUE
Miroslaw Malek, Mohan Guruswamy, Howard Owens, and Mihir Pandya
March 1989
27 pages
ABSTRACT: A new hybrid algorithm technique (HAT) based on the
idea of mixing two or more algorithms is proposed. Though the
algorithm is general and may be applied to the majority of
optimization problems, a hybrid algorithm search technique
(HAST) is the focus of this paper. As an example of HAST, this
paper describes mixing of simulated annealing and tabu search
algorithms into a new hybrid search algorithm applied to the
traveling salesman problem. A brief introduction to the simu-
lated annealing and tabu search algorithms is given followed by
a description of how we mixed these algorithms to form a new
parallel hybrid search technique. Comparison of our algorithm
mixer with simulated annealing and tabu search indicates con-
sistently better results. Examples include 33, 42, 50, 57, 75,
and 100 city problems from the literature. Solutions for the 50
and 75 city problems outperform best known published to date
results.
Keywords: Algorithm, search techniques, simulated annealing,
tabu search, traveling salesman problem.
TR-89-07 A SYSTOLIC PROGRAM FOR GAUSS-JORDAN ELIMINATION
Duncan Hudson and Christian Lengauer
March 1989
14 pages
ABSTRACT: A scheme for the compilation of imperative or func-
tional programs into systolic programs is used to derive an
occam program for Gauss-Jordan elimination from a Pascal-like
program. The correctness of the output program is guaranteed by
the correctness of the input program and of the compilation
scheme. The novelty of this example is that the compilation
scheme has been applied for the first time to a systolic array
that is described by piecewise linear, not linear distribution
functions.
Keywords: Algebraic Path Problem, code generation, compilation,
Gauss-Jordan elimination, occam, systolic array.
TR-89-08 MECHANICAL THEOREM PROVING IN DIFFERENTIAL GEOMETRY
Shang-Ching Chou and Xiao-Shan Gao
March 1989
29 pages
ABSTRACT: With an improved version of Ritt-Wu's zero decomposi-
tion algorithm for differential polynomials, we present two
approaches to mechanical proving of geometry theorems in dif-
ferential geometry. The first approach can be used to prove a
theorem when nondegenerate conditions are given explicitly.
The second approach can be used to prove a statement to be
generically true. More than fifty nontrivial theorems in the
space curve theory have been proved mechanically by our pro-
gram, in particular, the properties of the Bertrand curves are
studied in full detail.
Keywords: Mechanical theorem proving, Wu's method, differential
polynomial, Ritt-Wu's decomposition algorithm, main component,
differential geometry, the space curve theore, the Bertrand
curves.
TR-89-09 RITT WU'S DECOMPOSITION ALGORITHM AND GEOMETRY THEOREM PROVING
Shang-Ching Chou and Xiao-Shan Gao
March 1989
23 pages
ABSTRACT: An improved Ritt-Wu's decomposition (of an algebraic
set into the union of irreducible varieties) algorithm is
given. The algorithm has been used to prove geometric theorems
that Wu's original method addresses. Unlike Wu's original
approach, nondegenerate conditions are given explicitly at the
beginning, not generated during the proof process. A program
based on this improved version of the algorithm proved more
than 500 theorems, including Morley's trisector theorem.
Keywords: Wu's method, mechanical theorem proving, prover, ele-
mentary geometry, degenerate conditions, Ritt-Wu's principle,
algebraic variety, nondegenerate component, ideal, ascending
chain, the dimension theorem, Morley's trisector theorem.
TR-89-10 USING (N-1)-PROCESS ELECTION TO SOLVE N-PROCESS ELECTION
James H. Anderson
March 1989
8 pages
ABSTRACT: We present a solution strategy for N-process election
in which a leader is chosen based upon the results of a number
of (N-1)-process elections. We show that the existence of such
a solution depends on the constraints that are placed on the
(N-1)-process elections.
Keywords: election primitives, impossibility proof, leader
election, knowledge-based reasoning, program composition, ran-
dom assignment.
TR-89-11 AUTOMATED REASONING IN MECHANICS USING RITT-WU'S METHOD
Shang-Ching Chou and Xiao-Shan Gao
April 1989
33 pages
ABSTRACT: Methods of automated reasoning in mechanics have been
presented and implemented on computers. The paper consists of
two parts. In part I, a mechanical method developed by W.T. Wu
on the basis of the work of J. F. Ritt has been used to prove
theorems in mechanics. In particular, a mechanical study of
the complete logical relationship between Kepler's laws and
Newton's gravitational laws has been given. Wu's work on the
same topic has been extended in several ways. Many other exam-
ples from mechanics are also given. In part II, a method of
mechanical derivation of formulas from a set of differential
polynomials has been presented. The method has been used
successfully to some problems in mechanics. In particular, a
mechanical derivation of Newton's gravitational laws from
Kepler's laws has been given without knowing Newton's Laws in
advance.
Keywords: Mechanical theorem proving, mechanical derivation of
formulas, Wu's method, differential polynomial, Ritt-Wu's
decomposition algorithm, mechanics, Newton's gravitational
laws, Kepler's laws.