As of June 2022 this page is not completely up to date. For additional material, see my ACM Digital Library page.

Patents

Dynamically Resizing a Virtual Machine Container

US Patent 8,566,835.

Application Performance Analysis for a Multiple Processor Queuing Station

US Patent 8,798,960
See also MASCOTS 2008 and SPAA 2008 papers.

Recovery Segments

US Patent 8,909,987.

Scheduling Computer Processing Jobs that have Stages and Precedence Constraints among the Stages

US Patent 8,281,313 granted 2 October 2012
See also SPAA 2005 and SIGMETRICS 2005 papers.

Constraint Satisfaction For Solutions To An Auction Winner-determination Problem

US Patent 8,086,520 granted 27 December 2011
See also AAIM 2009 and SigEcom Exchanges 2006 papers.

Method of Dispatching Tasks in Multi-Processor Computing Environment with Dispatching Rules and Monitoring of System Status

US Patent 8,015,564 granted 6 September 2011
See also SPAA 2005 and SIGMETRICS 2005 papers.

Method Of Allocating Computing Resources

US Patent 7,844,967 granted 30 November 2010
See also SelfManage 2003 paper / Tech Report HPL-2003-115.

Computing A Set Of K-best Solutions To An Auction Winner-determination Problem

US Patent 7,801,769 granted 21 September 2010
See also AAIM 2009 and SigEcom Exchanges 2006 papers.

Method Of Predicting Response Time For Storage Request

US Patent 7,721,061 granted 18 May 2010

Method Of Dividing Past Computing Instances Into Predictable And Unpredictable Sets And Method Of Predicting Computing Value

US Patent 7,720,771 granted 18 May 2010

Determining Performance Of An Application

US Patent 7,720,955 granted 18 May 2010

Automated Diagnosis and Forecasting of Service Level Objective States

US Patent 7,693,982 granted 6 April 2010
See also OSDI 2004 and SOSP 2005 papers.

Determining A Recurrent Problem Of A Computer Resource Using Signatures

US Patent 7,502,971 granted 10 March 2009
See also OSDI 2004 and SOSP 2005 papers.

Publications

