BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Scheduling for Communication and Processing Networks - Walrand\, J
  (UC\, Berkeley)
DTSTART:20100115T110000Z
DTEND:20100115T120000Z
UID:TALK22505@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:The talk reviews the history and recent results on the schedul
 ing of tasks that require access to a set of resources. The first step was
  the discovery that maximum weighted matching achieves the maximum through
 put for a class of such scheduling problems that includes wireless network
 s and packet switches. However\, this algorithm is too complex to be direc
 tly applicable. The second step was understanding when a simpler algorithm
 \, longest queue first\, also achieves maximum throughput. The third step 
 was inventing a distributed algorithm where tasks select an independent ra
 ndom back off delay before asking for the resources\; this delay has a mea
 n value that decreases exponentially with the backlog. Using stochastic ap
 proximation theory\, one shows that this algorithm achieves the maximum th
 roughput. The fourth step is a modification of maximum weight matching to 
 achieve the maximum utility in a processing network where tasks not only s
 hare resources but also require access to parts. The talk explains the int
 uition behind the results and the main ideas of the proofs.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR