Feature - Truth serum for researchers on the grid
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.
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.
"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