Waiting, waiting, waiting . . . Stock images courtesy of sxc.hu

No one likes waiting in line but-as long as no one cuts in front-we're usually happy to wait our turn. However, that changes as soon as there's the slightest hint we are being treated unfairly. In the research world, there are reports of individuals ditching their otherwise sunny disposition when they feel their jobs have queued longer than they should have.

Emmanuel Medernach noticed this among his colleagues at the LPC laboratory at the University Blaise Pascal in Clermont-Ferrand, France, where he is a member of the lab's computing management.

Medernach is now developing a new approach to grid scheduling to fix the problem. His approach has caught attention of many-including the EGEE awards committee, who gave Medernach first place in this spring's User Forum Poster Competition.

"Something has to be done to avoid inducing starvation of user computation." says Medernach. "In a queue we all expect the same treatment-we wanted the same thing for grid scheduling."

Although the lab's previous scheduling program was designed for efficiency, with the goal of maximizing mean throughput per job, the program focused on the jobs as a total-not on the users behind the jobs.

That solution might be good for the average person, but it could be bad for others. For example, a schedule that computes small, short jobs first will irk the researcher waiting for the solution to a big job. A schedule that gives priority to long jobs may never get around to the calculations of someone with many short jobs.

"We began by stating the properties we wanted our scheduling to have: impartiality and equity," says Medernach.

Impartiality means that scheduling is based on unbiased decisions. Equity means that, in allocation, the priority should be given to the neediest individuals. Medernach's approach to scheduling is inspired by the writings of John Rawls, the American political philosopher who penned "A Theory of Justice." This work attempts to marry the principles of liberty and equality, and present a way to distribute resources justly and fairly.
.

Emmanuel Medernach is working on fair grid scheduling for his PhD thesis at University Blaise Pascal in Clermont-Ferrand, France. To learn about his work view his prize winning poster. Photo courtesy of Emmanuel Medernach.

What is "fairness," really?

Medernach and his PhD advisor, Eric Sanlaville, from the LIMOS laboratory at University Blaise Pascal, found that fairness involves a multi-dimensional assessment of each user criterion. Then the only way to design an order based on impartiality and equity is known as a Leximin order, which ranks vectors by examining first the least well-off user, then the one who is just above, and so on. This approach, well established in the realm of economics, is novel to grid scheduling.

Medernach and Sanlaville are currently studying how to theoretically schedule simple job batches. Once they master this they will begin work on scheduling more complicated batches. In time they want to see this scheduling approach become real working software. To help with the development and testing of scheduling models, they are hoping to attract the attention of several grid projects interested in forming partnerships.

- Danielle Venton, EGEE