From: shapiro@yoko.inria.fr (Marc Shapiro)
Newsgroups: comp.doc.techreports
Subject: Reports from INRIA/SOR
Date: 15 Dec 1992 18:07:44 GMT
Organization: INRIA -- Institut National de Recherche en Informatique et Automatique -- Rocquencourt, France
Reply-To: Marc Shapiro <shapiro@corto.inria.fr>
NNTP-Posting-Host: oak.ucsc.edu
Originator: golding@oak


A number of new publications (articles and tech reports) are available
by anonymous FTP from the INRIA group SOR.

For a terse project description and a long bibliography of the SOR
group, retrieve the file SOR.ps.Z.

The rest of this message consists of:
        1. FTP instructions
        2. a list of the new reports
        3. abstracts of the new reports

						Marc Shapiro

M. Shapiro, INRIA, B.P. 105 Rocquencourt, 78153 Le Chesnay Cedex, France.
Tel.: +33(1)39-63-53-25; fax: +33(1)39-63-53-30; e-mail: marc.shapiro@inria.fr

======================================================================

                      1.  F T P   I N S T R U C T I O N S
                      ===================================
                                   
Publications of the INRIA/SOR group available by anonymous FTP:
        Host:      ftp.inria.fr [128.93.1.26]
        Login:     ftp
        Password:  your own e-mail address
        Directory: INRIA/publication/SOR

The papers are compressed 300dpi Postscript.  Remember to use FTP `binary'
or `image' mode when transferring compressed files.  Hardcopy can be
ordered by sending e-mail to Nelly Maloisel <nelly.maloisel@inria.fr>.

The file README contains a full list of all the papers available by FTP,
ordered most recent first.  (This is the only file in plain ASCII.)

The file SOR.ps.Z contains a project description and bibliography,
periodically updated.

======================================================================

            2.   L I S T   O F   T H E   N E W   P A P E R S
            ================================================

SSPC:rr1799.ps.Z	"SSP Chains: Robust, Dist. References Supporting
			Acyclic Garbage Collection", M.  Shapiro, P.  Dickman,
			D. Plainfoss\'e.  Rapport de Recherche INRIA 1799 and
			Broadcast Technical Report no. 1.

KFS:rr-1809.ps.Z	"KFS: Le syst\`eme de fichiers de Kitlog".  C.
		        Fouqu\'e.  Rapport de Recherche INRIA 1809.
                        (In French) 

Kitlog:srds.ps.Z	"Kitlog: a Generic Logging Service". M. Ruffin.  11th
			Symp. on Reliable Dist. Systems (SRDS), Houston TX
			(USA), Oct 1992.

FI:usenixWinter93.ps.Z	"Fault Interpretation: Fine-Grain Monitoring of Page
		        Accesses", D. Edelson.  1993 Usenix Winter Conference,
		        San Diego CA (USA), jan 1993

GFOSFDSS:iwooos92.ps.Z	"A Generic Fragmented Object Structured Framework for
			Distributed Storage Support", H. Soulard, M.
			Makpangou.  3d Int. Workshop on Object-Orientation in
			Operating Systems, Dourdan, France, Sept. 1992.

RFOM:iwooos92.ps.Z	"A Refinement of the Fragmented Object Model", P.
			Dickman, M. Makpangou.  3d Int. Workshop on
			Object-Orientation in Operating Systems, Dourdan,
			France, Sept. 1992.

DGCOOS:iwooos92.ps.Z	"A Distributed GC for Object Oriented Systems", D.
			Plainfoss\'e, M. Shapiro.  3d Int. Workshop on
			Object-Orientation in Operating Systems, Dourdan,
			France, Sept. 1992.

IRCL:iwooos92.ps.Z	"Implementing References as Chains of Links", J.
			Maisonneuve, M. Shapiro, P. Collet.  3d Int. Workshop
			on Object-Orientation in Operating Systems, Dourdan,
			France, Sept. 1992.

PC++GC:iwmm92.ps.Z	"Precompiling C++ for Garbage Collection", D.  Edelson.
			Int. Workshop on Memory Management, Saint-Malo (France)
			sept. 1992.

EFTGC:iwmm92.ps.Z	"Experience with a Fault-Tolerant Garbage Collector in
			a Distributed Lisp System", D. Plainfoss\'e, M.
			Shapiro.  Int. Workshop on Memory Management,
			Saint-Malo (France) sept. 1992.

SPC++:usenixC++92.ps.Z	"Smart Pointers: They're Smart, but They're Not
			Pointers", D. Edelson.  Usenix C++ Conf., Portland OR
			(USA), aug. 1992.

======================================================================

                        3.   A B S T R A C T S
		  	======================

----------------------------------------------------------------------
SSPC:rr1799.ps.Z

              SSP Chains: Robust, Distributed References
                Supporting Acyclic Garbage Collection
                                   
           Marc Shapiro, Peter Dickman, David Plainfoss\'e
Rapport de Recherche INRIA 1799 and Broadcast Technical Report no. 1.

                               ABSTRACT

