Monday, March 24, 2008
4:00 PM
5130 Upson Hall
  Theory Seminar
Spring 2008

CS 789
 

Eitan Bachmat
Ben-Gurion University

 
 

 Disk Scheduling, Airplane Boarding and the Universe

 
 
Disk drives have the ability to re-order read/write (I/O) requests, so that they can be serviced faster. This is an important practical feature that can speed up service times by a factor of 2 under favorable circumstances. About 10 years ago, Andrews, Bender and Zhang provided an algorithm to compute the optimal ordering in a special case.

We will show that their algorithm essentially coincides with the way passengers board an airplane.  We then show that both the disk scheduling process and airplane boarding can be described and analyzed using space-time geometry which models relativity theory. We will use these insights to suggest good airplane boarding policies and to suggest an elegant interpretation to Einstein's law of motion, an interpretation which can be considered as the ultimate dice game.