Abstract
A Grid resource broker is the arbiter for access to a Grid’s computational resources and therefore its performance and functionality has a wide-ranging influence on the utilization and performance of the Grid. Ideally, we want to avoid relying on a single ‘trusted’ resource broker because it may not be trustworthy. For example, a broker holding a resource auction could examine and reveal bid information to others, or defraud participants by subverting the auction results. The use of privacy preserving and verifiable auction protocols offers guarantees beyond those possible in real world auctions, making the electronic auctions as secure, or more secure, than their physical counterparts. This chapter provides the background to understand privacy preserving and verifiable auction schemes and discuss the implications of adopting them on Grid architecture. It then evaluates a range of potential secure auction schemes and identifies those that are most suitable to be adopted within for use in the Grid.
TopBackground
Auctions are favored as an efficient solution to the challenge of distributed resource allocation in both economic (Buyya et al., 2002; Bubendorfer et al., 2005; Chien et al., 2005) and can also be successfully applied in noneconomic (Malone, Fikes, Grant, and Howard, 1988) resource allocation systems. There are four main types of auction protocol; the English, Dutch, Sealed-Bid, and what has since become known as the Vickrey auction protocol. The English auction is the conventional open outcry, ascending price, multiple bid protocol. The Dutch auction is an open outcry, descending price, single bid protocol. The Sealed-Bid, or tender, is a sealed single bid, best price (1st price) protocol in which all bids are opened simultaneously. The Vickrey auction is similar to the Sealed-Bid auction, except that the winning bidder pays the amount of the second bid (2nd price). The second price bid mechanism results in a dominant strategy of truthful bidding in private value auctions, that is, bidding your true value will always give the best return regardless of other bidders strategies. It is worth noting that the revenue equivalence theorem states that all of the four main auction protocols return the same revenue in private value auctions (Vickrey, 1961), hence the selection of an auction protocol usually depends on implementation pragmatics such as messaging requirements.
Key Terms in this Chapter
Auction: The sale of some item or items where an auctioneer is selling to a set of bidders who place bids. An auction employs dynamic pricing dependant on the values of the bids.
Combinatorial Auction: An auction where there is more than one heterogeneous item for sale. Bidders can place bids on combinations of specific items.
Privacy Preserving: Maintaining the confidential nature of some item. An auction can be said to be privacy preserving if any confidential data sent to the auctioneer that does not need to be revealed to complete the auction remains confidential.
Trust: Reliance placed on a party for some purpose such as correctly computing an auction result, or not revealing private information.
Combinatorial Allocation Problem: How to efficiently allocate the items in a combinatorial auction to the bidders in an optimal way.
Verification: To check that some process has been correctly completed. Verification of an auction involves at the minimum checking that the auction protocol has been correctly executed, and that all bids have been counted.
Encryption: To alter data using a secret code so that it is unidentifiable to unauthorized parties. Authorized parties can use a code to decrypt the data to it’s original form.
Grid Economy: The grid economy is a market in which computing resources and services are bought and sold on demand.
Grid Resource Broker: A grid resource broker is a grid application scheduler that is responsible for resource discovery, selection, scheduling, and deployment of computations over resources.
Trustworthy: Deserving of trust, often due to past actions or reputation.