RESEARCH
AFFILIATIONS: SERVICE: DISTINCTIONS: PUBLICATIONS: CONTACT: HOME:

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 Research   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 A. Constantinides) 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) Localization 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.

 

	Research Grants 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 below) 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 (renewed 1973) National Science Foundation 1976-1980, 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 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 (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 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. Conf., 1961.) 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. 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 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 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 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 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)); 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 (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 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 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, 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, 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 Jean-Marie, 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 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