Incentives - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 92

the parameters in its utility function so as to optimally respond to the current
market situations.
Sanghavi and Hajek [Sanghavi and Hajek, 2005] observed that in a typical
auction-based pricing mechanism as described above, there is a heavy com-
munication burden on the peers. Indeed, the entire set of user preferences
has to be communicated from a peer to the auctioneer. Sanghavi and Hajek
then analytically derived a class of alternative information mechanisms that
can significantly reduce the communication overhead. Specifically, each peer's
bid is only a single real number in each case, instead of an entire real-valued
function.
Hausheer and Stiller [Hausheer and Stiller, 2005] studied a completely
decentralized auction approach for electronic P2P pricing of goods in a system
called PeerMart (which is built on top of Pastry [Rowstron and Druschel,
2001b]). The key idea is the usage of a broker set which comprises other peers
in the electronic marketplace. Specifically, a broker set consists of peers whose
IDs are closest to the ID of the good in the auction. Each of these peers then
potentially acts as the auctioneer in the selling process. The advantage of the
broker set-based method is that in case a particular peer in the set is faulty
(or even malicious in the sense that it does not respond to auction requests),
another member in the set can take up the role of auctioneer. An example is
shown in Figure 5.8.

5.2.1.9 Exchange-Based Systems

Motivated by the fact that any payment/credit-based system entails a
significant transaction and accounting overhead, Anagnostakis and Greenwald
[Anagnostakis and Greenwald, 2004] proposed an exchange-based P2P file
sharing system. The fundamental premise is that any peer gives priority to
exchange transfers. That is, in simple terms, any peer is willing to send a file
to a peer that is able to return a desired file. However, based on this idea, it
is incorrect to consider two-way exchanges only. Indeed, a “ring” of exchange
involving two or more peers, as shown in Figure 5.9, is also a proper P2P file
transfer.
In the exchange-based P2P file sharing system, each peer maintains a data
structure called incoming request queue (IRQ). Now, a crucial problem is how
each peer can determine whether an incoming request should be entertained,
i.e., whether such a request comes from some peer on a ring of exchange
requests. It is obviously computationally formidable to determine all the po-
tential multi-peer cycles. Fortunately, Anagnostakis and Greenwald [Anagnos-
takis and Greenwald, 2004] argue that based on simulation results, in practice
a peer only needs to check for cycles with up to five peers.
Each peer uses a data structure called request tree to check for potential
request-cycles. For example, as we can see in Figure 5.10, a peer A decides to
entertain a request for file object o 2 because A finds that peer P 9 possesses
an object that is needed by A. Based on this checking mechanism, the in-