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


Eitan Bachmat 

Disk Scheduling, Airplane Boarding and the Universe 

Disk drives have the ability to reorder
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 spacetime 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.
