🚀 go-pugleaf

[ I have edited this announcement slightly to improve its appearance
on 80-column text screens.  -richard]


	                  TECHNICAL REPORT CENTER
	              DEPARTMENT OF COMPUTER SCIENCES
	             THE UNIVERSITY OF TEXAS AT AUSTIN
	                     TAYLOR HALL 2.124
	               AUSTIN, TEXAS  78712-1188 USA
	
	                       (512) 471-9595
	
	          INTERNET ADDRESS: trcenter@cs.utexas.edu
	
	         TECHNICAL REPORTS, MAY 1992  AUGUST 1992*
	
	          []  TR-92-27  $1.50     []  TR-92-35  $
	          []  TR-92-28  $1.50     []  TR-92-36  $
	          []  TR-92-29  $1.50     []  TR-92-37  $
	          []  TR-92-30  $1.50     []  TR-92-38  $
	          []  TR-92-31  $2.50     []  TR-92-38  $
	          []  TR-92-32  $1.50     []  TR-92-40  $
	          []  TR-92-33  $1.50     []  TR-92-41  $
	          []  TR-92-34  $5.00     []  TR-92-42  $
	
*PREPAYMENT IS REQUIRED. Please check the appropriate boxes and return this
sheet  along  with  your payment to place an order. Make U.S. bank check or
international money order payable to ``The University of  Texas''  (foreign
checks  must  be made in U.S. dollars and drawn on a U.S. bank).  Abstracts
of new TRs are distributed three times a year (in January,  May,  and  Sep-
tember).

TR-92-27    SOFTWARE COMPONENTS FOR OBJECT-ORIENTED DATABASE SYSTEMS
                            Don Batory and Devang Vasavada
                                       May 1992
                                    27 pages; $1.50
	
            ABSTRACT: Genesis is a software system generator  for  database
            management systems that relies exclusively on as-is large scale
            component reuse.   We  briefly  review  the  general  model  of
            software  components on which Genesis is based and also discuss
            some component libraries for  relational  database  systems  in
            terms  of  this  model.   We  then  explain how we have evolved
            Genesis and its libraries to  be  able  to  synthesize  object-
            oriented  database  systems.  We study a subproblem of creating
            ``self-tuning'' software systems by examining  the  performance
            of selected components for object-oriented database systems.

            Keywords: Inheritance, large  scale  reuse,  GenVoca,  Genesis,
            relational database systems, object-oriented database systems.



TR-92-28    IMPLEMENTING A DOMAIN MODEL FOR DATA STRUCTURES
                      Don Batory, Vivek Singhal, and Marty Sirkin
                                       May 1992
                                    24 pages; $1.50

            ABSTRACT: We present a model of the data structure domain  that
            is  expressed  in terms of the GenVoca domain modeling concepts
            [Bat91]. We show how familiar data structures can  be  encapsu-
            lated  as  realms  of  plug-compatible, symmetric, and reusable
            components, and we show how  complex  data  structures  can  be
            formed  from  their  composition. The target application of our
            research is a precompiler for specifying and generating custom-
            ized data structures.

            Keywords: Software building-blocks, domain  modeling,  software
            reuse, data structures.



TR-92-29    SOFTWARE COMPONENTS IN A DATA STRUCTURE PRECOMPILER
                      Marty Sirkin, Don Batory, and Vivek Singhal
                                       May 1992
                                    23 pages; $1.50

            ABSTRACT: PREDATOR is a data structure  precompiler  that  gen-
            erates efficient code for maintaining and querying complex data
            structures.  that embodies a novel component  reuse  technology
            that  transcends traditional generic data types. In this paper,
            we explain the concepts of PREDATOR and our prototype. We  show
            how complex data structures can be specified as compositions of
            software building blocks and present performance  results  that
            compare PREDATOR output to hand-optimized programs.


            Keywords: Components, software  reuse,  compiler,  data  struc-
            tures.



TR-92-30    FP + OOP = HASKELL
                                     Emery Berger
                                       May 1992
                                    9 pages; $1.50

            ABSTRACT: The programming language Haskell adds object-oriented
            functionality (using a concept known as _t_y_p_e _c_l_a_s_s_e_s) to a pure
            functional programming framework. This  paper  describes  these
            extensions  and  analyzes  its  accomplishments as well as some
            problems.

            Keywords:  Haskell,  functional  programming,  object-oriented,
            type classes.



TR-92-31    CLOSURE AND CONVERGENCE:  A FOUNDATION OF  FAULT-TOLERANT  COM-
            PUTING
                             Anish Arora and Mohamed Gouda
                                       July 1992
                                    38 pages; $2.50

            ABSTRACT: We give a formal definition of what it  means  for  a
            system  to  ``tolerate'' a class of ``faults''.  The definition
            consists of two conditions: First, if a fault occurs  when  the
            system state is within a set of ``legal'' states, the resulting
            state is within some larger set and, if faults continue  occur-
            ring,  the  system  state  remains within that larger set (_C_l_o_-
            _s_u_r_e). Second, if faults stop occurring, the system  eventually
            reaches  a  state within the legal set (_C_o_n_v_e_r_g_e_n_c_e). We demon-
            strate the applicability of our definition for  specifying  and
            verifying  the fault-tolerance properties of a variety of digi-
            tal and computer systems. Further,  using  the  definition,  we
            obtain  a  simple classification of fault-tolerant systems, and
            discuss methods for the  systematic  design  of  fault-tolerant
            systems.

            Keywords: Fault-tolerance, reliability,  algorithms,  verifica-
            tion, design, masking, stabilizing, closure, convergence.



