Patents, Publications, etc. by Terence Kelly

Patents

Determining A Recurrent Problem Of A Computer Resource Using Signatures

US Patent 7,502,971 granted 10 March 2009
See also SOSP 2005 paper.

Publications

Efficiently Generating k-Best Solutions to Procurement Auctions

by Andrew Byde, Terence Kelly, Yunhong Zhou, and Robert Tarjan
AAIM, 15-17 June 2009, San Francisco, CA, USA
Also available as Springer LNCS volume 5564.
See also the 2006 HPL Tech report and 2006 ACM SIGecom Exchanges paper, below.

The Theory of Deadlock Avoidance via Discrete Control

by Yin Wang, Stephane Lafortune, Terence Kelly, Manjunath Kudlur, and Scott Mahlke
POPL, 21-23 January 2009, Savannah, Georgia, USA [ACM Digital Library] [local PDF]

Gadara: Dynamic Deadlock Avoidance for Multithreaded Programs

by Yin Wang, Terence Kelly, Manjunath Kudlur, Stephane Lafortune, and Scott Mahlke
OSDI, 8-10 December 2008, San Diego, CA, USA. [USENIX PDF] [local PDF]

Operational Analysis of Parallel Servers

by Terence Kelly, Kai Shen, Alex Zhang, and Christopher Stewart
MASCOTS, 8-10 September 2008, Baltimore, MD, USA. [local PDF]
Also available as HP Labs Tech Report HPL-2009-8

Brief Announcement: Operational Analysis of Processor Speed Scaling

by Kai Shen, Alex Zhang, Terence Kelly, and Christopher Stewart
SPAA, 14-16 June 2008, Munich, Germany. [ACM Digital Library] [local PDF]
Also available as HP Labs Tech Report HPL-2009-9

A Dollar from 15 Cents: Cross-Platform Management for Internet Services

by Christopher Stewart, Terence Kelly, Alex Zhang, and Kai Shen
USENIX Annual Tech, 22-27 June 2008, Boston, MA, USA. [USENIX PDF] [local PDF]
Also available as HP Labs Tech Report HPL-2009-7

The Application of Supervisory Control to Deadlock Avoidance in Concurrent Software

by Yin Wang, Terence Kelly, Manjunath Kudlur, Scott Mahlke, and Stephane Lafortune
WODES (Workshop on Discrete Event Systems), 28-30 May 2008, Goteborg, Sweden.

Estimating Cache Hit Rates from the Miss Sequence [tech report]

by Timothy Y. Chow, Terence Kelly, and Daniel Reeves
HP Labs Tech Report HPL-2007-155, 17 September 2007

AutoParam: Automated Control of Application-Level Performance in Virtualized Server Environments

by Zhikui Wang, Xue Liu, Alex Zhang, Christopher Stewart, Xiaoyun Zhu, and Terence Kelly, HP Labs
Feedback Control Implementation and Design (FeBID), 25 May 2007, Munich, Germany (Co-located with IM 2007)

Don't Settle for Less Than the Best: Use Optimization to Make Decisions

by Kimberly Keeton, Terence Kelly, Arif Merchant, Cipriano Santos, Janet Wiener, Xiaoyun Zhu (HP Labs) and Dirk Beyer (M-Factor)
HotOS XI, 7-9 May 2007, San Diego [USENIX PDF], [Local PDF]

Exploiting Nonstationarity for Performance Prediction

by Christopher Stewart, Terence Kelly, and Alex Zhang, HP Labs and University of Rochester
EuroSys 2007, 21-23 March 2007, Lisbon, Portugal. [ACM Digital Library] [Local PDF]
Also available as HP Labs Tech Report HPL-2007-64

Discrete Control for Safe Execution of IT Automation Workflows

by Yin Wang, Terence Kelly, and Stephane Lafortune, HP Labs and University of Michigan
EuroSys 2007, 21-23 March 2007, Lisbon, Portugal. [ACM Digital Library] [Local PDF]
Also available as HP Labs Tech Report HPL-2007-61
A short version appeared in HotDep 2006; see below.

Discrete Control for Dependable IT Automation [short paper]

by Yin Wang, Terence Kelly, and Stephane Lafortune, HP Labs and University of Michigan
Proceedings of HotDep 2006, 3 November 2006, [HotDep version]
A longer version appears in EuroSys 2007; see above.

Efficiently Generating k-Best Solutions for Procurement Auctions [tech report]

