Reputazione e P2P: un po' di bibliografia

Teoria dei Giochi

• Prajit K. Dutta; Strategies and Games - Theory and Practice. MIT press, 1999. ISBN 0262041693.

  Un libro ben scritto e piuttosto facile da leggere sulla Teoria dei Giochi.

• Robert Axelrod; The Evolution of Cooperation. Basic Books, 1984. ISBN 0465021212.

  Insorgenza della cooperazione attraverso il dilemma del prigioniero iterato. Tradotto anche in italiano.

• Martin A. Nowak, Karl Sigmund; Evolution of indirect reciprocity by image scoring. Nature 393, June 1998.

  L'immagine è vicino al concetto di "reputazione" come lo intendiamo noi. Vengono usati giochi evoluzionistici.

• Eric J. Friedman, Paul Resnick; The Social Cost of Cheap Pseudonyms. Journal of Economics & Management Strategy, 2001.

  Nelle applicazioni in cui gli utenti vengono identificati per "pseudonimi" (es.: login, userid), ed č possibile registrarne di nuovi in maniera arbitraria, gli utenti che si sono meritati una cattiva reputazione possono eliminarla cambiando pseudonimo e ripartendo da zero. Si mostra che la cooperazione puň comunque venire raggiunta, facendo pagare lo scotto di questa tecnica ai nuovi arrivati, che vengono trattati male finché non si costruiscono una reputazione positiva.

Sociologia

• Diego Gambetta; Can We Trust Trust? Trust: Making and Breaking Cooperative Relations, Basil Blackwell, 1988.

  Una discussione ad alto livello dei concetti di fiducia e reputazione.

WWW

• Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd; The PageRank Citation Ranking: Bringing Order to the Web. Stanford Digital Library, 1999.

  L'articolo originale che spiega il funzionamento dell'algoritmo usato da Google.

• Zoltán Gyöngyi, Hector Garcia-Molina, Jan Pedersen; Combating Web Spam with TrustRank. Proceedings of the 30th International Conference on Very Large Databases, 2004.

  Usa un oracolo umano e una variazione sul tema di PageRank per identificare le pagine "spam", cioé quelle fatte per ingannare i motori di ricerca ed alzare il rating. Interessante IMHO il concetto di "trust dampening": un fattore β che attenua la fiducia ad ogni passaggio.

Reti small-world

• R. Levien; Advogato's Trust Metric. 2000.

  Advogato č una rete sociale di sostenitori del software libero. La metrica di fiducia sembra una combinazione del MaxFlow proposto da Feldman e altri e di EigenTrust. La cosa divertente č che quegli articoli sono di 3-4 anni dopo.

• Albert-László Barabási; Linked. The New Science of Networks. Perseus, 2002.

  Un libro estremamente leggibile ed affascinante sugli sviluppi nello studio delle reti scale-free, in informatica come in biologia e sociologia. Lo consiglio spassionatamente.

• R. Milo, N. Kashtan, S. Itkovitz, M. E. J. Newman, U. Alon; On the uniform generation of random graphs with prescribed degree sequences. Preprint, 2004.

  Algoritmi per generare reti random, fissati i degree dei nodi.

• Réka Albert, Albert-László Barabási; Statistical mechanics of complex networks. Reviews of Modern Physics, vol. 74, Jan. 2002.

  Un articolo piuttosto complesso con molti risultati su reti random, scale-free, small-world.

• Soon-Hyung Yook, Hawoong Jeong, Albert-László Barabási; Modeling the Internet's large-scale topology. Physical Review E 66, 06614 (2002).

  In questo articolo viene modellata la topologia di Internet, con preferential attachment dipendente da grado dei nodi e distanza fisica tra di essi.

• M. E. J. Newman; The Structure and Function of Complex Networks. SIAM Review, Vol 45, No. 2, pp. 167-256.

  Un'ottima (e lunga) review sulle reti complesse. Completa e chiara.

