The following three sections cover recent research (dating from
in the period 1960 to 2000, and finally a listing
of Coffman's collaborators over the past 50 years.
Stochastic Modeling of Self-Assembly at Molecular Scale
A research project begun in 2002 centers on the stochastic analysis of
self-assembly in the tile-system model of DNA-based computing. Collaborators
are P. Momcilovic, Y. Baryshnikov, B. Yimwadsana, and Ned Seeman. Yimwadsana's
PhD thesis together with several ground-breaking papers has resulted from this project.
Studies of Information Access and Traffic Processes on the Internet
Several isolated projects were completed, with overlay networks providing connective
infrastructure in many cases.
- Stream-merging theory: precise results for a baseline mathematical model of video
downloading via stream merging.
- Hotspot prediction and response: empirical/statistical studies of traffic patterns
suggestive of incipient hotspots.
- Distributed file searching in peer-to-peer file-sharing systems.
- Seamless downloading of files: a RAM-like file-sharing system. (includes the PhD thesis of
- Mathematical modeling and analysis of additive-increase, multiplicative-decrease congestion
control protocols. (includes the PhD thesis of Jing Feng - Y. Baryshnikov co-advisor)
- Optical burst switching: Performance analysis of baseline mathematical models.
- Opportunistic spectrum use in proposed cognitive/software radio systems: theoretical analysis
of a dynamic resource allocation model with piece fragmentation allowed (includes the PhD
thesis of S. Tarumi - Gil Zussman, co-advisor).
Sensor Networks: Mathematical Models of Minimalist Local-Rule Processes.
(includes the PhD thesis of K. J. Kwak - Y. Baryshnikov co-advisor)
- Sleep-Wake protocols
- Target counting
Combinatorial Scheduling Theory
Classical problems in preemptive and non-preemptive parallel-machine scheduling with release dates,
tree precedence constraints, and unit execution times were
studied. Results for bi-criteria (mean and maximum completion time) problems broke new ground.
- Advanced Research Projects Agency (predecessor of DARPA) 1961-1965, Design and
Analysis of the SDC/ARPA Time-Sharing System, administered by the System Development
Corporation with a fully operational system completed in 1963 (see the Research Review
- National Science Foundation 1967-69, Formal Languages, with J. Hopcroft.
- National Aeronatutics and Space Administration 1969-1970, Performance Evaluation
- National Science Foundation 1971-75, Mathematical Analysis of Operating Systems
- National Science Foundation 1976-1980, Computer Resource Allocation, (renewed
- Office of Naval Research 1981, Combinatorial Scheduling and Packing Theory
(with B. S. Baker)
- Grants for travel to England (IBM, 1969) to Hungarian Academy of Sciences (NSF, 1976), and to
IEEE Conference, New Delhi (NSF, 1984)
- IBM Faculty Partnership Grant, 2000.
- National Science Foundation 2001-2004, Caching for Efficient Content Delivery on the WWW,
with P. Jelenkovic.
- Grant from the Erdos Foundation for 2 months of research in Hungary, 2000.
- NSF grant "The Columbia Hotspot Rescue Service," 2001-2005, with D. Rubenstein, Jason Nieh,
P. Jelenkovic, and H. Schulzrinne.
- National Science Foundation, 2007-2010, Adaptive Sharing Mechanisms, with M. Harchol,
V. Misra, P. Jelenkovic, and D. Rubenstein.
- National Science Foundation, 2010-2013, Efficient, Popularity Independent Video on Demand,
with V. Misra and D. Rubenstein.
Research Review up to 2000
Software Research and Development:
Coffman's contributions to large-scale systems development were in the
years 1962-1965 at the System Development Corporation (SDC), a spin-off of
the Rand Corporation, and are embodied in two bold claims:
He co-invented general-purpose time-sharing systems
(with a fair number of others), and he
co-invented computer networking (again, with a fair
number of others).
Support for the first claim begins
with the realization that the SDC/ARPA Time-Sharing System
(STSS hereinafter for simplicity) and the CTSS time sharing system
at MIT, the first of their kind, became fully operational at about the
same time in 1963. The term "general purpose" is meant to exclude, e.g.,
the system described in "A Time Sharing Debugging System for a Small Computer," by J. McCarthy, S. Boilen, E. Fredkin, and J.C.R. Licklider (Spring Joint
Comp. Conf., 1963), although this groundbreaking work did have its influence
on STSS as did the early thinking behind CTSS. The vision of time-shared
computers seems to date back to the late 50's; see, e.g., the references in
"An Experimental Time Sharing System," by F. Corbato, M. Merwyn-Daggett, and
R. Daley (Spring Joint Comp. Conf., 1962), and "Time Shared Computer Systems,"
by J. McCarthy (in Management and the Computer of the Future, edited by M.
Greenberger, MIT Press, 1962). Understandably, in that era, the gap between
vision and a working, productive system was a very large one.
Coffman was among 5 system programmers led by Jules Schwartz who built
STSS; Coffman was responsible for the design and implementation of the
scheduler/dispatcher component of the system. Coffman joined colleagues
Jules Schwartz and Clark Weissman in writing a prize-winning article
presented almost a year after
the events it chronicled. It described STSS,
experience with its use, its planned development, and its own vision for
the future: the promise of networks of time-shared computers that would
become a norm of the computing field. (Full citations for this article
and the others mentioned below that carry Coffman as a co-author
are easily found in the publications section.)
STSS boasted an innovative interactive system for program composition and
debugging, a tool based on a derivative of ALGOL (via JOVIAL) with various
service routines available including a compiler and a fancy desk calculator.
It also supplied its users with the first on-line, interactive data base
system, an IPL-V programming system, and a DIAL command (ibid. p. 399) which
allowed networked users to communicate on-line, a forerunner to today's email
and web communication services. It seems fair to say that, in closing the
gap between the vision and reality of general-purpose time-sharing, both
STSS and CTSS became watershed events in the history of computing, validating
as they did a paradigm shift in computing arguably as fundamental as any other
to this day.
To support the second (computer networking) claim, we note that
STSS was a landmark event in
a sense orthogonal to its historical time sharing role. Specifically,
computer networking seems to have had its debut at SDC in the same system
(organized around IBM's Q-32 computer). The system was designed as a node
of a computer network, a network that began with a connection between SDC's
Q-32 and a CDC computer at SRI some 400 miles distant, with plans in process
for connections to several more remote computers. Here, the term "networking"
also embraces the computer users, not just the computers. (In an earlier
project, B. Baldwin and N. Snow had described a high-speed data link between
Bell Labs' Holmdel and Murray Hill computers for the simple transfer of data:
"Remote Operation of a Computer by High Speed Data Link," Fall Joint Comp.
The STSS hardware included a small front-end computer, a PDP-1 (Fig. 1, Firsts ),
that is surely the predecessor of the ARPANET IMP (Interface Message
Processor). A little later, in 1965, another step in long-haul computer
communications was taken when a link was established between Lincoln
Labs' TX-2 computer and the STSS node at SDC. (See "Toward a Cooperative
Network of Time Shared Computers" by T. Marill and L. Roberts, Fall Joint
Comp. Conf., 1966). The second claim can rest on the fact that this was
touted as the first wide area computer network in "A Brief History of the
Internet" by B. Leiner, V. Cerf, D. Clark, R. Kahn, L. Kleinrock, D. Lynch,
J. Postel, L. Roberts, and S. Wolff (Comm. ACM Feb. 1997). The SDC-ARPA
computer networking experiments seem to predate this work, however.
Either way, it is clear that the experimental networks incorporating STSS
had made their mark as precursors to ARPA's next major networking step,
the ARPANET, and from there, the Internet.
Early Performance Analysis
With the viability of general-purpose time sharing just established,
and with the appearance of several key publications/reports, it seems
natural to identify 1964 as a time when modern computer performance
modeling and analysis took off in earnest. L. Kleinrock presented a
first stochastic analysis of time sharing (Nav. Res. Logist. Quart.,
Mar. 1964), while I. Flores provided a similar analysis of multiple
bank memories (J. ACM, April 1964). In an independent project, more
realistic time sharing models were studied by a small group at SDC, which
exploited finite-source models, modeled the quantum/time-slice as a
tunable parameter, and presented results for continuous-time processes.
A report written by Coffman and B. Krishnamoorthi in
1964 eventually appeared in Coffman's Ph.D. thesis in 1966. This
work led to a subsequent study
by Krishnamoorthi and R. Wood that appeared in a later SDC report
and eventually came out in J. ACM, July 1966.
Performance monitoring of the new time-sharing systems began at SDC
in the early '60s (see the article by Schwartz, Coffman, and Weissman).
Coffman instrumented STSS and collected performance data to
demonstrate the effectiveness of the STSS design and to characterize
statistically users of time-sharing systems. The results
were presented and analyzed in a paper by Coffman and Wood.
A. Scherr at MIT also seems to have gotten underway in 1964; he collected
data on CTSS that he showed in his 1965 Ph.D. thesis could be closely
modeled by a remarkably simple finite-source model. (See also the
article by S. Lavenberg and M. Squillante "Performance Evaluation in
Industry: A Personal Perspective," (in Performance Evaluation: Origins
and Directions, Springer 2000).
Computer scheduling techniques: In the late '60s and early '70s,
Coffman combined first with Kleinrock ('67,'68) and then Muntz in a number
of papers analyzing computer running-time priority
queues. Kleinrock introduced processor-sharing (PS) as
a formal limit of the round robin model. The
first rigorous analysis of the PS process itself (i.e., of the M/M/1/PS queue)
appears to be that of
Coffman, Muntz, and Trotter ('70). The PS process
and its variants have subsequently become extremely widely used tools in the
study of computer and communication systems; in these systems,
they rival the FIFO queue in importance,
and continue to be studied in new settings and variants.
Auxiliary storage: Coffman's groundbreaking papers in the analysis of secondary
storage were among his earliest contributions to the field, e.g., drum scheduling
('69). His interests in this field continued well into the 80's; see e.g.
his analysis of scanning disks('82) and queueing models('86) with Hofri.
Books on performance evaluation: Together with notable work on scheduling (see below) and
system deadlocks, (e.g., with Shoshani('70)),
much of Coffman's early PE work combined with that of Denning in the
book OPERATING SYSTEM THEORY, which they co-authored in 1973.
Prentice-Hall continued to sell this book for 20 years, unusual
in a field that has been outstanding for its frequent paradigm shifts. This was
the first book devoted largely to performance modeling and analysis of
computer operating systems. Much later, with
Aven and Kogan ('87 - Russian colleagues at the time), he co-authored a book
on computer storage problems.
Coffman's early studies of service systems and scheduling policies extended
to combinatorial scheduling, where he published what were to become
landmark papers with Muntz ('69, '70)
and Graham ('72): The Muntz-Coffman algorithms and the Coffman-Graham
algorithm are among the field's foundations. As an editor and co-author,
Coffman collaborated with Bruno, Graham, Kohler, Sethi,
Steiglitz, and Ullman ('75) to write an advanced text on scheduling and bin-packing
Highlights of further work in scheduling include his design of the MULTIFIT algorithm with
Garey and Johnson ('78), which was a SIAM best paper selection
for '78, and, with Garey('93), a solution to a problem of preemptive scheduling
that had remained open for 20 years. Other work in this area was co-authored with
Even ('98), Magazine, Santos, Yannakakis, Nozari, Langston, Labetoulle, and Bruno.
The literature on the average-case
analysis of scheduling algorithms was launched by Coffman's seminal work with
Frederickson and Lueker('84). Further analysis of these problems was done with
Flatto, Whitt, and Gilbert.
Bin packing: Motivated by computer storage applications, Coffman moved into
the design and analysis of bin packing approximation algorithms, an area in which he
is still active. His seminal contributions include the extension of
bin packing to 2 dimensions:
the strip packing problem. The first two papers in what is now a substantial literature
on the subject are by Coffman, Baker, and Rivest ('80)
and by Coffman, Garey, Johnson, and Tarjan ('80).
In the late '70s, he also pioneered the average-case analysis of bin packing
with So, Hofri, and Yao('80), a field that is now well developed; see the text by Coffman and
Lueker ('91). The extension of probabilistic analysis to discrete item-size
distributions was inaugurated by Coffman, Courcoubetis, Garey, Johnson, McGeoch,
Shor, Weber, and Yannakakis (1991). Coffman's most recent paper in
this area was with Courcoubetis, Garey, Johnson, Shor, Weber, and Yannakakis(2000) and was
chosen as one of SIAM's best papers of 2000.
Moving-server problems: Coffman, with Calderbank and
Flatto, wrote several papers on moving-server problems that originated
in the study of disks with multiple heads, a continuation of Coffman's earlier
interests in auxiliary storage systems.
The subsequent, large
literature on the competitive (combinatorial) analysis of k-server problems derived in part
from this work on stochastic models.
Dynamic storage allocation: In the '80's,
Coffman invested a major effort in performance analysis of
dynamic storage allocation (DSA) algorithms, the primary
reference models being those of Knuth (Vol. I). With Kadota and
Shepp('85) explicit results were obtained for the case of equal-size
files and an underlying infinite-server queueing model. With
Leighton('89), Coffman designed a best-fit type algorithm (dubbed ``distributed fit"
by Knuth in Vol. I) which remains the best, provably efficient
algorithm for DSA. Again, the underlying stochastic
process of arrivals/departures was the infinite-server queue.
The proof of the algorithm's performance exploited stochastic planar
matching theory, another area in which Coffman had major contributions, particularly
with Shor. In another work with Flatto and Leighton ('90), The
infinite-server probability model was changed to a single-server model. Other co-authors
in the analysis of stochastic models include C. Knessl and I. Mitrani.
Combinatorial models of DSA that were studied by Coffman included the very
difficult two dimensional case with Gilbert('84), the study of
compaction and insertion algorithms with Baker ('84),
and algorithms for resolving conflicts with Baker and Willard ('85).
Stochastic scheduling: Among the seminal papers are the parallel machine
studies with Agrawala, Garey, and Tripathi('84) and with Flatto, Garey, and Weber('87).
Several papers on fault tolerant systems (including checkpointing) also fall in this
Queueing reprise: Coffman's applications of queueing to performance
evaluation have been many and
varied. They include notably conveyor queues
(with Gelenbe and Gilbert('86)); processor-ring stability (with Gilbert, Greenberg, Leighton, Robert,
and Stolyar('95) and with Kahale and Leighton('98));
synthesis of queueing disciplines to meet pre-specified waiting time constraints
reservation systems (with Jelenkovic and Poonen('99) and Baryshnikov and Jelenkovic('02));
and heavy traffic analysis of polling systems
(with Puhalskii and Reiman ('98));
this work won the 2001 best paper prize of the Applied Prob. Soc.
Almost all of those listed below are co-authors of papers and books.
The remaining few are co-editors and co-principal investigators.
- Ashok Agrawala, L. Andrew, David Applegate, E. Asgeirsson, Oleg Aven, Urtzi
- Francois Baccelli, Brenda Baker, Yuliy Baryshnikov, Arthur Berger, Jacek Blazewicz, Lunya
Boguslavsky, Sem Borst, Julian Bramel, Sid Browne, John Bruno, Gerry Burnett
- Rob Calderbank, Philippe Chretienne,, Fan Chung, Roger Cody, Andreas Constantinides, Costas
Courcoubetis, Pierre-Jacques Courtois, Janos Csirik
- Peter Denning, Derek Dereniowski, Pete Downey
- Klaus Ecker, Michael Elphick, J. Etra, Jim Eve, Shimon Even
- Guy Fayolle, Anya Feldmann, G. Finke, Philippe Flajolet, Jing Feng, Leo Flatto,
- Gabor Galambos, Mike Garey, Don Gaver, Z. Ge, Erol Gelenbe, Ed Gilbert, Ron Graham, Albert Greenberg
- Shlomo Halfin, Steve Hanly, Mor Harchol, Micha Hofri, John Hopcroft, Bill Hosken
- Boris Igelnik
- Philippe Jacquet, Alain Jean-Marie, Predrag Jelenkovic, David (S.) Johnson, Don (B.) Johnson,
- Ted Kadota, Nabil Kahale, Len Kleinrock, Larry Klimko, Walter Kohler, Charles Knessl,
Yasha Kogan, Sasha Kreinen, Krish Krishnamoorthi, Wieslaw Kubiak, K.J. Kwak
- Jacques Labetoulle, Jeff Lagarias, Mike Langston, Tom Leighton, Jan Karel Lenstra,
Joe Leung, Zhen Liu, George Lueker
- Mike Magazine, Colin Mallows, Dmytro Matsypura, Peggy McGee, Lyle McGeoch, Silvano Martello, Arch McKellar,
Mo Michel, Vishal Misra, Isi Mitrani, Petar Momcilovic, Bill Moran, Dick Muntz
- Philippe Nain, Jason Nieh, Steven Nowick, A. Nozari
- Guillaume Pierre, P. Piret, Brigitte Plateau, S. Phillips, Henry Pollak, Bjorn Poonen,
- Brian Randell, Marty Reiman, Tom Richardson, Alexander Rinnooy Kan, Ron Rivest,
Philippe Robert, L. Ronyai, Dan Rubenstein, Barbara Ryan, Tom Ryan
- C. Santos, Martin Schmookler, Jules Schwartz, Ned Seeman, Ravi Sethi, Jay Sethuraman,
Bruce Shepherd, Larry Shepp, Peter Shor, Arie Shoshani, Florian Simatos, David Simchi-Levi,
Bert Simon, Don Slutz, Kimming So, Angelos Stavrou, Ken Stieglitz, Joel Spencer, Sasha Stolyar
- J. Talim, Bob Tarjan, Shuzo Tarumi, Vad Timkovsky, D. Ting, Don Towsley, Satish Tripathi,
Hale Trotter, C.J.M. Trumbull
- Jeff Ullman
- Lee Varian, Daniele Vigo
- Richard Weber, Gideon Weiss, Clark Weissman, Jolyon White, Phil Whiting, Ward Whitt,
Dan Willard, Pete Winkler, Gerhard Woeginger, Roger Wood, Paul Wright
- Mihalis Yannakakis, Andy Yao, Teddy Yimwadsana
- A. Zsban, Gil Zussman