The following three sections cover recent research (dating from 2000), research
in the period 1960 to 2000, and finally a listing of Coffman's collaborators over the past 50 years.
 
Recent and OnGoing Research

Stochastic Modeling of SelfAssembly at Molecular Scale
A research project begun in 2002 centers on the stochastic analysis of
selfassembly in the tilesystem model of DNAbased computing. Collaborators
are P. Momcilovic, Y. Baryshnikov, B. Yimwadsana, and Ned Seeman. Yimwadsana's
PhD thesis together with several groundbreaking 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.
 Streammerging 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 peertopeer filesharing systems.
 Seamless downloading of files: a RAMlike filesharing system. (includes the PhD thesis of
A. Constantinides)
 Mathematical modeling and analysis of additiveincrease, multiplicativedecrease congestion
control protocols. (includes the PhD thesis of Jing Feng  Y. Baryshnikov coadvisor)
 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, coadvisor).
Sensor Networks: Mathematical Models of Minimalist LocalRule Processes.
(includes the PhD thesis of K. J. Kwak  Y. Baryshnikov coadvisor)
 Localization
 SleepWake protocols
 Target counting
Combinatorial Scheduling Theory
Classical problems in preemptive and nonpreemptive parallelmachine scheduling with release dates,
tree precedence constraints, and unit execution times were
studied. Results for bicriteria (mean and maximum completion time) problems broke new ground.

 
 
Research Grants

 Advanced Research Projects Agency (predecessor of DARPA) 19611965, Design and
Analysis of the SDC/ARPA TimeSharing System, administered by the System Development
Corporation with a fully operational system completed in 1963 (see the Research Review
below)
 National Science Foundation 196769, Formal Languages, with J. Hopcroft.
 National Aeronatutics and Space Administration 19691970, Performance Evaluation
 National Science Foundation 197175, Mathematical Analysis of Operating Systems
(renewed 1973)
 National Science Foundation 19761980, Computer Resource Allocation, (renewed
1978)
 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 20012004, 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," 20012005, with D. Rubenstein, Jason Nieh,
P. Jelenkovic, and H. Schulzrinne.
 National Science Foundation, 20072010, Adaptive Sharing Mechanisms, with M. Harchol,
V. Misra, P. Jelenkovic, and D. Rubenstein.
 National Science Foundation, 20102013, 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 largescale systems development were in the
years 19621965 at the System Development Corporation (SDC), a spinoff of
the Rand Corporation, and are embodied in two bold claims:
He coinvented generalpurpose timesharing systems
(with a fair number of others), and he
coinvented computer networking (again, with a fair
number of others).
Support for the first claim begins
with the realization that the SDC/ARPA TimeSharing 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 timeshared
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. MerwynDaggett, 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 prizewinning article
(Firsts)
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 timeshared 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 coauthor
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 online, interactive data base
system, an IPLV programming system, and a DIAL command (ibid. p. 399) which
allowed networked users to communicate online, 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 generalpurpose timesharing, 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 Q32 computer). The system was designed as a node
of a computer network, a network that began with a connection between SDC's
Q32 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 highspeed 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.
Conf., 1961.)
The STSS hardware included a small frontend computer, a PDP1 (Fig. 1, Firsts ),
that is surely the predecessor of the ARPANET IMP (Interface Message
Processor). A little later, in 1965, another step in longhaul computer
communications was taken when a link was established between Lincoln
Labs' TX2 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 SDCARPA
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 generalpurpose 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 finitesource models, modeled the quantum/timeslice as a
tunable parameter, and presented results for continuoustime 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 timesharing 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 timesharing 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 finitesource 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 runningtime priority
queues. Kleinrock introduced processorsharing (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 coauthored in 1973.
PrenticeHall 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 coauthored a book
on computer storage problems.
Scheduling:
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 MuntzCoffman algorithms and the CoffmanGraham
algorithm are among the field's foundations. As an editor and coauthor,
Coffman collaborated with Bruno, Graham, Kohler, Sethi,
Steiglitz, and Ullman ('75) to write an advanced text on scheduling and binpacking
theory.
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 coauthored with
Even ('98), Magazine, Santos, Yannakakis, Nozari, Langston, Labetoulle, and Bruno.
The literature on the averagecase
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 averagecase 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 itemsize
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.
Movingserver problems: Coffman, with Calderbank and
Flatto, wrote several papers on movingserver 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 kserver 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 equalsize
files and an underlying infiniteserver queueing model. With
Leighton('89), Coffman designed a bestfit 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 infiniteserver 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
infiniteserver probability model was changed to a singleserver model. Other coauthors
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
category.
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)); processorring stability (with Gilbert, Greenberg, Leighton, Robert,
and Stolyar('95) and with Kahale and Leighton('98));
synthesis of queueing disciplines to meet prespecified waiting time constraints
(with Mitrani('80));
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.
of INFORMS.

 


Colleagues

Almost all of those listed below are coauthors of papers and books.
The remaining few are coeditors and coprincipal investigators.
 Ashok Agrawala, L. Andrew, David Applegate, E. Asgeirsson, Oleg Aven, Urtzi
Ayesta
 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, PierreJacques 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,
Greg Frederickson,
 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 JeanMarie, Predrag Jelenkovic, David (S.) Johnson, Don (B.) Johnson,
Neil Jones
 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,
Tolya Puhalskii
 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 SimchiLevi,
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

 
TOP /
CONTACT /
HOME