P2P

• Il sistema di crediti in eDonkey

• Bram Cohen, Incentives Build Robustness in BitTorrent. Workshop on Economics of Peer-to-Peer Systems, 2003.

  I meccanismi (ispirati a Tit-for-tat) di BitTorrent.

• Sepandar D. Kamvar, Mario T. Schlosser, Hector Garcia-Molina; The EigenTrust Algorithm for Reputation Management in P2P Networks. Proceedings of the Twelfth International World Wide Web Conference, 2003.

  Implementazione distribuita di PageRank per reputazione su reti P2P.

• Michal Feldman, Kevin Lai, Ion Stoica, John Chuang; Robust Incentive Techniques for Peer-to-Peer Networks. ACM Electronic Commerce, 2004.

  Dilemma del prigioniero iterato, giochi evolutivi, reputazione soggettiva. L'algoritmo proposto è MaxFlow per valutare la fiducia, ma manca un'implementazione distribuita scalabile: i peer dovrebbero conoscere tutto il grafo dei rapporti di fiducia.

• Li Xiong, Ling Liu; PeerTrust: Supporting Reputation-Based Trust for Peer-to-Peer Electronic Communities. IEEE Transactions on Knowledge and Data Engineering, 2004.

  Si parte da un concetto simile a EigenTrust e si aggiungono altri accorgimenti; interessante notare il concetto di similarità delle valutazioni come criterio per valutare l'affidabilità delle valutazioni date da un peer in particolare. Sfortunatamente, questo criterio mi sembra poco applicabile in reti di dimensioni dell'ordine di milioni di nodi.

• Q. Sun, H. Garcia-Molina; Slic: A selfish link-based incentive mechanism for unstructured peer-to-peer networks. Technical report, Stanford University.

  Un protocollo semplice per la creazione di incentivi all'interno di reti non strutturate (e.g.: gnutella, anche Freenet). Si propone di fornire un servizio migliore ai vicini che sono in grado di soddisfare la maggior quantitŕ di richieste inoltrate.

• A. Marcozzi, D. Hales, G. Jesi, S. Arteconi, O. Babaoglu; Tag-Based Cooperation in Peer-to-Peer Networks with Newscast. University of Bologna, Dept. of Computer Science, May 2005, Technical Report UBLCS-2005-15.

  Un'idea differente: usare dei "tag" per rappresentare l'aderenza ad un "gruppo sociale". Questo permette l'emersione spontanea di incentivi alla cooperazione. Implementato tramite rewiring (cambio dei link sulla rete) in reti non strutturate. Non so se questo possa funzionare in una rete strutturata tipo DHT.

• John R. Douceur; The Sybil Attack. IPTPS, 2002.

  La creazione a basso costo di nuove identitŕ rende possibile un attacco dovuto al fatto che una parte rilevante dei nodi di una rete P2P sono "falsi".

• Alice Cheng, Eric Friedman; Sybilproof Reputation Mechanisms. Third Workshop on Economics of Peer-to-Peer Systems, Philadelphia, PA. August 22, 2005.

  Studio teorico sulla resistenza all'attacco della sibilla. I punti piů interessanti sono che non esistono sistemi "simmetrici" di reputazione (nei quali, cioé, le valutazioni sono invarianti modulo renaming dei nodi) resistenti all'attacco, e la caratterizzazione di alcuni metodi "soggettivi" (come MaxFlow) resistenti ad esso.

• Oskar Sandberg; Searching in a Small World. Licenciate Thesis, Chalmers University of Technology and Göteborg University.

  Spiega il meccanismo di routing nella nuova versione di Freenet (una "darknet"): i nodi si dispongono in maniera tale da mimare la disposizione su un anello - o analoga topologia multidimensionale; il routing viene fatto sfruttando queste posizioni. Č possibile vedere un video (disponibile anche su Google Video) che spiega come tutto ciň č stato implementato in Freenet.