About
Pointers and summaries of some related work, with a focus on distributing parts of Tycoon.
Distributed Auctions/Markets
Auctions without Auctioneers: Distributed Auction Protocols
M. Esteva and J. Padget
I refer to this as the dining auctioneers protocol. It's a p2p-like system in which each peer (called an interagent, one for each buyer) is seated around a table. Bids move around in one direction, and nodes either forward on a bid when they receive it, or else they replace an incoming bid with their own. They only replace it if they are supposed to (depending on the type of auction; if it's ascending, they replace it if they bid higher, etc.). They show how this simple scheme can be used for first price/sealed bid, Vickrey's, Dutch, and English auctions.
The downfall is in the efficiency. It takes $\Omega(N)$ for any one of these auctions (and the English auction requires at least 3 full cycles around the table).
It is derived from the LCR leader selection algorithm, and the authors claim that faster, non-O(N) versions of the algorithm can be used. They don't point out how fast folks have gotten it, or whether or not any leader selection algorithm would work for all the types of auctions they consider.
One potential attack they don't discuss is in verifying that the winner of the auction reports the proper bid amount. In the authors' defense, the attack model does not consider selfish interagents, but it is supposed to handle Byzantine- and stop-failures; I don't see how it handles either of these at all.
Also, if interagents were malicious, second price auctions would fail here, as nodes would see the first price, $f$, going around, and could simply bid $f-\epsilon$, so you might as well just do a first-price auction.
Here's an idea to remedy the problem of winning interagents returning incorrect bid amounts: start the cycles at $k$ different interagents, $I_1...I_k$. Instead of having the highest bidder (in the case of the first-price auction) return to the buyer, have the interagent who first received the bid, $I_j$, return the result to the buyer. The buyer then has $k$ datapoints, with which it could go with the majority, etc. Then just have the interagents sign their bids so that the $I_j$'s can't just modify it.
A Dependable Distributed Auction System: Architecture and an Implementation Framework
P. Ezhilchelvan and G. Morgan
Auctioneers are decentralized, but are apparently assumed to be altruistic. The solution seems to just be an down-up multicast tree; send down info about the auction, gather bids as you go up, with some sort of aggregating function (e.g., max).
There's an interesting notion discussed regarding when to start expanding your auction. Each auctioneer is responsible for their own local market. When performing a bid, the auctioneer only ventures to other markets (to search for higher bidders) if they're not already getting high enough bids. They only consider "high enough" to mean "above the ask price," but one could imagine this being more flexible. On the other hand, it seems like when you have a large bid, then that's when you know you in fact *can* cover the cost to venture out to other markets: "I'm already guaranteed X, so I can spend a little of this profit to shop around, because apparently the demand is real high."
KARMA: A Secure Economic Framework for Peer-to-Peer Resource Sharing
V. Vishnumurthy and S. Chandrakumar and E.G. Sirer
DHT stores nodes' balances (currency is called karma). The key of the DHT is the node ID's. Uses the example of file sharing. When A gets a file from B, B encrypts it and the two peers use the 'Certified Mail Scheme' to trade the encryption key (from B) for a receipt (from A), so that B can be sure to get its money.
To handle nodes leaving and joining the system, there is a correction factor for inflation and deflation. It's a simple multiplication, but no numbers are given to show what this really means to the value of this currency.
There are a few other specifics in the paper pertaining to some more specific engineering details.
Overall, I have a problem with the notion of using the node ID's as the key; if a node can keep generating IDs, then it effectively has an unlimited budget. Of course, this could be modified in an orthogonal way (e.g., also have a reputation system), but that seems to defeat the purpose.
They punt on the problem of self-interested participants, saying that they can "compensate [participants] for taking part in transactions by awarding them with a small amount of karma." But who authorizes this? This opens the door for a very easy, very profitable collusion, especially given that a node can have Sybils (albeit, they can only enter the system at a constrained rate).
More later.
Distributed/P2P Systems
Sub-2-Sub: Self-Organizing Content-Based Publish Subscribe for Dynamic Large Scale Collaborative Networks
S. Voulgaris and E. Riviere and A. Kermarrec and M. van Steen
A pub/sub system that focuses on content-based searches (participants can subscribe to ranges of data) as opposed to topic-based searches (can only subscribe to a single-valued key). This is tough because range searches are generally tough in a DHT-like environment.
Rather than go structured, they stay unstructured, letting the subscribers use gossip to cluster their interests. Specifically, if a subscriber's range (i.e., interests) overlap with another's, then they will be clustered together. Everyone starts off knowing only a few random nodes, but these epidemic algorithms converge quickly (roughly in a logarithmic number of rounds).
Within a cluster, subscribers form some structure by which they can broadcast (in the paper, it's a ring with some additional random links). This way, a publisher need only find one of them, send them a message, and they'll broadcast amongst themselves. Finding a node from the cluster is done with a standard greedy, random walk; as long as nodes maintain some random long range links in addition to information about their nearby (similarly-interested) neighbors, this should happen quickly (depends on the number of links everyone stores).
Resilient Multicast Using Overlays
S. Banerjee and S. Lee and B. Bhattacharjee and A. Srinivasan
A very simple heuristic that can make just about any multicast system much more resilient to node and link stop failures.
In addition to the links in the multicast system (in the paper, they build off of the NICE multicast tree), each node maintains a very small number of random links to other peers. When a peer receives a packet, it sends it on the random links only with some small probability.
The paper gives both theoretical and experimental results that show that with even just a little bit of this extra work at each peer, data delivery rates can be nearly 100% with even high churn.
The paper also talks about some reactive measures (whereas the random transmissions on random links are proactive).
Customizable Routing with Declarative Overlays
More later