by Andrew Byde and Terence Kelly, HP Labs
19 October 2006: [HP Labs Tech Report HPL-2006-145]
See the SIGecom Exchanges paper below for problem statement and motivation. This paper presents a far superior algorithm. See the 2009 AAIM paper for a published version.

Predicting Performance in Distributed Enterprise Applications [tech report]

by Terence Kelly and Alex Zhang, HP Labs
HP Labs Tech Report HPL-2006-76, 4 May 2006
See also the WORLDS'05 paper below and the EuroSys 2007 paper with Christopher Stewart above.

Generating k-Best Solutions to Auction Winner Determination Problems

by Terence Kelly and Andrew Byde, HP Labs
27 April 2006 (good introduction, less detail): [ACM SIGecom Exchanges v.6 n.1, 12 pages] [ACM Digital Library]
2 March 2006 (more detail): HP Labs Tech Report HPL-2006-40 [10 pages, local PDF]
The algorithm presented here is inefficient. Read this early paper for the problem statement and motivation. See the tech report "Efficiently Generating k-Best..." and the AAIM 2009 paper above for a far better algorithm for generating solutions.

Detecting Performance Anomalies in Global Applications

by Terence Kelly, HP Labs
Second USENIX Workshop on Real, Large Distributed Systems (WORLDS 2005) [6 pages, local PDF]
See also the EuroSys 2007 paper "Exploiting Nonstationarity" and HP tech report 2006-76 above and the SOSP 2005 poster-paper summary:
"Transaction Mix Performance Models: Methods and Application to Performance Anomaly Detection" [1 page, local PDF]

Capturing, Indexing, Clustering, and Retrieving System History

by Ira Cohen, Steve Zhang, Moises Goldszmidt, Julie Symons, Terence Kelly, and Armando Fox
20th ACM Symposium on Operating Systems Principles (SOSP 2005) [ACM Digital Library] [local PDF]
Also available as HP Labs tech report 2005-158

An Extended Evaluation of Two-Phase Scheduling Methods for Animation Rendering

by Yunhong Zhou, Terence Kelly, Janet Wiener, Eric Anderson
11th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP 2005)
[workshop version, 16 pages, PDF] [Springer LNCS volume 3834 version, 23 pages, local PDF]
[See also the SPAA 2005 full paper and the SIGMETRICS 2005 poster.]

Value-Maximizing Deadline Scheduling and its Application to Animation Rendering

by Eric Anderson, Dirk Beyer, Kamalika Chaudhuri, Terence Kelly, Norman Salazar, Cipriano Santos, Ram Swaminathan, Robert Tarjan, Janet Wiener, Yunhong Zhou
17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005) [ACM Digital Library] [local PDF]
[See also the JSSPP 2005 paper and the SIGMETRICS 2005 poster.]

Deadline Scheduling for Animation Rendering [Poster]

by Eric Anderson, Dirk Beyer, Kamalika Chaudhuri, Terence Kelly, Norman Salazar, Cipriano Santos, Ram Swaminathan, Robert Tarjan, Janet Wiener, Yunhong Zhou
SIGMETRICS 2005 poster paper [2 pages, local PDF]
[For a complete description of this research project, see our SPAA 2005 and JSSPP 2005 papers.]

Correlating instrumentation data to system states: A building block for automated diagnosis and control

by Ira Cohen, Moises Goldszmidt, Terence Kelly, Julie Symons, HP Labs, and Jeff Chase, Duke University
Sixth Symposium on Operating Systems Design and Implementation (OSDI 2004), 6-8 December 2004, San Francisco
Also available as HP Labs tech report HPL-2004-183 [local PDF]

Generalized Knapsack Solvers for Multi-Unit Combinatorial Auctions: Analysis and Application to Computational Resource Allocation

by Terence Kelly, Hewlett-Packard Labs
Springer Lecture Notes in Artificial Intelligence, LNAI 3435 [local PDF]
HP Labs tech report 2004-21 [official HPL source] [local PostScript] [local PDF]
AMEC'04 paper (shorter but newer than TR) [from AMEC site, PDF] [local PostScript] [local PDF]
AAMAS'04 poster (2 pages) [IEEE DOI] [local PostScript]

Inducing Models of Black-Box Storage Arrays [Tech Report]

by Terence Kelly, Ira Cohen, Moises Goldszmidt, and Kim Keeton, HP Labs
11 June 2004
HP Labs tech report HPL-2004-108 [Local PDF]

Design, Implementation, and Evaluation of Duplicate Transfer Detection in HTTP

