CS Theses & Dissertations 1992

For 1992 graduation dates (in alphabetical order by last name):

Towards an Explanatory Division of Competence and Performance: a Language-Independent Parsing Scheme
Alphonce, Carl G.
URI : http://hdl.handle.net/2429/2075
Degree : Master of Science – MSc
Graduation Date : 1992-11
Supervisor : Dr. Poole

Link Strength in Bayesian Networks
Boerlage, Brent
URI : http://hdl.handle.net/2429/2041
Degree : Master of Science – MSc
Graduation Date : 1992-11
Supervisor : Dr. Lowe

Visualization of Multivariate Data Using Preattentive Processing
Healey, Christopher G.
URI : http://hdl.handle.net/2429/3321
Degree : Master of Science – MSc
Graduation Date : 1992-11
Supervisor : Dr. Booth

3D Interaction Studies Using the Shape-Matching Paradigm
Jang, Stanley
URI : http://hdl.handle.net/2429/3059
Degree : Master of Science – MSc
Graduation Date : 1992-11
Supervisor : Dr. Booth

Nested Group Communication for Wide-Area Networks
Liang, Luping
URI : http://hdl.handle.net/2429/3145
Degree : Doctor of Philosophy – PhD
Graduation Date : 1992-05
Supervisors : Dr. Chanson, Dr. Neufeld

Group communication concerns sending messages to receiver groups in distributed systems. A process group comprises a set of processes and encapsulates their internal interactions, thereby simplifying the interactions between user programs and groups of receiving processes. Although the basic idea was proposed a few years ago, few systems or applications take advantage of it due to a lack of a comprehensive understanding of the requirements of group communication with respect to different classes of applications, and a lack of operating system support to meet those requirements. This dissertation consists of two parts that address these deficiencies. The first part provides a comprehensive understanding of process groups by examining their potential applications, and the requirements to the system support expected by these applications. Groups are classified based on their structure and behavior. Also, a uniform treatment of grouping transparency is presented. The second part of this dissertation focuses on a particularly important aspect of group communication — group naming in an internet. For the purposes of maintaining subnet autonomy and reducing traffic on internet links, a nested group model is proposed to allow internet groups to contain other groups as members. By formalizing this nested group model using a name graph, two problems in group name resolutions are identified: resolution loops and resolution duplications. After analyzing existing methods (centralized vs. distributed dynamic methods) and identifying their deficiencies, we propose a novel distributed static method. Instead of detecting loops at the time of name resolution, the static method transforms the system view of the name graph into a special structure which is updated whenever there is a change in group membership. To guarantee correctness, the name graph transformation preserves the property that name resolutions based on the system's view of the name graph are consistent with respect to the users' view. Based on the assumption that name graph updates occur much less frequently than name resolutions, static method trades a higher overhead of name graph updates for a better performance of name resolution to gain an improved over all group message transport performance. In this part of the dissertation, a static shadow tree algorithm is designed and analyzed. The correctness arguments for the algorithm are provided and aspects such as concurrency control and failure handling in name graph updates are investigated as well. A prototype implementation of the algorithm is conducted as an existence proof to demonstrate implementation feasibility and to test the behavior of the algorithm.

Some New Results on Constructing Optimal Alphabetic Binary Trees
Mumey, Brendan M.
URI : http://hdl.handle.net/2429/3384
Degree : Master of Science – MSc
Graduation Date : 1992-11
Supervisor : Dr. Klawe

The Ship Model - A New Computational Model for Distributed Systems
Phillips, George William
URI : http://hdl.handle.net/2429/4601
Degree : Master of Science – MSc
Graduation Date : 1992-11
Supervisor : Dr.Chanson

A Bounded Delay Simulator
Reid, Robin Morris
URI : http://hdl.handle.net/2429/3137
Degree : Master of Science – MSc
Graduation Date : 1992-11
Supervisor : Dr. Seger

The Rapid Recovery of Three-Dimensional Structure from Line Drawings
Rensink, Ronald Andy
URI : http://hdl.handle.net/2429/3048
Degree : Doctor of Philosophy – PhD
Graduation Date : 1992-11
Supervisor : Dr. Woodham

A computational theory is developed that explains how line drawings of polyhedral objects can be interpreted rapidly and in parallel at early levels of human vision. The key idea is that a time-limited process can correctly recover much of the three-dimensional structure of these objects when split into concurrent streams, each concerned with a single aspect of scene structure. The work proceeds in five stages. The first extends the framework of Marr to allow a process to be analyzed in terms of resource limitations. Two main concerns are identified: (i) reducing the amount of nonlocal information needed, and (ii) making effective use of whatever information is obtained. The second stage traces the difficulty of line interpretation to a small set of constraints. When these are removed, the remaining constraints can be grouped into several relatively independent sets. It is shown that each set can be rapidly solved by a separate processing stream, and that co-ordinating these streams can yield a low-complexity "approximation" that captures much of the structure of the original constraints. In particular, complete recovery is possible in logarithmic time when objects have rectangular corners and the scene-to-image projection is orthographic. The third stage is concerned with making good use of the available information when a fixed time limit exists. This limit is motivated by the need to obtain results within a time independent of image content, and by the need to limit the propagation of inconsistencies. A minimal architecture is assumed, viz., a spatiotopic mesh of simple processors. Constraints are developed to guide the course of the process itself, so that candidate interpretations are considered in order of their likelihood. The fourth stage provides a specific algorithm for the recovery process, showing how it can be implemented on a cellular automaton. Finally, the theory itself is tested on various line drawings. It is shown that much of the three-dimensional structure of a polyhedral scene can indeed be recovered in very little time. It also is shown that the theory can explain the rapid interpretation of line drawings at early levels of human vision.