Abstracts for the Graduate Research Conference April 4, 1997


Reliable Distributed Computing with Transactional Distributed Shared Memory
Pedro Souto
Transactional distributed shared memory integrates transactions with distributed shared memory. Transactional distributed shared memory supports reliable distributed computing and provides a simple programming paradigm. It is particularly suitable to build distributed applications in a local area environment, that share a somewhat large amount of data that must survive system failures. In this talk I will give an overview of transactional distributed shared memory and I will illustrate its simplicity and power by showing how it can be used to design and implement an ``yellow pages'' service.

Reconstruction and Visualization of 3D Colonic Surface
Lichan Hong
This talk presents an innovative technology called "3D virtual colonoscopy", which incorporates several advanced visualization techniques to enable the physician to virtually examine the inner surface of the entire colon for identifying and inspecting colonic polyps. We first describe our unique process of acquiring and reconstructing a patient's colon model, followed by the novel visualization algorithms that we have developed to provide automatic planned navigations as well as interactive guided navigations inside the colon. Finally, we present our experimental results on a simulated pipe phantom, the Visible Human data set, and patient data.

Design and Performance of an Assertional Concurrency Control System
David S. Gerstl
(work by: Arthur J. Bernstein, David S. Gerstl, Wai-Hong Leung, Philip M. Lewis)
Serializability has been widely accepted as the correctness criterion for databases subject to concurrent access. Serializable execution is generally implemented using a two-phase locking algorithm that locks items in the database to delay transactions that are in danger of performing in a non-serializable fashion. Such delays are unacceptable in high-performance database systems and in systems supporting long-running transactions.
A number of models have recently been proposed in which transactions are decomposed into smaller, atomic, interleavable steps. These models have the potential for improving performance since locks are released at the end of each step. Serializability of transactions is no longer guaranteed, however. A shortcoming of much of this work is that little guidance is provided as to how transactions should be decomposed and what interleavings preserve correct execution.
We have proposed a new correctness criterion, weaker than serializability, that guarantees that each transaction satisfy its specification. Based on that correctness criterion, we have designed and implemented a new concurrency control within the \Ingres database management system. We then performed experiments using the \Tpcc Benchmark Transactions, which we decomposed into steps according to our theory. The experiments demonstrate significant improvement for benchmark transactions when lock contention is high, when long running transactions are a part of the transaction suite, and when sufficient system resources are present to support the additional concurrency that the new control makes possible.

Software Design, Specification, and Verification: Lessons Learned from the Rether Case Study
Xiaoqun Du
(work by: Xiaoqun Du, Kevin McDonnell, Evangelos Nanos, Y.S. Ramakrishna, Scott A. Smolka)
Rether is a software-based real-time ethernet protocol developed at SUNY Stony Brook. The purpose of this protocol is to provide guaranteed bandwidth and deterministic, periodic network access to multimedia applications over commodity ethernet hardware. It has been implemented in the FreeBSD 2.1.0 operating system, and is now being used to support the Stony Brook Video Server (SBVS), a low-cost, ethernet LAN-based server providing real-time delivery of videos to end users from the server's disk subsystem.
Using local model checking, as provided by the Concurrency Factory specification and verification environment, we showed (for a particular network configuration) that Rether indeed makes good on its bandwidth guarantees to real-time nodes without exposing non-real-time nodes to the possibility of starvation. In the course of specifying and verifying Rether, we identified an alternative design of the protocol that warranted further study due to potential efficiency gains. Again using model checking, we showed that this alternative design also possesses the properties of interest.

WFL - WebFlow Logic
Hasan Davulcu
A workflow can simply be defined as a set of tasks that cooperate to implement a business process. Executing a workflow thus involves coordinated execution of multiple long-running steps in an environment of distributed, heterogeneous processing entities.
The WebFlow Logic project is exploring the use of declarative, logic-based languages for specifying and reasoning about workflows.
At present, we have a prototypical WebFlow Logic (WFL) system implemented in XSB (an efficient deductive database system).
The WFL system is tolerant to crashes and the workflows in progress are recovered automatically when the server is back up. This is due to the fact that WFL is stateless, and all information about active workflows is stored in the Jasmine object-oriented database.

