Publications for Sean Quinlan

Security in Plan 9

Authors:

Russ Cox, Eric Grosse, Rob Pike, Dave Presotto, and Sean Quinlan

Publication:

USENIX Security Symposium, 2002.

Awarded best paper!

Abstract:

The security architecture of the Plan 9(tm) operating system has recently been redesigned to address some technical shortcomings. This redesign provided an opportunity also to make the system more convenient to use securely. Plan 9 has thus improved in two ways not usually seen together: it has become more secure and easier to use.

The central component of the new architecture is a per-user self-contained agent called factotum. Factotum securely holds a copy of the user's keys and negotiates authentication protocols, on behalf of the user, with secure services around the network. Concentrating security code in a single program offers several advantages including: ease of update or repair to broken security software and protocols; the ability to run secure services at a lower privilege level; uniform management of keys for all services; and an opportunity to provide single sign on, even to unchanged legacy applications. Factotum has an unusual architecture: it is implemented as a Plan 9 file server.

Venti: a new approach to archival storage

Authors:

Sean Quinlan and Sean Dorward

Publication:

First USENIX conference on File and Storage Technologies, 2002.

Awarded best paper!

Abstract:

This paper describes a network storage system, called Venti, intended for archival data. In this system, a unique hash of a block's contents acts as the block identifier for read and write operations. This approach enforces a write-once policy, preventing accidental or malicious destruction of data. In addition, duplicate copies of a block can be coalesced, reducing the consumption of storage and simplifying the implementation of clients. Venti is a building block for constructing a variety of storage applications such as logical backup, physical backup, and snapshot file systems.

We have built a prototype of the system and present some preliminary performance results. The system uses magnetic disks as the storage technology, resulting in an access time for archival data that is comparable to non-archival data. The feasibility of the write-once model for storage is demonstrated using data from over a decade's use of two Plan 9 file systems.

Robust Data Compression of Network Packets (Draft)

Authors:

Sean Dorward and Sean Quinlan

Publication:

Submitted to Data Compression Conference, 2000

Abstract:

This paper describes an approach for compressing data packets that enables inter-packet compression without the drawback of multiplying the effect of packet loss. By adding an acknowledgment scheme, the sender can limit the history state used by the compression algorithm to those packets that have been correctly received. A vector identifying the packets used as history is included in the compressed packet, enabling the receiver to reconstruct the history state required to decompress the packet. This approach improves the compression achieved compared to stateless schemes, while retaining robustness in the face of packet loss or reordering.

The paper reports several simulation experiments using our approach. We first describe an implementation based on the publicly available zlib implementation of the popular deflate compression format. We then describe the implementation of a Lempel-Ziv '77 variant called thwack that is more efficient at handling the unpredictable history state used to compress and decompress packets.

Real-Time Modification of Collision-Free Paths

Author:

Sean Quinlan

Publication:

Ph.D. Thesis, Stanford University, 1994

Abstract:

The modification of collision-free paths is proposed as the basis for a new framework to close the gap between global path planning and real-time sensor-based robot control. A physically-based model of a flexible string-like object, called an elastic band, is used to determine the modification of a path. The initial shape of the elastic is the free path generated by a planner. Subjected to artificial forces, the elastic band deforms in real time to a short and smooth path that maintains clearance from the obstacles. The elastic continues to deform as changes in the environment are detected by sensors, enabling the robot to accommodate uncertainties and react to unexpected and moving obstacles. While providing a tight connection between the robot and its environment, the elastic band preserves the global nature of the planned path. The greater part of this thesis deals with the design and implementation of elastic bands, with emphasis on achieving real-time performance even for robots with many degrees of freedom. To achieve these goals, we propose the concept of bubbles of free-space---a region of free-space around a given configuration of the robot generated from distance information. We also develop a novel algorithm for efficiently computing the distance between non-convex objects and a real-time algorithm for calculating a discrete approximation to the time-optimal parameterization of a path. These various developments are combined in a system that demonstrates the elastic band framework for a Puma 560 manipulator.

Efficient Distance Computation between Non-Convex Objects

Author:

Sean Quinlan

Publication:

IEEE International Conference on Robotics and Automation, 1994

Abstract:

This paper describes an efficient algorithm for computing the distance between non-convex objects. Objects are modeled as the union of a set of convex components. From this model we construct a hierarchical bounding representation based on spheres. The distance between objects is determined by computing the distance between pairs of convex components using preexisting techniques. The key to efficiency is a simple search routine that uses the bounding representation to ignore most of the possible pairs of components. The efficiency can further be improved by accepting a relative error in the returned result. Several empirical trials are presented to examine the performance of the algorithm.

Elastic Bands: Connecting Path Planning and Control

Authors:

Sean Quinlan and Oussama Khatib

Publication:

IEEE International Conference on Robotics and Automation, 1993

Abstract:

Elastic bands are proposed as the basis for a new framework to close the gap between global path planning and real-time sensor-based robot control. An elastic band is a deformable collision-free path. The initial shape of the elastic is the free path generated by a planner. Subjected to artificial forces, the elastic band deforms in real time to a short and smooth path that maintains clearance from the obstacles. The elastic continues to deform as changes in the environment are detected by sensors, enabling the robot to accommodate uncertainties and react to unexpected and moving obstacles. While providing a tight connection between the robot and its environment, the elastic band preserves the global nature of the planned path. This paper outlines the framework and discusses an efficient implementation based on bubbles.

Towards Real-Time Execution of Motion Tasks

Authors:

Sean Quinlan and Oussama Khatib

Publication:

in Experimental Robotics 2, ed. R. Chatila and G. Hirzinger, Springer-Verlag, 1993

Abstract:

The goal of the research described in this paper is to build robotic systems that can execute motion tasks in real time. We present two ideas towards this goal: a real-time path planner for static three-dimensional configuration spaces and a new framework for the integration of planning and control. The planner is based on a new class of cells, {\em slippery cells}, incorporated in an approximate cell decomposition algorithm. The {\em elastic band} concept is proposed to provide an effective link between planning and execution. With elastic bands, a path is treated as a flexible entity. The initial configuration of the elastic band is the path provided by the planner. The shape of the elastic dynamically evolves during execution, using sensory data about the environment.

A Cached WORM File System

Author:

Sean Quinlan

Publication:

Software - Practice & Experience, 21(12), pp. 1289-1299, 1991

Abstract:

This paper describes a general-purpose file system that uses a write-once-read-many (WORM) optical disk accessed via a magnetic disk cache. The cache enables blocks to be modified multiple times before they are written to the WORM and increases performance. Snapshots of the file system can be made at any time without limiting the users' access to files. These snapshots reside entirely on the WORM, are accessible to the user via a second read-only file system, do not contain multiple copies of unchanged data, and can be used to rebuild the file system in the event that the disk cache is destroyed. The file system has been implemented as part of Plan 9, an experimental operating system under development at AT&T Bell Laboratories.

Last modified: 8/30/2002