Terence Kelly's Patents and Publications

Patents

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.
[several other patent applications pending]

Publications

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

$Id: index.html,v 1.96 2013/11/08 10:47:35 tpkelly Exp $