SSP chains are a novel technique for referencing objects in a distributed
system.  To client software, any object reference appears to be a local
pointer; when the target is remote, an SSP chain adds an indeterminate
number of levels of indirection.  Copying a reference across the
distributed system extends an SSP chain at one end; migrating the target
object extends it at the other end.  Invocation through an SSP chain is
efficient: each stage of an SSP chain contains location information and
long chains are short-cut at invocation time.  These actions require
(almost) no extra messages in addition to those of the client application.
The rules for creating, using, modifying and deleting SSP chains are stated
precisely and maintain well-defined invariants.  The invariants hold even
in the presence of message failures (loss, duplication, late delivery);
after a crash, the existence invariants must be re-established.  SSP chains
support distributed garbage collection (GC); we present a robust
distributed variant of reference counting.  The techniques presented here
are cheap, robust, widely applicable, and scalable.

----------------------------------------------------------------------
KFS:rr-1809.ps.Z

                       KFS: Kitlog File System
                              (in French)

			   Carole Fouqu\'e

			       ABSTRACT

This report describes the design of KFS (Kitlog File System). KFS is a
log-structured file system implemented on top of the general purpose
logging service Kitlog. This work validates the Kitlog model by showing
that services provided by a generic logging tool adequatly support the
specific needs of the file system. As a result, the design of the KFS file
system is simplified, because a number of usefull mechanisms such as free
space management or data lookup are already supported by the Kitlog logging
service.

----------------------------------------------------------------------
Kitlog:srds.ps.Z	

                  Kitlog: a Generic Logging Service
                                   
                            Michel Ruffin
11th Symp. on Reliable Dist. Systems (SRDS), Houston TX (USA), Oct 1992.

A generic logging service should cater to the variable and even
antagonistic needs of clients, without imposing unnecessary overhead on
clients that do not use all of its functions.  Kitlog provides an original
solution to this problem by decomposing logging characteristics into five
mechanisms: buffering policy, distribution of records, replication of
records, sharing of logs, and management of physical media.  Each
characteristic is embodied in a class.  For each class, multiple policy
implementations can be provided.  Instances of these classes are stackable
in any appropriate number or order. A client customizes his log, to a
particular set of failure assumptions, by selecting adequate classes,
instantiating them, and connecting the instances together.

----------------------------------------------------------------------
FI:usenixWinter93.ps.Z

     Fault Interpretation: Fine-Grain Monitoring of Page Accesses
				   
			  Daniel R. Edelson

			       ABSTRACT

This paper presents a technique for obtaining fine-grain information about
page accesses from standard virtual memory hardware and Unix operating
system software. This can be used to monitor all user-mode accesses to
specified regions of the address space of a process.  Application code can
intervene before and/or after an access occurs, permitting a wide variety
of semantics to be associated with memory pages.  The technique facilitates
implementing complex replication or consistency protocols on transparent
distributed shared memory and persistent memory. The technique can also
improve the efficiency of certain generational and incremental garbage
collection algorithms.  This paper presents our implementation and suggest
several others.  Efficiency measurements show faults to be about three
orders of magnitude more expensive than normal memory accesses, but two
orders of magnitude less expensive than page faults.  Information about how
to obtain the code via anonymous ftp appears at the end of the paper.

----------------------------------------------------------------------
GFOSFDSS:iwooos92.ps.Z

         A Generic Fragmented Object Structured Framework for
                     Distributed Storage Support

                  Herv\'e Soulard, Mesaac Makpangou
     3d Int. Workshop on Object-Orientation in Operating Systems
                     Dourdan, France, Sept. 1992.

                               ABSTRACT

We propose a generic framework for storage support in a distributed
environment.  This comprises a set of storage abstractions and storage
policies: data clusters, cluster containers, and container domains,
supporting sharing, caching, and replication.  These abstractions and these
policies are structured as fragmented objects (FOs), such that each storage
system designer can offer the appropriate tradeoffs to its targeted
applications.  The core set of abstractions is discussed, their interfaces
are presented, and the FO-structuring of the cluster abstraction is
detailed.

----------------------------------------------------------------------
RFOM:iwooos92.ps.Z

             A Refinement of the Fragmented Object Model
                                   
                   Peter Dickman, Mesaac Makpangou
     3d Int. Workshop on Object-Orientation in Operating Systems
                     Dourdan, France, Sept. 1992.
                                   
                               ABSTRACT

Fragmented Objects offer an interesting alternative to the use of uniform
transparent object references in distributed systems.  This novel paradigm
for distributed programming provides facilities for the encapsulation of
policy issues, as well as implementation details such as communication
mechanisms and consistency requirements. At the same time a clean and
comprehensible model is offered to both FO designers and client
programmers.  A number of omissions in earlier papers on this topic are
rectified here, and certain mechanisms are generalised to increase both the
power and the expressiveness of the model.  In particular, FO interfaces
are extended to include upcalls and a new internal model, based on the
fragment factory, is introduced.

----------------------------------------------------------------------
DGCOOS:iwooos92.ps.Z

             A Distributed GC for Object Oriented Systems
                                   
                   David Plainfoss\'e, Marc Shapiro
     3d Int. Workshop on Object-Orientation in Operating Systems
                     Dourdan, France, Sept. 1992.
                                   
                               ABSTRACT

