iSGTW - International Science Grid This Week
iSGTW - International Science Grid This Week

Home > iSGTW 21 May 2008 > iSGTW Feature - Let's be fair: A new approach for grid scheduling


Feature -  Let’s be fair: A new approach for grid scheduling

Waiting, waiting, waiting . . .

Stock images courtesy of

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


 iSGTW 22 December 2010

Feature – Army of Women allies with CaBIG for online longitudinal studies

Special Announcement - iSGTW on Holiday

Video of the Week - Learn about LiDAR


NeHC launches social media

PRACE announces third Tier-0 machine

iRODS 2011 User Group Meeting

Jobs in distributed computing


Enter your email address to subscribe to iSGTW.


 iSGTW Blog Watch

Keep up with the grid’s blogosphere

 Mark your calendar

December 2010

13-18, AGU Fall Meeting

14-16, UCC 2010

17, ICETI 2011 and ICSIT 2011

24, Abstract Submission deadline, EGI User Forum


January 2011

11, HPCS 2011 Submission Deadline

11, SPCloud 2011

22, ALENEX11

30 Jan – 3 Feb, ESCC/Internet2


February 2011

1 - 4, GlobusWorld '11

2, Lift 11

15 - 16, Cloudscape III

More calendar items . . .


FooterINFSOMEuropean CommissionDepartment of EnergyNational¬†Science¬†Foundation RSSHeadlines | Site Map