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