by Jeff Mogul, Yee Man Chan, and Terence Kelly, Hewlett-Packard Labs
First Symposium on Networked Systems Design and Implementation (NSDI'04), 29-31 March 2004, San Francisco
Also available as HP Labs tech report HPL-2004-29 [local PDF]

Utility-Directed Allocation

by Terence Kelly, Hewlett-Packard Labs
First Workshop on Algorithms and Architectures for Self-Managing Systems 11 June 2003, San Diego, California, USA
Workshop version [PostScript]
HP Labs Tech Report version [PDF] [local PDF]

Ph.D. Dissertation:
Optimization in Web Caching:
Cache Management, Capacity Planning, and Content Naming

by Terence Kelly, University of Michigan
ACM Doctoral Dissertation Award nominee
Rackham Distinguished Dissertation Award nominee (among top 40 of over 600 dissertations completed at U-M in 2002)
final version completed 29 July 2002: [PDF] [bz2 compressed PostScript]

Aliasing on the World Wide Web: Prevalence and Performance Implications

by Terence Kelly, University of Michigan and Jeffrey C. Mogul, Compaq Western Research Lab
Performance Track of the Eleventh International World Wide Web Conference 7-11 May 2002, Honolulu, Hawaii, USA
Final conference version of 19 March 2002, 12 pages:
WWW'02 conference Web site [PDF]
[ACM Digital Library] [local PDF]

Thin-Client Web Access Patterns: Measurements from a Cache-Busting Proxy

by Terence Kelly, University of Michigan
Computer Communications Vol. 25, No. 4 (March 2002) pp. 357-366 Published version [PDF]
First version appeared in Proceedings of the Sixth International Web Caching and Content Delivery Workshop 20-22 June 2001, Boston, Massachusetts
Workshop version of 11 June 2001, 9 pages: [PDF]

Optimal Web Cache Sizing: Scalable Methods for Exact Solutions

by Terence Kelly and Daniel Reeves, University of Michigan
Computer Communications Vol. 24, No. 2 (Feb 2001) pp. 163-173. Published version [PDF]
An earlier version appeared in the proceedings of The 5th International Web Caching and Content Delivery Workshop 22-24 May, Lisbon, Portugal
Workshop version of 29 April 2000, 12 pages: [PostScript] [PDF]
Slides for workshop presentation: [PostScript]
Priority depth (generalized stack distance) implementation in ANSI C

Variable QoS from Shared Web Caches: User-Centered Design and Value-Sensitive Replacement

by Terence Kelly, Sugih Jamin, and Jeffrey K. MacKie-Mason, University of Michigan
MIT Workshop on Internet Service Quality Economics, 2-3 December 1999, Cambridge, MA
12 November 1999, PostScript (published version), 14 pages.
This will eventually appear as a chapter in the MIT Press book, Internet Services [ISBN 0-262-13448-9]. However this book has taken aeons to publish. As of September 2005, it is listed in both MIT Press and Amazon as "September 2004." The publicity blurb about "clarifying the issues for a post-Internet bubble age" is particularly entertaining, considering that the entire contents of the book were finalized years before the bubble burst.

Biased Replacement Policies for Web Caches: Differential Quality-of-Service and Aggregate User Value

by Terence Kelly, Yee Man Chan, Sugih Jamin, and Jeffrey K. MacKie-Mason, University of Michigan
Fourth International Web Caching Workshop, San Diego, California, 31 March - 2 April 1999.
24 March 1999, PostScript (published version), 10 pages.
We present a simple generalization of least-frequently-used (LFU) replacement that is sensitive to varying levels of server valuation for cache hits. Through trace-driven simulation we show that our algorithm delivers a reasonable QoS relationship: higher byte hit rates for servers that value hits more. We furthermore demonstrate that our algorithm delivers higher aggregate value to servers than LRU or LFU.

An API for Internet Auctions

by Kevin O'Malley and Terence Kelly, University of Michigan
Dr. Dobb's Journal, September 1998, pp. 70-74.
Describes the client Application Programming Interface (API) to the Michigan Internet AuctionBot.

Relaxation Criteria for Iterated Traffic Simulations

by Terence Kelly and Kai Nagel, Los Alamos National Labs and Santa Fe Institute
International Journal of Modern Physics C, Volume 9 Number 1, pages 113-132.
12 December 1997, PostScript (published version), 20 pages
Defines and evaluates several empirical measures of equilibration/relaxation in automotive traffic networks, and applies these measures to the output of the TRANSIMS traffic simulator. Formerly available as Los Alamos unclassified technical report LA-UR 97-4453 at the TRANSIMS paper archive. Contact me for an earlier and much longer version of this paper containing more data.

Driver Strategy and Traffic System Performance

by Terence Kelly, Princeton University and Santa Fe Institute
Physica A, Volume 235, Number 3-4, pages 407-416.
PDF (published version), 10 pages
5 September 1996, PostScript (late draft), 11 pages
Explores the effects of several departure time selection strategies on overall traffic system performance in a simple simulation model of iterated rush-hour commuting. "ATIS at Rush Hour" (see below) addresses the same issues using a different simulation model.

Presentations

Market-Oriented Data Distribution for Information System Survivability

RAND Corporation, Santa Monica, California
1 September 1998, Handouts, compressed PostScript, 5 pages
This talk reviews the use and misuse of markets in the military, and suggests that automated software markets embedded within military information systems might enhance survivability by enabling large-scale data replication and by providing dynamic resource allocation. The talk also escribes a market-based Web cache management system and presents the results of a preliminary investigation of its performance via trace-driven simulation.

The Dining Bidders: Secure Auctions for a Paranoid World

Microsoft Research, Redmond, Washington
21 July 1998, Handouts, compressed PostScript, 4 pages
Describes a privacy-preserving security layer that can be wrapped around any type of auction. A draft paper is also available.

Older Unpublished Papers

These unpublished papers are drafts and should not be cited or quoted without permission of the author(s).

Extending the ALLONS Traffic Control Algorithm to Systems of Signalized Intersections

(13 January 1998, HTML (some figures missing) and PostScript, 23 pages)
Explores extensions of a single-intersection traffic signal control algorithm to systems of multiple intersections. The control problem is formulated as the search of a tree-structured decision network, and I consider both traditional search algorithms (depth-first search, A*) as well as innovative recent generalizations of A* from the operations research literature.

Dr. T: A Communications Infrastructure for Distributed Interactive Applications

(11 December 1997, HTML (some figures missing) and PostScript, 39 pages)
Dr. T is a simple communications infrastructure designed to support distributed interactive applications such as networked games, chat programs, and shared whiteboard systems. It hides from application programmers the details of networking software and presents a very simple abstraction of distributed process group input. On campus-sized WANs Dr. T supplies inputs to process group members frequently enough to keep pace with a 30 Hz screen refresh rate. This paper describes the design & implementation of Dr. T and illustrates the use of the system with a sample "game" application. All of the source code described in this paper is presented.

ATIS at Rush Hour: Adaptation and Departure Time Coordination in Iterated Commuting

(18 May 1997, HTML and PostScript, 54 pages)
Advanced Traveler Information Systems (ATIS) enable motorists to use fundamentally new strategies when selecting departure times in morning commuting. What are the effects of these new strategies on overall traffic system performance? Just as safety devices such as air bags and anti-lock brakes can have counter-intuitive effects when deployed on a large scale, it is conceivable that ATIS systems may degrade system-level traffic network performance. This paper compares the effects of departure time decisionmaking strategies that unaided motorists may employ with strategies that require ATIS-like technologies. Includes appendices containing annotated listings of all simulation code used in this set of experiments. See also "Driver Strategy and Traffic System Performance" below.

Further Computational Results on Fastest Paths in Stochastic Time-Dependent Networks

(18 May 1997, HTML and PostScript, 15 pages)
Dijkstra's algorithm and other dynamic-programming methods cannot be used to compute fastest paths in transportation networks where travel times are both stochastic and time-dependent. Michigan professor Michael Wellman developed an algorithm capable of computing fastest paths in such networks. This paper presents computational evidence suggesting that the time required by Wellman's algorithm increases sub-exponentially as a function of network size on a class of randomly-generated transportation networks.

sniffle project report

(14 September 1995, HTML and PostScript, 75 pages)
sniffle is a "Simple Networked Interface to the Full Functionality of Lab Equipment." It's a flexible, extensible, general system I developed during the summer of 1995 for Professor Michael Littman of Princeton's Mechanical and Aerospace Engineering Department. sniffle allows any Web client to control nearly the full functionality of an Analog Devices RTI-815 I/O board mounted in the Web server computer and a Tektronix 222 digital oscilloscope connected to the server via a serial port. See the sniffle home page. for a variety of documents related to the project, e.g. a "hype sheet" briefly describing the system. sniffle has been in continuous use since September 1995 on a Win3.1 platform and is being ported to Win95 in January 1998. A number of projects have been built on top of it, and the core of the system has been extended. A research group at the University of Colorado has added the sniffle documentation to its reading list.