Agents Tags in Peer-to-Peer Applications
From: From Selfish Nodes to Cooperative Networks - Emergent Link-based incentives in Peer-to-Peer Networks
David Hales, Proceedings of the Fourth International Conference on Peer-to-Peer Computing, 2004
It doesn't come as a great shock to hear that in most peer-to-peer (P2P) systems the majority of users are freeloaders, while a minority shares a great deal of files. This is good news, of course, for the law enforcement world which only has to take out the ringleaders for the whole thing to fall apart. Let's assume that we're talking about entirely legal file sharing from here on in though.
Generally speaking, for a P2P application to be as useful as possible, it should encourage as many as possible to share. Ideally this should be done without having to resort to any centralised server or third party solutions, so as to maintain the greatest benefits from having the most open network possible. One can also assume that everyone wants to act as selfishly as possible individually.
The algorithm the agents use is called SLAC (which as a grad student, I heartily approve of) - Selfish Link and behaviour Adaption to produce Cooperation. Yeah, choosey with the letters. This algorithm doesn't really use tags as such, but is closer in spirit to the ideas suggested in Riolo et al 2001 but which they didn't really look at closely.
Each agent has to choose whether to spend its time answering other queries, or whether to spend its time making queries (and thus getting more responses most likely), there is the same kind of tragedy of the commons situation here. It's optimal for the individual agents not to help others but it's no good if everyone does that.
The agents have links to other agents (as in a P2P situation) in some random fashion to start with, and they ask other agents they have links to whether they will trade with them (or play a game of the Prisoner's Dilemma, the algorithm works either way). The agents gain some utility if they are able to source files from another agent. Every so often each agent will randomly select an agent from the population as a whole and compare their utility with that agent. Whoever has the lower utility drops all of their previous links and adopts a link with each of the other agent’s links, as well as the other agent itself. Importantly, the agent with a lower utility also adopts the strategy of the agent with the higher utility.
Because of this system, it turns out that those that don't ever cooperate have their links leave them for more cooperative groups, and thus suffer from a certain amount of ostracisation. This works well in theory, at least according to the pretty pictures, but I do have some issues with this, many of which they themselves admit require further research (which they may well have done by now, I shall soon check). The reason these are problems is that the idea of this sort of system is that anyone should be able to connect to it with a varying strategy and not control the system too much. If you force people to abide by the rules properly, then fine, but that's not easy!
1. I wonder if falsely reporting utility might be a good idea for an agent. As I think about it, I guess it never is. Either way they will have a link to the agent they compare utilities with, and after that they might as well have a link to the other agents "friends" if they are indeed more cooperative. Likewise it wouldn't be worth underreporting utility. It seems like there would be other ways to cheat the system, but they would be more security than algorithmic issues.
2. How do they choose a node at random from the whole network? Actually I'm not entirely sure how the completely decentralised P2P networks work in this manner; I guess everyone has to connect somewhere. Can anyone else tell me before I get around to learning it myself?
3. While each agent will always want to move into groups which are more eager to share, I'm not sure that for the agent changing their strategy is necessarily a good move when they do so. The authors mention that checking the effect of "whitewashers" like this is important future work. They mention Lai et al 2003 in this respect.
4. Every so often an agent mutates to either change its behaviour or "reset" its links to be to just one random other agent. I guess this could be viewed as being disconnected from the network and reconnecting or something, rather than something an agent does deliberately. Changing strategy could be changing to some new client version, apparently.
5. Why do agents have to draw from the same pool of resources to answer queries as well as make queries? This seems to be creating a different problem because it's one that's more convenient to solve with the technique! Otherwise it's just users being lazy or choosing not to share for a different reason than limited resources, and that isn't a convenient problem to solve with any technique from computer science.
6. They assume that each agent is equally capable of sharing files. This will never be so in a P2P situation, even when everyone does share. They may not have done so in all their tests though, it may have just been for the particular graphs shown. Equally, even if we assume resources for answering and making queries are drawn from the same pool, different agents will have different sized pools depending on computer and connection speeds. This may confuse the issue.
Conclusion: It does seem to be a good incentives mechanism for a P2P application, but I think it still offers a lot of opportunities for exploitation, and is likely to discriminate against even the most cooperative user who just doesn't have a lot to share. But maybe that's fair, depending on how you look at it. It is very nice in that the structure of encouraging sharing is purely emergent from agents being selfish so long as they follow the rules. It's also reasonable to assume that even though at least some will exploit any loopholes in the system, sufficiently many will not, so it will work. The system should certainly cope with a few freeloaders.
Riolo, Cohen, Axelrod - Evolution of Cooperation Without Reciprocity, Nature, 2001
Lai, Feldman, Stoica, Chuang - Incentives for Cooperation in Peer-to-Peer Networks, Workshop on Economics of Peer-to-Peer Systems, 2003
posted by Rowan at
9:22 AM
2 Comments:
I probably shouldn't say much here because I have little to go on beyond Kazaa, but I'll say what I've noticed anyway, because I'm bored.
In answer to 1. False utility: It is possible to falsely report utility to your benefit. I haven't used Kazaa in a long time and I think it doesn't work anymore, but toward the end of my usage period I was finding it increasingly difficult to download working MP3s. Yes, this isn't legel, but bite me. Part of this is because there are deliberately wrecked songs being circulated to make people give up and buy it. I think these tracks are falsely reported as high quality and certainly have false play times. This affects the downloading user. Now as far as sharing users go: Kazaa implemented a practise of prioritising accorinding to how well you play - you have a ranking, starting at 100. If you download a lot then your rating goes down becuase you're using. If then once you have a file base you do a lot of sharing and not a lot of using, your rating goes up, and when upload > download, your rating goes above 100. The maximal rating is 1000. Now there was some loophole in the system, I believe in KazaaLite, which I know nothing about, which allowed users to (I believe) falsely report their rating (utility) as 1000, when all they ever did was download.
The reason this is a problem is that the downloading was prioritised by utility, so if you were a good happy player who shared lots and downloaded a bit, you'd get faster transfer speeds, bigger chunks coming from the broadband users. So if you leeched off the system you could wait hours for a single MP3. So these false 1000's, that let them get really high speeds, sort of made it crappy for everyone else who then couldn't get good speeds even though they were playing nicely.
The key is then how to implement the bit you were talking about that allows cheats to have their connections cut and have to start over.
2. Peer-to-peer networks: It depends on the type of network. I can't be bothered thinking too hard or reading too much, but for a start, look at the basic happy place:
http://en.wikipedia.org/wiki/Peer-to-peer
Basically a p2p network is one which doesn't rely on servers, but where each user acts as a miniserver (I know, you know that). Fine. The trick is, this can be implemented in two ways - your connections can be purely random (in which case your choosing a random person to compare with could be quite hard or easy depending on whether the connections are totally and continuously dynamic or not; OR the other, possibly more useful, implementation, is where you do have one independent server, which tracks the users. Thus your random agent exange could be determined by randomly accessing the lookup table of the address server.
So it's not just a question of how P2P networks work but what type you really are talking about. In the 2nd case all sharing is still done between nodes, but there IS a big brother who knows where you all are.
3. New groups & strategies: You know that your new group is more eager to share because they have a higher utility than where you came from after your random comparison. Thus from your point of view, moving to a group who shares more, and then predominantly downloading, will work very well for you. The only obvious ways to get around this is to have a peer-boot idea, where if your sharing isn't within statistical tolerances of the rest of the group, then you get kicked to find another random comparator or reset links; OR to implement rules on group changes, stating that whenever an agent joins a new group, it's strategy MUST change one way or the other. That could backfire even worse if they go from being a moderate sharer into a higher sharing group and their strategy change goes in the other direction.
4. Resets: Good move, why not? Also a good way to deal with agents unwanted in a group if the rest of a group can vote one out. Very Survivor, I know. But there's no compulsion to vote one out, but should it be proposed and a vote taken, if the majority of the group are annoyed with agent user, then user's links are reset to start over, at random.
5. Resource pools for up and down: I guess this is a question of application. In computer science/networking that probably is the best way to look at it. In a different situation, more like a society sim, it may not be.
6. Ability to share: I guess in terms of studies it's best to assume that absolutely everyone is using a 256k broadband modem and are using it for nothing else but their P2P network. In practise this is not the case, some users are faster, some slower, and some have other demands on their resources (what if you want to share documents AND process SETI@home data?). I guess in this case the analysis would get fiendishly complicated, but I think you'd start by giving the agents tags, or handicaps, relating to their connection speed and peripheral network usage outside the P2P network. Also monitor IPs so that one user couldn't connect multiple times with broadband and get a good handicap because any one connection is small, but capable of being big if the others are all virtually inactive.
I think this is a somewhat different problem to most of the agent society ones you've looked at, so again, figure out what the problem is explicitly before comparing principles and results.
Sorry to talk for so long. Still waiting on a computation to finish!!
:) Mshooqn! :) (I love random character verification)
By
Anonymous, at 10:49 AM
I'll just address a couple of those points:
1. Kazaa is an entirely different system to what I'm talking about here. Also what you're talking about is falsely representing your benefit to the system, not how happy you are with the number of files you've been able to download.
3. I agree that the peer-boot idea is worthwhile in a sense, but the whole point is that there is no controls, and no need for controls like that as it organises itself very efficiently. There also isn't a tangible "group" as such, it just organises itself into something approaching groups, just enough that group selection is encouraged.
By
Rowan, at 2:30 PM
Post a Comment
<< Home