TR-92-32    EXPERIMENTAL EVALUATION OF TECHNIQUES FOR FAULT TOLERANCE
                 Luiz A. Laranjeira, Miroslaw Malek, and Roy Jenevein
                                       July 1992
                                    16 pages; $1.50

            ABSTRACT: In the design  of  critical  applications  that  must
            deliver  continuous  service under real-time constraints  it is
            of essence to have fault tolerance achieved with  as  low  time
            redundancy  as  possible.  Furthermore, in the case of embedded
            systems, space may also be a limited resource.  Therefore,  for
            critical  applications,  we are left with the task of providing
            reliable computing with low space  _a_n_d  time  redundancy.   The
            quantification  of space and time redundancy in the implementa-
            tion of fault tolerance is consequently a must.

            We present the results of practical  experiments,   implemented
            on   a   multiprocessor  platform,  with  several  general  and
            application-specific technique for fault  tolerance.  The  time
            and space overheads incurred by each technique are analyzed and
            compared. Three  iterative  algorithms  were  utilized  in  the
            experiments:  solution of Laplace equations, the calculation of
            the invariant distribution of Markov chains, and  the  solution
            of  systems  of  linear  equations.  Fault-tolerant versions of
            those algorithms were implemented  with two general  techniques
            for fault tolerance (triplication with voting and checkpointing
            and rollback) and  three  application-specific  techniques  for
            fault  tolerance  (self  stabilization,  algorithm-based  fault
            tolerance, and natural redundancy). The results of the  experi-
            ments  show  that the approach based on natural redundancy, for
            applications  possessing  that  property,  presents  the   most
            attractive  cost/benefit  ratio  when  only  single  faults are
            likely to occur. The  implementations  of  the  above-mentioned
            algorithms  with  this  technique  demanded  less than 15% time
            redundancy for  problems  of  significant  size  in  fault-free
            situations,  only  one extra iteration to recover from a fault,
            and no extra processors.  These  capabilities  seem  ideal  for
            critical  applications  that must deliver reliable service in a
            timely manner. Surprisingly,  time  overheads  for  some  other
            methods were much higher than expected.

            Keywords: Critical applications,  experimental results,  fault-
            tolerant  algorithms,  techniques  for fault tolerance, natural
            redundancy,   parallel   algorithms,    real-time    computing,
            space/time redundancy.



TR-92-33    A TAXONOMY OF SHARED ADDRESS SPACE SYSTEMS
                            Banu Ozden and Avi Silberschatz
                                      July  1992
                                   30  pages; $1.50

            ABSTRACT: The availability of 64-bit processors enables operat-
            ing  systems the use of the shared address space (SAS) paradigm
            where all processes execute in the same address space. This  is
            in  contrast  to  most  existing operating systems that use the
            private address space (PAS) paradigm where each  process  views
            the  entire  space  as  dedicated  to itself.  The PAS paradigm
            yields high overhead for interprocess communication  and  shar-
            ing, whereas the SAS paradigm can reduce the cost of communica-
            tion and provide simple abstractions to the  application  level
            to  build  variety  of communication schemes.  Furthermore, the
            use of the SAS paradigm results  in  increased  system  perfor-
            mance.

            The SAS paradigm can be classified into  various  models, which
            differ  in  the way the address space and protection domain are
            managed.

            In this paper, we provide a taxonomy of the SAS models and dis-
            cuss the tradeoffs between these models.

            Keywords: Large address  space  system,  shared  address  space
            paradigm,  private  address  space paradigm, 64-bit processors,
            address space management, protection domain management.




TR-92-34    SPECIFICATION  AND VERIFICATION OF  LARGE-SCALE  REACTIVE  PRO-
            GRAMS
                                  Mark G. Staskauskas
                                      August 1992
                                   192 pages; $5.00

            ABSTRACT: The UNITY methodology has  attracted  wide  attention
            because of its elegant logic for specifying and reasoning about
            concurrent programs.  However, the UNITY  examples  tackled  so
            far  are  much  smaller  in  scale  than the problems typically
            encountered in practice. The goal of this dissertation  is  the
            identification of extensions to UNITY that will enable it to be
            applied to significantly larger problems. To  explore  possible
            extensions, we have applied UNITY to three large-scale examples
            drawn from industrial applications: the I/O  subsystem  portion
            of  the  GCOS operating system; a distributed electronic funds-
            transfer system; and a telephone-switching system.

            Keywords: Program verification, concurrent program development,
            formal  methods  in software engineering, formal specification,
            temporal logic, reactive programs, UNITY, resource  allocation,
            stepwise refinement.

===========================================================================
Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
    compdoc-techreports-request@ftp.cse.ucsc.edu