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

Home > iSGTW - 17 December 2008 > iSGTW Feature - Truth serum for researchers on the grid

Feature - Truth serum for researchers on the grid

William S. Vickrey (1914-1996)
Image courtesy of

Needs images

When you request time on a shared computing resource, are you always scrupulously honest about your job’s urgency and requirements?  Andrew Mutz and his colleagues at the University of California, Santa Barbara have developed a scheduler that discourages you from fibbing. It maximizes “rewards” and minimizes “costs” to users when their stated scheduling preferences are true.  Not quite ready for prime time, it applies some time-tested concepts in a new way.

The team’s reservation-based version of the Portable Batch System (PBS) scheduler uses techniques derived from William Vickrey’s Nobel prize-winning work on the economic theory of incentives. Several variations of a scheme called the Vickrey Auction exist, the common feature being an incentive to bidders to bid their true value.  The team refers to its scheduling scheme as the Dynamic Programming Generalized Vickrey Auction, or the DPGVA.  

In computing, combinatorial Generalized Vickrey Auctions (GVA) have long been known to allocate resources efficiently while exposing users to truth-revealing incentives, says Mutz. However, the algorithms can be computationally intractable.   

Garbage in, garbage out  

Grid scheduling involves looking at the user-specified job metadata (information about the job such as its priority or requested running time).  Users sometimes “fudge” this metadata to try to make their job run sooner or faster.  When they do, the scheduler receives bad information and consequently provides poor overall resource allocation.     

Loosely speaking, DPGVA “pays” each user an amount proportional to the payoff seen by all other users. This encourages each participant to act so as to maximize the usefulness of the resource, and in so doing, be as honest as possible in defining job parameters.

A depiction of the expressive power of bids in the DPGVA.  On the left, bids must value equally all consecutive time windows before the job's deadline.  Combinatorial bids (right), on the other hand, allow bidders to specify different values to multiple, non-contiguous bundles of time slots. 

Image courtesy of Andrew Mutz.  

No free lunch

“A job’s running time depends on the number of inputs and their magnitudes,” says Mutz. “A combinatorial GVA allows more expressive power than users need. We’ve stepped back from that and simplified the requests users can make.” In the process they’ve made the scheduling computationally tractable—but with concessions that make DPGVA unready for deployment.   First, users can only request the entire resource, not a portion of it.  Second, users are subject to some granularity constraints when specifying deadlines and running time, such as access only to adjacent set-width time windows.
Testing has shown superior job completion results for honest job metadata relative to “fudged”, so the honest user comes out ahead. But the authors still need to address the scheduler’s shortcomings. Mutz and his colleagues are working on techniques to guarantee good results while breaking some constraints and to align the interests of the individual and the group for a wider range of features.

"It’s very difficult to get all the features we’d like in a scheduler and keep these provably-true incentives," says Mutz.  "So we’re working to understand just how much these incentives break when we expand the scheduler’s feature set."

Anne Heavey, iSGTW


 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