RESEARCH

The principal focus of my career has been on research, teaching, and service to the professions of electrical engineering and computer science.  My performance in teaching and university administration has been at best mediocre if you are to believe opinions expressed by disenchanted (unprepared) students and (witless) administrators. I offer more counterpoint when I cover my teaching experiences and the grief I went through as an administrator.  Something the reader with a taste for schadenfreude might enjoy.

My research contributions are reviewed in Section I below.  The publications section shows that the contributions span more than 50 years, from 1964 to 2015.  Sections I.A and I.B, which describe my  salad days, are distinguished by what might appear as surprising corrigenda to the history of computing dating back to the early 1960’s, when the System Development Corporation (SDC) and MIT played dominant, very early roles in systems R&D.  This revision of history properly sets MIT in a position inferior to that of SDC, especially where it refers collectively to the origins of email, time-sharing systems, computer networks, and stochastic modeling of time-shared and networked computer systems.   In particular, the results require a number of MIT faculty and graduates to cede to, or in one case to share with, researchers at SDC their claimed position of being first to break ground in system development or analysis in the above categories.  Two key authoritative and refreshingly objective publications clarify much of the existing record, both written quite recently by David Hemmendinger in the IEEE Annals of the History of Computing, “Messaging in the Early SDC Time Sharing System,” 36, 1, 2014, and “Two Early Interactive Computer Network Experiments,” 36, 3, 2016.   

The details describing the principals involved, and their failures to acknowledge earlier work, are not a focus here.  Needless to say, the typical argument of those who fail to acknowledge the past is that they were ignorant of it.  This argument in the circumstances surrounding the inventions and systems development discussed below, in particular the interactions between MIT and SDC in the 60’s, is trivial to refute. These breakdowns in scholarship, which have marginalized my team of collaborators, especially its leader Jules Schwartz (may God rest his soul), are covered at length in a companion document (history-revised.docx) well informed by the objective coverage in the Hemmendinger papers.  

Section II lists research grants acquired while in academia (1966-1978, 1999-2008). Section III lists the 150+ colleagues with whom I have collaborated and to whom I owe much of my success , and the great pleasure and fulfillment I’ve experienced in my work (I call it work, but much of it was just fun which, as a bonus, often  made useful scientific advances as well).

