CDS Lecture Series


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