Update 15.1: January 2003, Balls Into Bins

Balls Into Bins
New CSS member uses computer game theory to help create more efficient distributed computing systems.

Petra Berenbrink, Assistant Professor of Computing Science with her spaniels Bayes and Aristoteles.

Petra Berenbrink's PhD thesis was about balancing computational loads among many processors. She based it on something called "Ball-Into-Bin" games, where you throw balls into an array of bins. Berenbrink's research has shown that if balls arriving at bins have a choice of where to fall, even a small choice, the load on the whole system is balanced much better. Surprisingly, it takes very little to achieve this; random small choices greatly improve system efficiency.

The new SFU Assistant Professor of computing science says, "In the short term, I plan to continue my work on randomized algorithms in the field of load balancing, routing and scheduling."

Berenbrink wants to form collaborations with researchers outside computing to apply her ideas in areas like medicine, biology, physics, and engineering to name just a few. Some of her best experiences during her PhD at the University of Paderborn, Germany involved interdisciplinary research. "Generally I find collaboration with colleagues having their backgrounds in different branches of science always very exciting," says Berenbrink. "I would very much like to continue this." Contact: petra @ sfu.ca.

Next: Joining Grammar Trees