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.