DISTINCTIONS
Notes:
- Lists of talks were not updated regularly over the years, and as a result, those below are undoubtedly missing a few items.
- 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 Recognitions
- 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.
Keynote speeches
These include
- 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
Professional
- 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 email.
- 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 packing algorithms.
- 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.)