Scheduling

Motivation

Scheduling is the problem of deciding how to allocate scarce resources to best achieve some objective. Computer systems researchers started studying scheduling in the 1960s during the development of operating systems. In this context the resources would be components of the computer, such as CPUs, memory, and I/O devices. As the client-server model of computing (e.g. database servers, web servers, mail servers, name servers, etc.) became ubiquitous in the subsequent decades, algorithmic scheduling research was not significantly affected as the underlying natural theoretical problems were similar. However, it is now the case that in many information technologies, the network, and not the servers, has become the limiting factor in obtaining better performance.

The goal of this Dagstuhl Seminar is to bring together part of the community of algorithmic researchers who focus on scheduling, and part of the community of algorithmic researchers who focus on networking in general, and resource management within networks in particular. These communities are far from unknown to each other as they attend the same general academic conferences. But as each community has its own specialized conferences, there is less interaction between these communities than there should be. Further there are differences in the types of algorithmic problems these communities are naturally drawn towards. We expect that the outcome of this seminar will be more collaboration between the two communities. The main collaboration that we foresee will arise from the networking community describing various models and associated resource allocation problems and, together with the scheduling community, making progress on some of the algorithmic problems in these models. We also anticipate that the scheduling community may have problems that are amenable to techniques developed in the networking community.