1. Lists of talks were not updated regularly over the years, and as a
result, those below are undoubtedly missing a few items.
2. The last section,
which is meant to be the most substantive one,
mentions Coffman's accomplishments/affiliations that are associated with significant
historical/pioneering events in computer science and engineering.
Distinguished Lecturer Series
These include the series in Computer Science and/or Electrical Engineering Departments at the
Universities of Maryland,
Virginia, Tennessee, Clemson, Columbia, The
North Carolina State University, University of Newcastle-upon-Tyne, University of Melbourne,
Institute of Control Science (Moscow), University of Poznan (Poland),
University of Paris VI, University of Osaka.
- Best paper prize/award, Spring Joint Computer Conference, 1964
- SIAM best paper nomination in computer science, 1978.
- SIAM best paper nomination in computer science, 1983.
- SIAM best paper selection for the year 2000.
- Applied Probability Society best publication prize, 2002.
- ACM Sigmetrics Conference, 1984
- International Seminar on Teletraffic Analysis and Computer Performance Evaluation, 1986
- Dutch symposium honoring J.W. Cohen, 1988
- INRIA(French) school on scheduling theory, 1992
- International Computer Performance and Dependability Symposium, 1998
- ACM Sigmetrics Conference, 2002.
- Sixth Workshop on Models and Algorithms for Planning and Scheduling Problems, 2003.
- 9th HERCMA Conference, Athens University of Economics and Business, 2008.
- First Sigmetrics Workshop on Hot Topics in Measurement and Modeling of Computer Systems (HotMetrics 2008).
- First and Tenth Sigmetrics Workshops on Mathematical Modeling and Analysis of Computer Systems (MAMA 1998,2008).
- 7th Symposium on Matrix Analytic Methods, MAM7, 2011.
Election to Fellow, IEEE, 1984
Distinguished Member of Technical Staff, AT&T Bell Laboratories award, 1984
ACM Outstanding Contribution Award, 1987
Achievement Medal of the Technical University of Poznan, Poland, 1991
Election to Fellow, ACM, 1994
Recipient of ACM Sigmetrics Achievement Award, 2002
IBM Faculty Parnership Awards 2002, 2004
ACM Distinguished Service Award, 2004
Lardner Prize, Canadian Operational Research Society, 2011
Milestones in Computer Science, Electrical Engineering, and Operations Research
- Coffman was in the set of 100 ACM members chosen to inaugurate the Fellow grade of ACM.
- He also inaugurated the SIGMETRICS achievement award, as its first winner.
- With Peter Denning, Coffman co-founded the Symposium on Operating System Principles.
- Coffman was a co-founder of ACM's SIGMETRICS.
- He also co-founded the IFIP Working Group 7.3 on Computer Performance Analysis.
- Development of Operating Systems and Computer Networks
- Time Sharing: While researchers at MIT were completing the CTSS time-sharing system,
Coffman participated in the team of 5 researchers that built the initial version of the
SDC/ARPA time-sharing system. The two systems were fully operational at roughly the same
time in 1963. The RESEARCH section has more detail, e.g.,
the DIAL command in the SDC/ARPA system was the forerunner of modern
- Networking: Coffman, via the SDC/ARPA system, contributed to the origins of modern computer networking,
in that the SDC/ARPA system was but a part of the first experimental system
offering on-line user access to any computer within
a network of (geographically remote) time-shared computers.
- Basic Research
- Performance Evaluation:
Coffman was responsible for pioneering research in
the '60s on the methodology of computer performance
evaluation, e.g., the first rigorous analysis of the M/M/1/PS (processor-sharing)
queue was conducted with R. Muntz and H. Trotter. In 1973, the work in this field was collected
in the first of many books on Computer Performance Evaluation. It was entitled ``Operating System
Theory" and was co-authored by P. Denning.
- Scheduling Theory: Coffman shared in the origins of modern combinatorial scheduling theory in
the late '60s: The Coffman-Graham and Muntz-Coffman algorithms remain central to the
foundations of the field. Coffman assembled an advanced text on scheduling and bin-packing theory entitled
Computer and Job-Shop Scheduling Theory (1975).
- Data Structures and Algorithms: The analysis of digital search trees was an active research topic for many years.
(See Knuth Vol. 3.) Coffman introduced these data structures and, with J. Eve, provided a first analysis.
- Achievable Region Theory: A substantial literature built up, especially amongst the stochastic optimization
community, on the ``achievable-region" problems of queueing theory
(e.g., synthesizing, for a given traffic load, a queueing discipline that meets pre-specified, expected
waiting times conditioned on required service times);
this field started with Coffman's work in the early '70s, first with J. Michel and
then with I. Mitrani.
- Two-Dimensional Packing: Mathematical models of two-dimensional packing problems leading to asymptotic
performance bounds were first formulated by Coffman, with the early papers co-authored variously by
B. Baker, M. Garey, E. Gilbert, D. S. Johnson, R. Rivest, and R. Tarjan.
- Moving-Server Problems: In work growing out of his interests in computer disk
systems, and in collaboration with R. Calderbank and L. Flatto, Coffman formulated moving-server
problems that were soon to be called 2-server problems. The stochastic analysis of these models
led up to the later, substantial literature on the competitive analysis of k-server problems.
- Dynamic Resource Allocation Coffman and F. T. Leighton devised and analyzed
rigorously the first (and perhaps only) provably
efficient algorithm for dynamic storage allocation. (See Knuth, Vol. 3.)
- Probabilistic Analysis of Algorithms:
- The origins of the research into the ``typical" (average-case) behavior of classical multiprocessor
scheduling algorithms appeared in the work of Coffman in the late 70's, in collaboration with
G. Frederickson and G. Lueker.
- A little later, Coffman, G. Frederickson,
and A. Yao independently did the groundbreaking average-case analysis of classical bin
- Coffman's work on the average-case analysis of partitioning problems
culminated in a book co-authored by G. Lueker on the probabilistic analysis
of packing and partitioning problems (1991). (This book was a Lanchester-prize nomination.)