NB In what follows, the references to the publications section have the form:  [acronym, paper#].  The acronyms are defined at the beginning of the publications section, e.g., [OS,5] refers to paper number 5 in the Operating Systems category, [SM,3] stands for paper number 3 in the Stochastic Matching category, etc. The reader will discover early that the sequencing of the publications is not the same as the sequencing of the research projects reviewed below.

1. Research Review
   1. Systems R&D: The Early Years 1958-1965

      Contributions to large-scale systems research were made during my 7-year tenure at the System Development Corporation (SDC), a non-profit spin-off of the Rand Corporation, where I participated in a small team of initially 5 system programmers led by Jules Schwartz .  This team built the landmark SDC-ARPA Time-Sharing System (called TSS) operating on IBM’s AN/FSQ-32 computer (called the Q-32) during a six-month period beginning in late 1962.  TSS as described below was released for general usage in mid-1963 and represented three pioneering events in the history of computer operating systems, communications, and networks.  

      1. The Origins of General-Purpose, Time-Shared Computers.  The early 1963 release of TSS to SDC users was essentially coincident with the release of the Compatible Time Sharing System (CTSS) to MIT users.  These two systems were contemporaneously the general-purpose sequels to earlier systems, e.g., the term "general purpose" excludes 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 (Proc. Spring Joint Comp. Conf., 1963), although this work influenced TSS as did the early thinking behind CTSS. The vision of time-shared computers dates back at least to the late 50's; see for example the references in "An Experimental Time Sharing System," by F. Corbato, M. Merwyn-Daggett, and R. Daley (Proc. 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 the vision of a general-purpose time-sharing system and its successful implementation was a large one, made so not only by software challenges, but also, and to perhaps an even larger extent, by existing hardware limitations.  .

         As one of the five members of the team that built the initial version of TSS, my role was the design and programming/coding of the operating-system kernel responsible for resource allocation, and the scheduling/dispatching of tasks initiated by the system and its users.  

         I joined colleagues Jules Schwartz and Clark Weissman in writing the prize-winning `best paper’ presented at the 1964 Spring Joint Computer Conference [OS,9] approximately 9 months after the events it chronicled.    It described TSS, the architects’ experience with its use, their plans for its development in the near term, and their vision for its future.  TSS 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, and an on-line IPL-V programming system.   

         It is fair to say that, in closing the gap between the vision and reality of general-purpose time-sharing systems, both TSS and CTSS  jointly became a landmark engineering event in the history of computing, validating as they did one of the more fundamental paradigm shifts in the early days of computing.

      2. The Formative Stage of Email  In 1963, TSS also provided in a second landmark event a mail command called DIAL (see p. 399 of [OS,9]) which allowed remote as well as local users networked by TSS to communicate on-line.  This event launched the evolution of user communications in computer networks which led up to today's email on the Internet, a service which has become a permanent part of the infrastructure of society.  Claims have existed on the Internet and in the literature for decades that it was two years later in 1965 that CTSS was first to provide a mail-type command.   David Hemmendinger’s article in the 2015 IEEE Annals of the History of Computers , “Messaging in the Early SDC Time-Sharing System,” reveals the error in such claims, and shows that this benchmark in computing history must be attributed to the team that built TSS at SDC in 1963.   

         The conceptually obvious extension of this mail facility from networks of users to networks of computers each with a network of users followed quickly on the heels of the Arpanet experiment and has been attributed to R. Tomlinson who has been lionized for introducing the `at’  symbol, @, as the connective between the addressees and their addresses in  email.  It is unfortunate that he is also regarded by many as the originator of email.  The wordplay  needed to make this true is to insist on regarding the mail passing from one online correspondent to another in the same computer system as `messages;’ no matter how remote the  correspondents might be; a message becomes `email’ only if it is transmitted along a path that includes at least  one intermediate computer.  The irony in these events is that neither the origin of email, i.e., the initial version at SDC in 1963, nor Tomlinson’s subsequent, obvious extension of the concept was thought to be of special importance at the time it was implemented.

      3. A First Experiment in Computer Networking: A third pioneering event was an experiment demonstrating the promise of networks of time-shared computers that would become a norm of the computing field. In this respect, TSS was a pioneering event in a sense orthogonal to its historical time-sharing role. Specifically, experiments in interactive computer networking had their debut at SDC in the same system organized around IBM's Q-32 computer. The system became a node of a two-computer network, a network that began with a connection between the Q-32 and a CDC 1604 computer at the Stanford Research Institute (SRI) some 300 miles distant.   Plans were made for connections to several more remote computers. The term `networking’ as used here embraces the users of the networked computers as well the computers themselves.

         The TSS hardware included a relatively small front-end computer, a PDP-1 (Fig. 1, [OS,9]), reminiscent of the subsequent ARPANET IMP. Two years later, in 1965, another experiment in long-haul computer communications was initiated when a link was established between the Lincoln Labs (LL) TX-2 computer and the TSS node at SDC.  (See "Toward a Cooperative Network of Time Shared Computers" by T. Marill and L. Roberts, Proc. Fall Joint Comp. Conf., 1966).  Both experiments were short-lived and necessarily ad hoc.  The SDC-LL experiment was touted as the first experimental 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-SRI networking experiment promoted by Licklider (who was noticeably absent from the above author list) at ARPA obviously predates this work, however, thus establishing a historical fiction in the networking community that endured for 50 years. That so many well-known scholars were unaware of the earlier networking experiment supported by the same funding agency is so striking as to be deeply suspect.  See historical details in the recent article by David Hemmendinger:  “Two Early Interactive Computer Network Experiments,” in the IEEE Annals of the History of Computers,    36, 3, 2016.    See also the book by Bourne and Hahn, A History of Online Information Services , 1963--1976, MIT Press, 2003. The document (history-revised.docx), a companion to the current document, has a discussion of certain of the principals involved in this lapse in scholarship which is strongly suggestive of how the lapse originated.

          

   2. 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. Leonard Kleinrock applied expected-value arguments to obtain mean delays created in an approximate mathematical model of a time sharing system (Nav. Res. Logist. Quart., Mar. 1964). In an independent project, more realistic studies by a small group at SDC adopted finite-source models, represented the quantum/time-slice as the tunable parameter it was meant to be, and presented results for continuous-time processes. A technical report written by C. and Krishnamoorthi in 1964 [QS,25] eventually appeared in C.’s Ph.D. thesis in 1966. This work led almost immediately to a generalization by Krishnamoorthi and Wood that appeared in a later 1964 SDC report and eventually came out in J. ACM in 1966.

      Performance monitoring of the new time-sharing systems began at SDC in the early '60s (see the announcement in the 1964 article [OS,9]).  I instrumented TSS and collected performance data to demonstrate the effectiveness of the TSS design and to characterize statistically users of time-sharing systems. The results were analyzed and published in a 1965 SDC technical report  by C. and  Wood entitled  “Interarrival Statistics for Time Sharing Systems,'' and subsequently published in  Comm. ACM [QS,25]  in 1966.

      In research at MIT having a later start in 1965, Allan Scherr collected data on CTSS  and proposed in his PhD thesis that it could be approximated by a simplistic, continuous-time Markov process for a finite-user system.  Unfortunately, neither the quantum size nor swapping times could be naturally incorporated in the model.  Nor was the model specifically oriented to the running-time priority disciplines of time-sharing systems like CTSS .   A revision of Scherr’s thesis was published as a monograph by MIT Press in 1967.   A search for a publication of Scherr’s work among standard refereed technical journals came up empty.   For further discussion see (history-revised.docx)

      In the late '60s and early '70s, I combined with L. Kleinrock and later with R. Muntz in a number of papers analyzing computer running-time priority queues, e.g., the foreground-background model studied originally by L. Schrage:  “The Queue M/G/1 with Feedback to Lower Priority Queues,” Management Science, 13, 7 (1967), which has the strongest early results on feedback priority queues.   The expected waiting time for the Markov PS (processor-sharing) queue was obtained by Kleinrock by computing a formal limit of a result for his approximate model of the round-robin discipline. The result was quite intuitive, but left a burning question when it comes to the performance of round-robin and PS disciplines:  Equally if not more important is the second moment which gives a better idea of the sacrifice large jobs make in longer waiting times in order to reduce the waiting times of short jobs. This appeared in the first rigorous analysis of the PS process itself, which can be found in [QS,15]; where I, Muntz, and Trotter obtained generating functions for the unconditional waiting-time distribution and the distribution conditioned on the amount of service required.  The PS process and its variants subsequently became extremely widely used tools in the study of computer and communication systems and networks; they rivaled the FIFO queue in importance, and continue to be studied in new settings.

      Our analysis of PS sojourn times in an M/M/1 queue, though a little difficult to get right, followed a more or less conventional program.   Customers with exponential service times arrive in a Poisson stream at a single, sharable server, where the term sharable means that the customers in the system simultaneously share the service rate in equal amounts.  The share increases and decreases in the obvious way when departures and arrivals take place.  One begins the analysis with the usual birth-and-death approach leading to a differential-difference equation for the conditional sojourn time of a customer in terms of its required service, the arrival time, and the number of customers already in the system.  One then computes a Laplace transform with respect to the time variable and then a generating function with respect to the number in system to obtain a first order partial differential equation in both the transform variable and the generating function variable.  Conventional methods lead to explicit formulas from which moments can be computed in the usual way.  A (very lengthy) calculation of the variance showed, as perhaps the most striking characteristic of the sojourn times for large jobs, that they pay dearly for the reduced sojourn times of small jobs.

   3. Auxiliary storage

      Groundbreaking papers in the analysis of secondary storage were among my earliest contributions to the field, e.g., the rotating-server model representing drum scheduling in early computer systems. My interest in this field continued well into the 80's; see e.g., my analysis of scanning disks [AS,3] and queueing models [AS,1] with M. Hofri.  These classical computer I/O devices had in common a surface moving relative to `servers’ (read/write heads). This led to intriguing generalizations of the surfaces assumed (mathematically an interval, a rectangle, or a sphere) and the number of servers.   See Section G for the related stochastic optimization problems continuous in both time and space.  And for a comprehensive review of most of this work, see the chapter by myself and Hofri ``Queueing Models of Secondary Storage Devices” in the book by H. Takagi, (Ed.), Stochastic Analysis of Computer and Communication Systems, Elsevier Science, 1990.

   4. Books on Performance Evaluation

      Together with notable work on scheduling (see below) and system deadlocks, (e.g., with Shoshani [OS,7]), much of my early research in Performance Evaluation (PE) was combined with that of Denning in the book Operating System Theory, which we co-authored in 1973 [OS,3]. Prentice-Hall continued to sell this book for 20 years, unusual in a field that has been outstanding for its frequent advances and paradigm shifts. This was the first book devoted largely to performance modeling and analysis of computer operating systems. Much later, O. Aven and Y. Kogan - Russian colleagues at the time - and I co-authored a book [SS,1] on computer storage problems, an early example of the work made possible by the glasnost policy in Russia.

      In spite of the then new openness and the perestroika movement in Russia, the latter book was a test of patience.  I would promptly communicate my contributions, whether edits or new material, to Aven-Kogan, just as soon as they put the ball in my court with their own contributions.  Each such exchange took at least a month to 6 weeks in each direction!  It took 8 years to complete this book.   I trust the reader will forgive the authors for an error rate rather larger than the norm.  The end of this process was more the result of fatigue than a sense that the book was truly complete and properly edited.

      
      
      

   5. Combinatorial Scheduling

      My  early studies of service systems and scheduling policies extended to combinatorial scheduling immediately upon my arrival at Princeton in 1966, where I published what were to become pioneering papers with R. Muntz [STC,24,27] and R. Graham [STC,23]: The Muntz-Coffman algorithms and the Coffman-Graham algorithm are among the field's foundations. The latter work resulted in an optimization algorithm for the 2-processor, unit-execution-time makespan minimization problem with tasks constrained by a precedence graph (irreflexive partial order).  The complexity of the corresponding 3-processor problem remains tantalizingly open after more than 45 years.  .As an editor and co-author, I collaborated with J. Bruno, R. Graham, W. Kohler, R. Sethi, K. Steiglitz, and J. Ullman [STS,3] to write a highly popular, advanced text on combinatorial scheduling and bin-packing theory, with new copies still in demand after almost 50 years.  The reader need only make a request to have a copy free of charge.

      Highlights of further work in scheduling include the design of the MULTIFIT algorithm in a paper I co-authored with Garey and Johnson [STC,12]; this was a SIAM best paper selection for 1978.  Makespan was the objective function and the basic new idea was to apply an efficient bin-packing algorithm iteratively on candidate capacities, packing into “bins” the tasks being scheduled on processors until a smallest, sufficiently large capacity (schedule length) was found.

      This paper is still being cited after nearly 40 years.

      Garey and I collaborated in solving an enticing scheduling problem that had remained open for 20 years.   The problem was to schedule unit-length jobs on 2 processors subject to a given precedence graph to minimize schedule length.  An upper bound on the ratio of the length of an optimal non-preemptive schedule to the length of an optimal preemptive schedule was proved to be 4/3.  The proof was a “tour de force” in the sense that the paper contained some 40+ figures illustrating the steps of an unusually deep and extensive case analysis.  As of this writing no-one has yet submitted a simpler proof, or a proof of a more general result. And indeed, I know of only two or three who have given the current proof a full test.

      Among the co-authors of other work in this area are S. Even, M. Magazine, C. Santos, M. Yannakakis, A. Nozari, M. Langston, J. Labetoulle, R. Sethi, W. Kubiak,  D. Dereniowski, J. Bruno,  and V. Timkovsky.

      The literature on the average-case analysis of scheduling algorithms was launched by the seminal work I did with G. Frederickson and G. Lueker [STP,4].  We analyzed the largest-first (LF) rule applied to independent tasks on two processors, with i.i.d. task running times drawn from a uniform distribution.  Bounds on expected makespans were derived.  Further analyses of problems of this type were done in collaboration with L. Flatto, W. Whitt, and E. Gilbert.

   6. Bin Packing

      Motivated by computer storage applications, I moved into the design and analysis of bin packing approximation algorithms. Seminal contributions include the extension of bin packing to 2 dimensions: the strip packing problem. The first two theory papers in what is now a substantial literature on the subject are by Baker, Coffman, and Rivest [BPH,11] and by Coffman,  Garey, Johnson, and Tarjan [BPH,9].  

      In the late '70s. the average-case analysis of bin packing was pioneered by Coffman, So, Hofri, and Yao('80), a field that is now well developed; see the text by Coffman and Lueker ('91), a Lancaster award nomination.  The main result of that paper was a tight bound on the expected performance of the Next-Fit algorithm.   The extension of probabilistic analysis to discrete item-size distributions was inaugurated by Coffman, Courcoubetis, Garey, Johnson, McGeoch, Shor, Weber, and Yannakakis (1991). My most recent paper in this area was by Coffman, Courcoubetis, Garey, Johnson, Shor, Weber, and Yannakakis (2000) and was chosen as one of SIAM's best papers of 2000.

   7. Moving-Server Problems:

      With Calderbank and Flatto, I wrote several papers on the analysis of stochastic models of moving-server problems that originated in the study of disks with multiple heads, a continuation of my earlier interests in auxiliary storage systems. The subsequent, large literature on the combinatorial competitive analysis of k-server problems was initiated at Bell Labs by D. Sleator and R. Tarjan, and followed on the heels of our stochastic analysis in the same research center.  

      To get a better idea of the types of problems I and my co-authors studied, model the radius of a disk surface by the unit interval with two movable points modeling R/W head locations.  Suppose the heads are on the same arm with the distance d between them fixed.   R/W requests must be satisfied first-come-first served and are modeled by a sequence of  i.i.d. random variables uniformly distributed over the unit interval.  We calculated the invariant measure of a Markov chain representing successive head positions under the nearer-server (NS) rule: Requests in [0,d] are processed by the left head, those in [1-d, 1] by the right head, and those in [d, 1-d] by the nearer of the two heads. An interesting result was the equilibrium expected distance that the heads had to be moved in processing a request. A basic insight of the analysis was that a system with two heads performs more than twice as well as a system with a single head.  Experiments demonstrated that NS is very nearly optimal under the fixed head-separation constraint.

      We also analyzed a service system in which two servers move independently on the surface of a sphere.  Requests for service arrive independently and uniformly over the surface and are served in order of arrival.  We showed that the NS policy is optimal among all server selection policies in the sense that it minimizes the equilibrium expected angular distance which a server moves to process a request.  We derived an integral equation for the equilibrium measure for the angular distance between servers under the NS policy.  Numerical results were obtained from this analysis.

   8.  Dynamic Storage Allocation:  

      In the '80's, I 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 [DR,10] explicit results were obtained for the case of equal-size files and an underlying infinite-server queueing model. With Tom Leighton [DR,7], I helped design 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 I had a couple of major contributions, particularly with Shor. In another work with Flatto and Leighton [DR,5], the infinite-server probability model was changed to a single-server model. Other co-authors in the analysis of stochastic models include Charles  Knessl and I. Mitrani.

      Combinatorial models of DSA that I studied included the very difficult two dimensional case with Gilbert [DR,15], the study of compaction and insertion algorithms with Baker [DR,14], and algorithms for resolving conflicts with Baker and Willard [DR,13].

   9. Stochastic Scheduling

      Among the seminal papers are studies of two parallel-machine problems differing only in the objective function. Common to both studies is a problem of scheduling n jobs non-preemptively on m uniform processors under the assumption that job running times are not known in advance, but are known to have exponential distributions with rate parameters depending only on the assigned processor. In the earlier paper,  Agrawala, Coffman,  Garey, and Tripathi [STS,9] take total flow time (sum of finishing times) as the performance measure to minimize, while the subsequent paper by Coffman,  Flatto,  Garey, and  Weber [STS,8] takes the makespan (latest finishing time) as the measure to minimize. The solution to the first problem is an elegantly simple threshold rule; but no such solution has been found for the second (makespan) problem.

      For the makespan problem, we show that, for m = 2 and 3, there exist optimal scheduling rules of threshold type, with easily computed thresholds. We conjecture that similar threshold rules suffice for m > 3 but are unable to prove this. However, for m > 3 we do obtain a general bound on problem size that permits Bellman equations to be used to construct an optimal scheduling rule for any given set of m rate parameters, with the memory required to represent that scheduling rule being independent of the number of remaining jobs.

      The research described below on fault tolerant systems also falls in this general category of stochastic scheduling.

   10. Fault-Tolerant Computing

       Mathematical models of systems that tolerate faults/malfunctions have been yet another source of intriguing problems, dating back in my case to the 80’s and 90’s.  Typically, the problems have asked for algorithms that maximize the probability that a computation completes before all machines have failed, or, in the case of repairable machines, algorithms that minimize the expected time to complete the computation.  The error-handling primitives/mechanisms are saves, checkpoints, and redundant machines.  At a checkpoint the system determines whether a fault has occurred since the previous checkpoint.  Also at checkpoints, a save can, if desired, store the current state of the computation on some secure storage medium.   A computation can then be put back in that state in response to a fault discovered at a later checkpoint.   Apart from the probability law governing failures, the parameters defining specific problems include answers to the following questions:  A) are system errors self-evident “meltdowns”, or does the cost of an explicit test have to be incurred to determine whether a computation is in a flawed state?  B) are there multiple parallel machines that can run the computation in lock-step?  C) are failures permanent, or are machines repairable – at a cost?  D) is the running time of the computation known in advance?

   11. Queueing Reprise

       My probability models of performance evaluation were many and varied. They included 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 Probability Society of INFORMS.

   12. Molecular Computing: Stochastic Modeling of Self-Assembly

       A research project begun in 2002 centered on the stochastic analysis of self-assembly in the tile-system model of DNA-based computing. Collaborators were Y. Baryshnikov, P. Momcilovic, B. Yimwadsana, and Ned Seeman. Yimwadsana's PhD thesis together with several ground-breaking papers resulted from this project. Speed of computation and power consumption are the two main parameters of conventional computing devices implemented in microelectronic circuits. As performance of such devices approaches physical limits, new computing paradigms are emerging. DNA-based molecular computing is one of them.

       Specifically, in a paper of mine with Baryshnikov and Momcilovic, we focus on an abstraction to growth models where computational elements called tiles are self-assembled one by one, subject to some simple hierarchical rules, to fill a given template encoding a Boolean formula. While DNA-based computational devices are known to be extremely energy efficient, little is known concerning the fundamental question of computation times. In particular, given a function, we study the time required to determine its value for a given input. In the simplest instance, the analysis has interesting connections with interacting particle systems and variational problems.

       In another paper adding Seeman and Yimwadsana as co-authors, we extend the stochastic analysis to models incorporating an error-correcting technique called pulsing which is analogous to checkpointing in computer operation. The model is again couched in terms of the well-known tiling models where the focus is on the times to self assemble rectangular structures. Explicit asymptotic results are found for small error rates, and exploit the connection between these times and the classical Hammersley process.

   13. Achievable-Region Theory

       The so-called ``system with feedback to lower priority queues" is a well-studied computer scheduling policy; it contains many parameters, in general, which must be fixed in order to achieve a given waiting-time performance. The problem of synthesizing a system of the above type which satisfies pre-specified expected (conditional) waiting-times is solved by J. Michel and me, by computing appropriate parameter values, assuming that Poisson arrival and general service-time parameters are known. The solution space defines an ``achievable region," a term introduced by others in subsequent research on generalizations of this problem not tied to specific service disciplines.

       Building on this research, Isi Mitrani and I formulated a significantly more general multiclass model not tied to any particular set of policies beyond those considered to be reasonable or feasible: specifically, those policies that use no information about future arrival or service times, that never keep servers idle when there is at least one unfinished job, and that base scheduling decisions only on information available in the current busy period. Required performance is given by a vector with a component for each customer class (in our case the vector is an ordering of expected waiting times). The achievable region, which we showed to be a polyhedron, contains all such vectors that can be realized by a multiclass service discipline. The vertices of this region play a special role.

   14. Studies of 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).
   15. Sensor Networks: Modeling and Analysis of Minimalist Local-Rule Processes.

       (The PhD thesis of K. J. Kwak - Y. Baryshnikov and I were co-advisors - covers much of the research in this area.)

       My contribution with Yuliy Baryshnikov and KJ Kwak in our paper ``High Performance Sleep-Wake Sensor Systems Based on Cyclic Cellular Automata" is a scalable, easily implemented, self-organizing, energy conserving intruder- detection sensor system applying concepts from cellular automata theory. The system self-assembles periodic wake-sensor barriers (waves) that sweep the sensor field; it is highly effective even in the case of frequent communication failures, sensor failures, large obstacles, and when intruders know sensor locations.

       Our contribution in a later paper, ``Cauchy Localization: A Distributed Computation on WSNs,'' deals with the localization problem of a wireless sensor network (WSN) which is posed as a distributed computation performed by the sensors alone. A relatively small number of the nodes along the boundary of the WSN are initialized with their exact locations, which serve as reference coordinates that seed the computation. A range-free, scalable localization protocol begins with a self-organizing, local-rule, distributed computation: In a converging sequence, each sensor periodically takes as its location an estimate of the average of its neighbors' estimates. These estimates are used to construct an instance of the Cauchy Integral Formula from which the final location estimates are produced. The results convincingly argue that this approach is superior to other range-free methods operating under similar minimalist constraints. Among the salient properties of the approach is a tolerance to variations in timing and sensor density, and to variations in the characteristics of individual sensors, such as computing speed and communication range.

       We were joined by a fourth co-author, W. Moran, in writing the paper, ``Stochastic Counting in Sensor Networks (Noise Helps)" We propose a novel algorithm for counting N indistinguishable objects, called targets, by a collection of sensors. We adopt a minimalist scenario where sensors are unaware of the (non-empty) intersections of sensing regions, and so simple addition of all sensor counts inflates estimates of the total number of targets. The multiple counting in intersections must be accounted for, but with nothing more than the sensor counts, this is clearly impossible. However, noise is typically present in the target counting of many, if not most, applications. We make the key observation that if there is a (target-dependent) noise source affecting all sensors simultaneously, then it couples those with non-empty intersections. Exploitation of this coupling allows them to extract multiple-counting statistics from stochastic correlation patterns, and hence to compute accurate estimates of the number of targets via the classical inclusion–exclusion formula. Cumulants are the correlation measures of choice. The analysis brings out and resolves certain technicalities that arise in the statistical counting algorithm.

   16. Combinatorial Scheduling Theory – A reprise

       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.

2. 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.

   
   
   

   III. Colleagues

   All but 3 or 4 of those listed below are co-authors of papers and books. The remainder 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, Teofilo Gonzalez,  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, Charles Knessl, Yasha Kogan, Walter Kohler, Sasha Kreinen, Krish Krishnamoorthi, Wieslaw Kubiak, KJ Kwak
   • Jacques Labetoulle, Jeff Lagarias, W. Lai, Mike Langston, Tom Leighton, Jan Karel Lenstra, Joe Leung, Zhen Liu, George Lueker
   • Mike Magazine, Colin Mallows, Rob Margolies, Silvano Martello, 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
   • Ram Ramaswami, 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
   TOP /  CONTACT / HOME