Multi-Resolution Indexing for Multimedia Database
Kevin Kreeger
One of the major challenges with multimedia database systems is to provide a content-based rather than textual-based query interface. This problem can be formulated as a nearest-neighbor search in a multi-dimensional feature space, which typically has a well-defined distance metric between a given pair of features. We have found that the calculation of these distance metrics accounts for a significant portion of the overall query service time. In this research, we investigate the feasibility of employing multi-resolution media representation to reduce the computation overhead of distance metric calculation, with the goal of improving the overall query service performance. In this talk, we will present two specific approaches of multi-resolution indexing, as applied to the polygonal shape image database system that is built in the Parallel Multimedia Index Server (PAMIS) project.

An Implementation Framework for On-Line Analytical Processing
Allen Ballman
On-Line Analytical Processing (OLAP) abstracts high-level information from raw data sets stored in large-scale data repository, whose capacity is usually on the order of hundreds of Gigabytes to Terabytes. The performance of OLAP systems is typically improved via pre-computation of query results, so that the run-time query delay is reduced. In this paper, we start with a description of the capabilities of OLAP systems, their operational characteristics, and a taxonomy of existing OLAP systems according to the amount and extent of query pre-computation. We then present a framework to describe the detailed implementation issues of a particular approach towards OLAP called the computation cache, which allows system designers the flexibility of space/time tradeoffs based on database characteristics and query patterns. Lastly, we present the high level design of a parallel OLAP system called Babbage based on a network of workstations, and its parallel I/O subsystem.

Cube4: Real-Time Volume Rendering Architecture
Baoquan Chen and Arie Kaufman
We describe a high-performance special-purpose system, Cube-4, for displaying and manipulating high-resolution volumetric datasets in real-time. A primary goal of Cube-4 is to render 512x 512 x 512, 16-bit per voxel, datasets at about 30 frames per second. Cube-4 implements a ray-casting algorithm in a highly-parallel and pipelined architecture, using a 3D skewed volume memory. Each pipeline includes 3D interpolation, gradient/shading and compositing unit. The main focus of this talk is on slice-parallel data flow approach, while several approaches exist.

Internet Phone Server
Praveen Arora
The basic idea of IPS is same as the other internet phone softwares available have i.e. to route a phone call directly over the internet. But the novelty here is that a user does not need to have any PC at his disposal for him to get the internet phone services as is required in the internet phone softwares available. Neither he has to get an internet connection nor he has to bother about any IP addresses. With the help of this service the user will call up an IPS in his area through his phone, which will connect him to his desired phone by routing the call over internet to another IPS in the destination area and finally to the destination phone. It has been implemented also, but finally we have ran into echo cancellation problem.

Superconductor Interprocessor Networks for Petaflop Supercomputers
Dmitry Zinoviev
(work by C. Reed, L. Wittie, D. Zinoviev, and K. Likharev)
As a part of the PetaFLOP supercomputer point study, we have considered several high-throughput, low-latency networks that can be used for interprocessor and processors-memories communications, and estimated the parameters of those networks. Superconductor implementations of the networks have been proposed based on the RSFQ logic/memory family.

Adaptive Real-Time Level-Of Detail-Based Rendering For Polygonal Models
Jihad Ell-Sana and Amitabh Varshney
We present an algorithm for performing adaptive real-time level-of-detail-based rendering for triangulated polygonal models. The simplifications are dependent on viewing direction, lighting, and visibility and are performed by taking advantage of image-space, object-space, and frame-to-frame coherences. In contrast to the traditional approaches of precomputing a fixed number of level-of-detail representations for a given object our approach involves statically generating a continuous level-of-detail representation for the object. This representation is then used at run-time to guide the selection of appropriate triangles for display. The list of displayed triangles is updated incrementally from one frame to the next. Our approach is more effective than the current level-of-detail-based rendering approaches for most scientific visualization applications where there are a limited number of highly complex objects that stay relatively close to the viewer. Our approach is applicable for scalar (such as distance from the viewer) as well as vector (such as normal direction) attributes.