Zero Tolerance for Bias (Drill Bits #12)

by Terence Kelly
ACM Queue magazine, Vol. 22 No. 2, March/April 2024
Applications with profound social and economic consequences require uncompromising fairness.
[ACM Digital Library] [HTML] [PDF]

Programmer Job Interviews: The Hidden Agenda (Drill Bits #11)

by Terence Kelly
ACM Queue magazine, Vol. 21 No. 6, November/December 2023
Learn how top tech firms covertly measure a prized skill that sets the best coders above the rest.
[ACM Digital Library] [HTML] [PDF]

Snapshot: Fast, Userspace Crash Consistency for CXL and PM Using msync

by Suyash Mahar, Mingyao Shen, Terence Kelly, and Steven Swanson
IEEE International Conference on Computer Design, 6-8 November 2023, Washington, DC
Extended dance version: [arXiv PDF]

Protecting Secrets from Computers (Drill Bits #10)

by Terence Kelly
ACM Queue magazine, Vol. 21 No. 4, July/August 2023
Entrusting secrets to hardware and software designed and built by legions of total strangers is for credulous fools. Fortunately, there are safe ways to use computers for communicating and storing data without trusting them.
[ACM Digital Library] [HTML] [PDF]

Catch-23: The New C Standard Sets the World on Fire (Drill Bits #9)

by Terence Kelly and Yekai Pan
ACM Queue magazine, Vol. 21 No. 1, January/February 2023
Tour the horror show that is the latest C standard.
[ACM Digital Library] [HTML] [PDF]

Literate Executables (Drill Bits #8)

by Terence Kelly
ACM Queue magazine, Vol. 20 No. 5, September/October 2022
Literate executables walk the walk of Open Source: They emit their own source code on demand.
[ACM Digital Library] [HTML] [PDF]

Persistent Scripting

by Zi Fan Tan, Jianan Li, Terence Kelly, and Haris Volos
Non-Volatile Memory Workshop (NVMW), May 2022
Motivates and describes persistent gawk. See Drill Bits #7 (Persistent Memory Allocation) for the allocator that makes it possible.
[paper PDF] [slides PDF] [local paper PDF] [local slides PDF]

Persistent Memory Allocation: Leverage to Move a World of Software (Drill Bits #7)

by Terence Kelly
ACM Queue magazine, Vol. 20 No. 2, March/April 2022
Presents the persistent memory allocator, pma, underlying the first implementation of persistent memory for scripting: persistent gawk. See also the NVMW paper on persistent scripting.
[ACM Digital Library] [HTML] [PDF]

Steampunk Machine Learning: Victorian Contrivances for Modern Data Science (Drill Bits #6)

by Terence Kelly
ACM Queue magazine, Vol. 19 No. 6, November/December 2021
A simple, intuitive, robust way to deal with noise and nonsense when fitting data to models was invented centuries before its time. My example code in R makes it a snap.
[ACM Digital Library] [HTML] [PDF]

Terminate with Extreme Prejudice

by Terence Kelly
IEEE Computer magazine, Vol. 54 No. 8, August 2021
Botched termination tests cause a tragicomic downward spiral of senseless inefficiency. See also Drill Bits #1 (Efficient Graph Search).
[IEEE Xplore] [HTML] [PDF]

Crashproofing the Original NoSQL Key-Value Store (Drill Bits #5)

by Terence Kelly
ACM Queue magazine, Vol. 19 No. 4, July/August 2021
GNU dbm, the modern incarnation of Ken Thompson's original Unix dbm, now can tolerate power failures and other crashes. See how simple and easy crashproofing can be if we let a modern file system do nearly all of the work.
[ACM Digital Library] [HTML] [PDF]

Schrodinger's Code: Undefined Behavior in Theory and Practice (Drill Bits #4)

by Terence Kelly, Weiwei Gu, and Vladimir Maksimovski
ACM Queue magazine, Vol. 19 No. 2, March/April 2021
Learn to banish the perils of undefined behavior that threaten your C/C++ code, and enjoy the adorable animated cat.
[ACM Digital Library] [HTML] [PDF]

Offline Algorithms in Low-Frequency Trading: Clearing Combinatorial Auctions (Drill Bits #3)

by Terence Kelly
ACM Queue magazine, Vol. 18 No. 6, November/December 2020
This installment shows how to allocate complementary resources via combinatorial auctions, providing a working solver in C.
[ACM Digital Library] [HTML] [PDF]

A Penny in Every Fuse Box

by Terence Kelly
ACM Inroads magazine, Vol. 11 No. 4, December 2020
For Computer Science instructors. Explains the need to teach Efficient Graph Search (See Drill Bits #1).
[ACM Digital Library] [Inroads site, possibly paywall'd] [PDF]

Compressed Sparse Row Format for Representing Graphs (Programming Workbench #2)

by Terence Kelly
USENIX ;login: magazine, Vol. 45 No. 4, Winter 2020
Episode 2 of "Programming Workbench," about a compact and efficient alternative to adjacency lists & adjacency matrices. Provides example code in C.
[USENIX master version] [PDF]

Hand-Over-Hand Locking for Highly Concurrent Collections (Programming Workbench #1)

by Terence Kelly
USENIX ;login: magazine, Vol. 45 No. 3, Fall 2020
The first installment of my "Programming Workbench" column, devoted to a simple yet widely overlooked concurrency pattern. Provides example code in C.
[USENIX master version] [PDF]

Decentralized Computing (Drill Bits #2)

by Terence Kelly
ACM Queue magazine, Vol. 18 No. 5, September/October 2020
Sometimes we can compute correct outputs without bringing all relevant inputs together in one place. Example code in Python and C.
[ACM Digital Library] [HTML] [PDF]

Is Persistent Memory Persistent?

by Terence Kelly
Communications of the ACM, Vol. 63 No. 9, September 2020
Republication of the Queue article of the same name.
[ACM Digital Library] [HTML]

Efficient Graph Search (Drill Bits #1)

by Terence Kelly
ACM Queue magazine, Vol. 18 No. 4, July/August 2020
The classic breadth-first and depth-first search algorithms in every textbook are sometimes grotesquely and gratuitously inefficient. This first installment of my "Drill Bits" column fixes the performance bug and provides an implementation in C. See also "A Penny in Every Fuse Box" and "Terminate with Extreme Prejudice"
[ACM Digital Library] [HTML] [PDF]

Is Persistent Memory Persistent?

by Terence Kelly
ACM Queue magazine, Vol. 18 No. 2, March/April 2020
A simple and inexpensive test of failure-atomic update mechanisms. Later republished in CACM.
[ACM Digital Library] [HTML] [PDF]

Good Old-Fashioned Persistent Memory

by Terence Kelly
USENIX ;login: magazine, Vol. 44, No. 4, Winter 2019
Presents new "famus_snap" library.
Includes pointers to machine-readable source code for all example programs.
[USENIX master version] [USENIX PDF]

Persistent Memory Programming on Conventional Hardware

by Terence Kelly
ACM Queue magazine, Vol. 17, No. 4, July/August 2019
Includes pointers to machine-readable source code for all example programs.
[ACM Digital Library] [ACM Queue web site]

Dali: A Periodically Persistent Hash Map

by Faisal Nawab, Joe Izraelevitz, Terence Kelly, Charles B. Morrey, Dhruva Chakrabarti, and Michael L. Scott
DISC 2017, 16-20 October, Vienna, Austria
[PDF from DISC web site] [local copy]

Failure-Atomic Persistent Memory Updates via JUSTDO Logging

by Joseph Izraelevitz, Terence Kelly, and Aasheesh Kolli
ASPLOS 2016, 4-6 April 2016, Atlanta, Georgia
[HPL Tech Report version, same as published version]

Failure-Atomic Updates of Application Data in a Linux File System

by Rajat Verma, Anton Ajay Mendez, Stan Park, Sandya Mannarswamy, Terence Kelly, and Brad Morrey
USENIX Conference on File and Storage Technologies (FAST), February 2015, Santa Clara, California
[USENIX PDF] Also available as HP Labs tech report HPL-2014-53. See also ``SQLean'' tech report HPL-2015-103 for application.

SQLean: Database Acceleration via Atomic File Update [Tech Report]

by Rajat Verma, Anton Ajay Mendez, Stan Park, Sandya Mannarswamy, Terence Kelly, and Brad Morrey
Hewlett Packard Labs tech report [HPL-2015-103] [local PDF]

Procrastination Beats Prevention: Timely Sufficient Persistence for Efficient Crash Resilience

by Faisal Nawab, Dhruva Chakrabarti, Terence Kelly, and Charles Morrey
International Conference on Extending Database Technology (EDBT), 23-27 March 2015, Brussels, Belgium
[Conference PDF]

Zero-Overhead NVM Crash Resilience

by Faisal Nawab, Dhruva Chakrabarti, Terence Kelly, and Charles Morrey
Non-Volatile Memories Workshop (NVMW), 1-3 March 2015, San Diego, California.
[Conference PDF] [Local PDF]

Generic Crash-Resilient Storage for Indigo and Beyond [Tech Report]

by Aviv Blattner, Ram Dagan, and Terence Kelly
HP Labs Tech Report HPL-2013-75, released 6 November 2013.

Failure-Atomic msync(): A Simple and Efficient Mechanism for Preserving the Integrity of Durable Data

by Stan Park, Terence Kelly, and Kai Shen
EuroSys 2013, 15-17 April 2013, Prague, Czech Republic
[EuroSys copy] [local copy]

Practical Lock/Unlock Pairing for Concurrent Programs

by Hyoun Kyu Cho, Yin Wang, Hongwei Liao, Terence Kelly, Stephane Lafortune, and Scott Mahlke
International Symposium on Code Generation and Optimization (CGO) 2013, 23-27 February 2013, Shenzhen, China

Sidestep: Co-Designed Shiftable Memory & Software [tech report]

by Terence Kelly, Harumi Kuno, Matthew Pickett, Hans Boehm, Al Davis, Wojciech Golab, Goetz Graefe, Stavros Harizopoulos, Pramod Joisha, Alan Karp, Naveen Muralimanohar, Fred Perner, Gilberto Medeiros-Ribeiro, Gadiel Seroussi, Alkis Simitsis, Robert Tarjan, and Stan Williams
HP Labs Tech Report HPL-2012-235 [local PDF], released 21 November 2012

On Atomicity Enforcement in Concurrent Software Via Discrete Event Systems Theory

by Yin Wang, Peng Liu, Terence Kelly, Stephane Lafortune, Spyros Reveliotis, and Charles Zhang
IEEE Conference on Decision and Control (CDC), 10-13 December 2012, Maui, Hawaii

Composable Reliability for Asynchronous Systems

by Sunghwan Yoo, Charles Killian, Terence Kelly, Hyoun Kyu Cho, and Steven Plite
USENIX Annual Technical Conference, 13-15 June 2012, Boston, MA, USA
[USENIX ATC 2012 version] [local PDF]
Open Source release of "Ken" implementation
See also HP Labs Tech Report HPL-2010-155, below.

Concurrency bugs in multithreaded software: modeling and analysis using Petri nets

by Hongwei Liao, Yin Wang, Hyoun Kyu Cho, Jason Stanley, Terence Kelly, Stephane Lafortune, Scott Mahlke, and Spyros Reveliotis
Discrete Event Dynamical Systems, published online 13 May 2012, DOI: 10.1007/s10626-012-0139-x
[Springer Online First version]
Printed journal version forthcoming.

Output-Valid Rollback-Recovery

by Terence Kelly, Alan H. Karp, Marc Stiegler, Tyler Close, and Hyoun Kyu Cho
HP Labs Tech Report HPL-2010-155, released 21 October 2010 (written earlier)
See also USENIX ATC 2012 paper, above, and HPL Tech Report HPL-2014-14 ("COVR") from March 2014.

Supervisory Control of Software Execution for Failure Avoidance: Experience from the Gadara Project

by Yin Wang, Hyoun Kyu Cho, Hongwei Liao, Ahmed Nazeem, Terence P. Kelly, Stephane Lafortune, Scott Mahlke, and Spyros A. Reveliotis
WODES (Workshop on Discrete Event Systems), 30 August - 1 September 2010, Berlin, Germany.
Also available as HP Labs tech report HPL-2010-194: [HP Labs version]

Gadara Nets: Modeling and Analyzing Lock Allocation for Deadlock Avoidance in Multithreaded Software

by Yin Wang, Hongwei Liao, Spyros Reveliotis, Terence Kelly, Scott Mahlke, and Stephane Lafortune
IEEE Conference on Decision and Control (CDC), 15-18 December 2009, Shanghai, China [IEEE Xplore #1] [IEEE Xplore #2]
Also available at HP Labs tech report HPL-2010-193: [HP Labs version]

Eliminating Concurrency Bugs with Control Engineering

by Terence Kelly, Yin Wang, Stephane Lafortune, and Scott Mahlke
IEEE Computer magazine, vol. 42, no. 12, December 2009 [IEEE Xplore #1] [IEEE Xplore #2]
See also papers in OSDI 2008 and POPL 2009, below.

Maximally Permissive Deadlock Avoidance for Multithreaded Computer Programs [extended abstract]

by Yin Wang, Hongwei Liao, Ahmed Nazeem, Spyros Reveliotis, Terence Kelly, Scott Mahlke, and Stephane Lafortune
IEEE Conference on Automation Science and Engineering (CASE), 22-25 August 2009, Bangalore, India [IEEE Xplore #1] [IEEE Xplore #2]

A Formal Foundation for Failure Avoidance and Diagnosis [tech report]

by Terence Kelly, Yin Wang, Stephane Lafortune, and Matt Welsh
HP Labs Tech Report HPL-2009-203, released 21 August 2009 (written earlier)

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
Published as Springer LNCS volume 5564.
Also available as HP Labs Tech Report HPL-2009-163 [Local PDF]
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]
Also available as HP Labs Tech Report HPL-2009-202
Nominated by ACM SIGPLAN for CACM Research Highlights Article, June 2009. Roughly 2% of all accepted papers at all SIGPLAN conferences receive this nomination annually.

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]
Also available as HP Labs Tech Report HPL-2009-200
Featured in IEEE Computer magazine News Briefs, August 2009.

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. [IEEE Xplore #1] [IEEE Xplore #2 (broken link; invalid DOI)]
Also available as HP Labs Tech Report HPL-2009-201

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
Featured in Y.C. Tay's book Analytical Performance Modeling for Computer Systems

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: [local PDF] [local bz2 compressed PostScript] [U. Mich. Library archive (Deep Blue)]

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. An unpublished paper, "ATIS at Rush Hour", addresses the same issues using a different simulation model.

Bald Like Me

Appears in 100 Successful College Application Essays, Second Edition, New American Library, 2002. ISBN 0-451-20713-0. Submitted to Princeton University. Apologies to John Howard Griffin.

Early 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.