We describe a distributed garbage collector protocol targeted for
uncooperative distributed object oriented systems.  The protocol has been
implemented on distributed Lisp system and a few performance measurements
are discussed. Since this implementation, we have refined deeply the
protocol to address non FIFO channels. A new reference model is proposed
along with the protocol to improve invocation efficiency.

----------------------------------------------------------------------
IRCL:iwooos92.ps.Z

              Implementing References as Chains of Links
                                   
           Julien Maisonneuve, Marc Shapiro, Pierre Collet
     3d Int. Workshop on Object-Orientation in Operating Systems
                     Dourdan, France, Sept. 1992.
                                   
                               ABSTRACT

The goal of this work is to provide uniform transparent access to objects,
be they local, remote, persistent, or mobile. In this way, we facilitate
distributed programming and persistence management.

An object (the {\em target}) is accessed through a {\em reference}.  A
reference retains its meaning as it is copied, stored, passed in messages,
and as the target migrates.  A reference is used to invoke a procedure (or
{\em method}) of the target object.  References support standard
single-space targets, as well as fragmented objects.  The cost of using a
reference to a local object is comparable to the cost of accessing the
object through a pointer.  In the implementation, a reference is a {\em
chain\/} of {\em links}.  Each link embodies a small piece of
functionality.  A chain may be composed of an arbitrary number of links.

----------------------------------------------------------------------
PC++GC:iwmm92.ps.Z

               Precompiling C++ for Garbage Collection
                                   
                            Daniel Edelson
 Int. Workshop on Memory Management, Saint-Malo (France) sept. 1992.
                                   
                               ABSTRACT

Our research is concerned with compiler-independent, efficient and
convenient garbage collection for C++.  Most collectors proposed for C++
have either been implemented in a library or in a compiler.  As an
intermediate step between those two, this paper proposes using
precompilation techniques to augment a C++ source program with code to
allow mostly type-accurate garbage collection.  There are two key
precompiler transformations.  The first is automatic generation of {\em
smart pointer\/} classes.  The precompiler defines the smart pointer
classes and the user utilizes them instead of raw pointers.  These smart
pointers supply functionality that allows the collector to locate the root
set for collection.  The second transformation augments the C++ program
with code that allows the garbage collector to locate internal pointers
within objects.  This paper describes the precompiler and the garbage
collector. The paper includes a brief (1500 word) survey of related
techniques.

----------------------------------------------------------------------
EFTGC:iwmm92.ps.Z

          Experience with a Fault-Tolerant Garbage Collector
                     in a Distributed Lisp System
                                   
                   David Plainfoss\'e, Marc Shapiro
 Int. Workshop on Memory Management, Saint-Malo (France) sept. 1992.
                                   
                               ABSTRACT

In order to evaluate our fault-tolerant distributed garbage collection
protocol, we have built a prototype implementation within a distributed
Lisp system, {\em Transpive}, replacing Piquer's native indirect reference
count distributed garbage collector.  This paper presents our protocol and
highlights implementation issues on Transpive.  In particular, we describe
the prototype and the alterations required to fit into the Transpive
distributed programming model. The message and CPU performance of our
protocol are measured and its fault-tolerance evaluated. We conclude that
the cost of our protocol is close to Piquers's, although our protocol has
greater functionality.

----------------------------------------------------------------------
SPC++:usenixC++92.ps.Z

       Smart Pointers: They're Smart, but They're Not Pointers
                                   
                            Daniel Edelson
           Usenix C++ Conf., Portland OR (USA), aug. 1992.
                                   
                               ABSTRACT

There are numerous times when a C++ user could benefit from a pointer
variant that has more functionality than is provided by the basic,
language-defined pointer.  For example, type-accurate garbage collection,
reference counting, or transparent references to distributed or persistent
objects, might be implemented with classes that provide pointer
functionality.  The C++ language directly supports one kind of pointer
substitute, the smart pointer, in the form of overloadable indirection
operators: -> and *.

In this paper we evaluate how {\em seamlessly\/} smart pointers can replace
raw pointers.  The ideal is for client code not to care whether it is using
raw pointers or smart pointers.  For example, if a typedef selects whether
raw or smart pointers are used throughout the program, changing the value
of the typedef should not introduce syntax errors.

Unfortunately, C++ does not support pointer substitutes well enough to
permit seamless integration.  This paper presents the desired behavior of
smart pointers in terms of the semantics of raw pointers that the smart
pointers try to emulate.  Then, we describe several ways of implementing
smart pointers. For each, we show cases in which the smart-pointers fail to
behave like raw pointers.  From among the choices, we explain which is the
best for emulating the standard pointer conversions.

Accessors are similar to smart pointers, but have certain advantages.  This
paper discusses the differences between accessors and smart pointers, and
shows why our conclusions about type conversion behavior also apply to
accessors.  Whether a programmer prefers smart pointers or accessors, this
paper shows the limitations and recommends an implementation.

======================================================================

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