Distributed Reputation Systems for Internet-based Peer-to-Peer Systems and Mobile Ad-Hoc Networks
by Jochen Mundinger, Sonja Buchegger and Jean-Yves Le Boudec
Reputation systems are widely and successfully used in centralized scenarios. Will they work equally well, however, in decentralized scenarios such as Internet-based peer-to-peer systems and mobile ad hoc networks?
Reputation and recommender systems are widely used to provide a basis for the choice of transaction items and partners in online scenarios. They have proven useful in online auctioning systems such as eBay or online book stores such as Amazon, and can be viewed as a substitute for the word-of-mouth mechanisms observed in offline personal encounters.
As a result, it has recently been proposed that reputation systems be extended to decentralized and self-organized systems such as Internet-based peer-to-peer systems and mobile ad-hoc networks. The need here is predominantly to provide incentives for cooperation and to protect the network from node misbehaviour. However, reputation systems need to be distributed in decentralized scenarios and their potentially complex behaviour is not yet fully understood. This understanding is necessary to investigate whether distributed reputation systems might prove as useful as their counterparts for centralized systems. In a collaborative effort started in 2004 between EPFL, SIMS and the Statslab, we are therefore analysing the behavior of distributed reputation systems and evaluating whether and how they can best be used.
We have developed a reputation system to detect, discourage and stop node misbehaviour in Internet-based peer-to-peer systems and mobile ad hoc networks. We proposed a protocol called CONFIDANT (Cooperation Of Nodes — Fairness In Dynamic Ad hoc NeTworks) to cope with misbehaviour. Detection is based both on first-hand observation and on second-hand information provided by other nodes.
To be useful, reputation systems need to be reliable and robust against liars. They can, however, be tricked by the spread of false reputation ratings. On the other hand, simple solutions such as exclusively relying on one's own direct observations do not make use of all the information available.
Our fully distributed reputation system is based on a modified Bayesian estimation procedure and can cope with false information so as to effectively use second-hand information. Each node maintains a reputation rating and a trust rating for all other nodes it cares about. Reputation ratings capture the quality of the behaviour of a node as an actor in the network performing routing and forwarding tasks. From time to time reputation information is exchanged with others. However, second-hand information is only accepted if it is compatible with the current reputation rating or comes from a trusted node. To decide whether it is compatible, we introduce a simple mechanism called the deviation test. If the received estimation of misbehaviour deviates more than a threshold value from the current one, it is rejected, otherwise it is accepted. The trust rating is updated each time a deviation test has been performed, meaning compatible nodes are thus more trusted.
We use simulation to evaluate and demonstrate the performance. We found that CONFIDANT can keep the network performance high even when up to half of the network population misbehaves. We showed that our approach of using second-hand information significantly speeds up the detection of misbehaving nodes while keeping the number of false positives and negatives negligibly low.
Simulation results also suggest that the deviation test performs nearly as well on its own without the trust component. We have therefore analysed it in more detail and in a more general context. We introduced a mathematical model for a distributed reputation system based on the deviation test. We showed that it exhibits a phase transition behaviour, ie critical parameter values exist, below which liars have no impact and above which liars do have a certain impact and corrupt the reputation system. The critical values are obtained via a mean-field approach and are confirmed by direct computation as well as simulation. We thus give guidelines for a good choice of parameters. We also provide insight into a fundamental design question of such systems, namely whether or not direct observations only should be passed on as second-hand information.
Our current focus is on combining our simulation-based approach with the analytical approach. In particular, we are applying the insights gained by the analysis to find and zoom in on relevant parts of the experiment space. We are interested in seeing whether and how the phase transition effects observed in the analytical work carry through to our simulations of a more complex system, such as a mobile ad hoc network implemented in GloMoSim. Based on our analytical results, we now know what sort of behaviour we need to look for in the simulations. This will then enable us to see how the guidelines for a good choice of parameters from the analytical approach translate into a good choice of parameters for the more realistic system. We thereby optimize the performance of the distributed reputation system.
In conclusion, we provide a methodology to identify potential sweet spots and irregular behaviour of complex distributed reputation systems in decentralized self-organized systems. We expect to complete the combination of the two approaches by the end of the year.
Links:
http://lcawww.epfl.ch/salem/IP4Web/ImmuneNetworking.htm
http://www.sims.berkeley.edu/~sonja/CONFIDANT.html
http://winet-coop.epfl.ch/
http://icapeople.epfl.ch/leboudec
http://www.statslab.cam.ac.uk/~jm288
Please contact:
Sonja Buchegger, SIMS, UC Berkeley, USA
Tel: +1 510 643 2251
E-mail: sonja
sims.berkeley.edu
Jochen Mundinger, Statistical Laboratory,
University of Cambridge, UK
Tel: +44 1223 337952
E-mail: J.Mundingerstatslab.cam.ac.uk
Jean-Yves Le Boudec,
EPFL-IC-LCA, Switzerland
Tel: +41 21 69 36631
E-mail: jean-yves.leboudecepfl.ch
