ColloquiaTalk by Petra Berenbrink on Friday, May 18th

[Marge Ishmael]

DEPARTMENT OF COMPUTER SCIENCE

Friday, May 18th at 2:30 p.m. in Ryerson 251

PETRA BERENBRINK, University of Warwick, UK

--------------------------------------------------

Title: "Scheduling for Parallel Data Servers: on
Balls-into-Bins Games"

Abstract: In the last couple of years, a dramatic increase in the need for
storing huge amounts of data can be observed.  The introduction of
enterprise resource planning, on-line transaction processing,
e-business, data warehousing, and especially the increasingly
media-rich content found in intranets and the Internet are heavily
contributing to the data load.  This is overwhelming traditional
storage architectures.  A common approach to handle this huge amount
of data is to combine storage devices into a dedicated network, called
storage area network (SAN), that is connected to several LANs and/or
servers.

The main problems occurring in the development of such storage area
networks are data placement (distribution of the data over the disks),
scheduling (scheduling of the disk accesses), and routing
(determination of path systems and routing of the data through the
network). In this talk, I will focus on the scheduling problem. I will
show that the scheduling problem is very closely related to so-called
balls-into-bins games.  The study of balls-into-bins games in its
different shades has a very long history.  These very common models
are used in order to derive a considerable number of results in the
area of probability theory.  In general, the goal of a balls-into-bins
game is to allocate a set of independent objects (tasks, jobs, data
requests) to a set of resources (servers, bins, disks). It is assumed
that the balls are independent and do not know anything about the
other balls.  Every ball is allowed to choose i.u.r. a subset of the
bins in order to be allocated in one of the bins.  The aim is to
minimize the maximum load of the bins.

In this talk, I will present several balls-into-bins games. I will
sketch two variations of witness tree proofs that can be used to
analyze the performance of these games. The method of witness tree
proofs has been developed at the University of Paderborn. The great
advantage of this proof technique is that it can be used to analyze
most of the balls-into-bins games.

*The talk will be followed by refreshments in Ryerson 255*
If you would like to meet the speaker, please send e-mail to 
marge at cs.uchicago.edu
Persons with disabilities who may need assistance, please call 773.834.8977
-- 
Margery Ishmael
Department of Computer Science
The University of Chicago
1100 E. 58th Street
Chicago, IL. 60637

Tel. 773-834-8977  Fax. 773-702-8487