Randy Cogill

Department of systems and Information Engineering

University of Virgina

** Simple, effective scheduling strategies based on randomized load balancing**

Many scheduling problems in networks can be posed as standard optimization
or stochastic control problems. However, computing and implementing optimal
strategies often involves impractical levels of computation and
communication.

Although optimal strategies are often not practically implementable, simple randomized strategies often work surprisingly well. In this talk, I'll discuss the problems of matching in peer-to-peer networks, multiprocessor scheduling, and packet switching. In each case, a simple randomized strategy performs comparably to an optimal strategy. I will also present several probability inequalities that are used in the analysis of these strategies.

Back to CDS Lecture Series

Back to Intelligent Servosystems Laboratory