Incentives Engineering für strukturierte P2P-Systeme
Final Report Abstract
Strukturierte Peer-to-Peer-Systeme (P2P-Systeme) sind verteilte, Koordinator-freie Systeme zum performanten Zugriff auf (Schlüssel, Wert)-Paare. Ausgangsfrage des Projektes ist, ob die Teilnehmer sich kooperativ verhalten und Netzwerkstrukturen bilden, die zu einer effizienten Anfragebearbeitung führen. Operationale P2P-Systeme, bei denen es sich aber um unstrukturierte P2P-Systeme handelt, zeigen, dass sich viele Teilnehmer unkooperativ verhalten: Sie erbringen keine Leistungen, konsumieren aber Leistungen anderer Teilnehmer. Ziel ist es, Strategien und Mechanismen zu entwickeln, die effizientes Verhalten belohnen und unkooperatives Verhalten unattraktiv werden lassen. Das Projekt ist u. a. deshalb herausfordernd, weil das Weiterleiten von Anfragen gemäß der Struktur des Netzes erfolgt. Dies führt zu Abhängigkeiten zwischen den Strategien der Teilnehmer und der Netzwerkstruktur. Da ohne eine globale Sicht auf das System prinzipiell jeder Knoten in einer Weiterleitungskette für den Verlust einer Anfrage verantwortlich sein kann, ist es schwierig, unkooperative Teilnehmer zu lokalisieren. Neue Herausforderungen in verteilten Systemen bestehen nicht nur in der Quantität der Kooperation, sondern vor allem in ihrer Qualität. Neben der Frage, ob kooperiert wird, wird zunehmend bedeutender, wie kooperiert wird. Dies wird beispielhaft an der Qualität des Vertrauensverhältnisses zwischen den Knoten untersucht und hier im Besonderen anhand des Umgangs mit persönlichen Daten. Diese eignen sich besonders, da Teilnehmer eine genaue Vorstellung darüber haben, welche ihrer personenbezogenen Daten sie mit welchen anderen Teilnehmern teilen möchten. In diesem Kontext sollte ein strukturiertes P2P-System daher die Kooperation zwischen Teilnehmern fördern, die den Austausch personenbezogener Daten untereinander wünschen. Sind Daten einmal ausgetauscht, ist es für einen Teilnehmer schwierig, zu evaluieren, ob weiterhin in seinem Sinne mit den Daten verfahren wird. Dies ergibt sich einerseits aus der Komplexität und der Vielzahl gesetzlicher Vorschriften, die den Umgang mit Daten regeln, andererseits aus der Vielzahl von Technologien, die personenbezogene Daten sammeln und verarbeiten. Es ist daher zu untersuchen, ob Teilnehmer qualitativ hochwertige Beurteilungen darüber austauschen, ob eine datenschutzkonforme Verarbeitung ihrer Informationen stattfindet. Aus dem Projekt und seinen Arbeitpaketen sind die folgenden Ergebnisse hervorgegangen: (1) In diesem Projekt durchgeführte verhaltensökonomische Experimente über die Anfragebearbeitung menschlicher Teilnehmer in verteilten Systemen zeigen, dass Teilnehmer Schwellenwert-Strategien nutzen. D.h. sie kooperieren nur mit Kontakten, die einen bestimmten Anteil ihrer Anfragen bearbeiten, und defektieren sonst. Dies erhöht den Kooperationsgrad im System. Feedback, d. h. ausgetauschte Information über den Kooperationsgrad Dritter, ist für diese Strategie nicht von Bedeutung. (2) Eine Analyse der Bedeutung von Feedback kommt zu dem Schluss, dass Feedback keine Voraussetzung für kooperatives Verhalten ist. Schwellenwert-Strategien und lang andauernde Kontaktverbindungen sowie die Konkurrenz zwischen Kontakten sind ebenfalls Anreize für kooperatives Verhalten und benötigen keinen zusätzlichen Informationsaustausch. (3) Kontakte, die zusätzlich zu den vom System vorgegebenen gewählt werden, verringern die Weiterleitungslast im System. In bestimmten Situationen lohnt es sich jedoch für einen Teilnehmer, sich nur gering zu vernetzen. Die Folge ist eine ineffiziente Netzwerkstruktur. Teil dieser Arbeit ist die Entwicklung einer Strategie – der Kontakt-für-Kontakt (C4C) Strategie – die zu effizienteren Netzwerkstrukturen führt: Ein Peer lässt Kontakte, die selbst nicht hinreichend vernetzt sind, nicht oder nur teilweise von den eigenen zusätzlichen Kontakten profitieren. Hinreichend vernetzte Kontakte hingegen können von allen zusätzlichen Kontakten vollständig profitieren. Dadurch entsteht ein Anreiz zur Vernetzung. (4) Neben dem Kooperationsgrad und der Vernetzung der Teilnehmer wird ein System durch die Dynamik der Strategien beeinflusst. In der Dynamik von Strategien in verteilten Systemen entstehen zwei Gleichgewichte: ein ineffizientes und ein effizientes. Im ersten kooperieren die Teilnehmer nicht, im zweiten kooperieren sie. Auf dynamische Veränderungen können Teilnehmer mit Strategieanpassungen reagieren, d.h. durch Self-Tuning. Self-Tuning der Teilnehmer führt zu angepassten Schwellenwert-Strategien und zu einer Vernetzung, die nicht optimal ist. Insbesondere wählen die Teilnehmer über den Adressraum gleichverteilte zusätzliche Kontakte. Dies ist zwar aus der Sicht des einzelnen Teilnehmers optimal, jedoch nicht aus der Sicht des Gesamtsystems. In diesem Projekt wird daher eine Strategie – die sogenannte Drop-Slow-Contacts (DSC) Strategie – vorgeschlagen, die zu einer aus globaler Sicht optimalen Netzwerkstruktur führt: Teilnehmer wählen zusätzliche Kontakte anhand ihres Kooperationsgrades und anhand der Zeit, die diese benötigen, Anfragen zu bearbeiten. (5) Die Verallgemeinerung auf eine Netzwerkstruktur mit initialer Ringstruktur zeigt, dass die in der Analyse von n-dimensionalen Grid-Strukturen erlangten Ergebnisse mit denen in einer Ring-Struktur vergleichbar sind. (6) Im Web-2.0-Ansatz kollaborativer Beschreibungen von Datenschutzpräferenzen sind beliebige Netzwerkstrukturen möglich und es findet ein Austausch von qualitativ hochwertigen Informationen statt: Teilnehmer können damit evaluieren, ob ein anderer Teilnehmer mit ihren Datenschutzpräferenzen konform geht. Teilnehmer tauschen qualitativ hochwertige Beiträge aus. Quantitativ benutzen sie aber das System auf eine ähnliche Weise wie herkömmliche Web-2.0-Ansätze: Die Häufigkeit der Beitragserstellung einer Exponentialverteilung. Es gibt wenige Benutzer, die sehr viele, und viele Benutzer, die eher wenige Beiträge erstellen. (7) Zur Kontrolle darüber, welche Benutzer Zugriff auf welche Inhalte haben, wurde ein System entwickelt, das nach einem Anonymitätsmaß Garantien darüber liefert, welche Informationen unbefugte Dritte mit speziellem Hintergrundwissen für Attacken schlimmstenfalls erhalten. Ein derart sicheres System darf die Performanz der Anfragebearbeitung nicht negativ beeinflussen. Dies wurde im Design des Mechanismus berücksichtigt. Das Verständnis von Strategien in P2P-Systemen kann genutzt werden, um Anwendungen, die auf der Anfragebearbeitung in P2P-Systemen oder auf Sozialer Suche in Sozialen Netzwerken beruhen, besser zu verstehen beziehungsweise zu beeinflussen. Beispiele sind Portale zur Sozialen Suche, Anwendungen des Web 2.0 oder Anwendungen in Soziale- Netzwerke-Plattformen. Die Entwickler solcher Anwendungen müssen berücksichtigen, dass sie kein Verhalten dauerhaft vorgeben können, wenn dieses nicht im Interesse des einzelnen Teilnehmers liegt. Systementwickler können die Ergebnisse dieses Projektes, z. B. Schwellenwert-Strategien oder Kontaktwahl zur Steigerung des Kooperationsgrades sowie die C4C- oder die DSC-Strategie zur Verbesserung der Netzwerkstruktur, nutzen, um das Gemeinwohl bis hin zur Effizienz zu steigern. Eine breite Verwertbarkeit der Ergebnisse des Projektes ist möglich, da die Grundannahmen – verteiltes System, autonome Knoten, endogene Vernetzung – auf viele reale Systeme zutreffen.
Publications
- "Indirect Partner Interaction in P2P Networks - Stimulating Cooperation by Means of Structure", Proceedings of the ACM Conference on Electronic Commerce (ACM EC '07), San Diego, California, USA, 2007
Stephan Schosser, Klemens Böhm und Bodo Vogt
- "The Dangers of Poorly Connected Peers in Structured P2P Networks and a Solution Based on Incentives", In: Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence (IEEE/WIC/ACM WI '07), Silicon Valley, USA, 2007
Björn-Oliver Hartmann, Klemens Böhm, Andranik Khachatryan und Stephan Schosser
- Dissertation "Strategische Analyse von Anreizmechanismen in strukturierten Peer-to-Peer Systemen", Fakultät für Informatik, Institut für Programmstrukturen und Datenorganisation, Universität Karlsruhe (TH), 2008
Stephan Schosser
- "Incentivizing connectivity in structured Peer-to-Peer systems". In: Web Intelligence and Agent Systems An International Journal, IOS Press, vol.8, no.2, pp. 123-147, 2010
Björn-Oliver Hartmann, Klemens Böhm, Andranik Khachatryan, Stephan Schosser und Bodo Vogt
- "Towards Efficient Equilibria of Combinations of Network-Formation and Interaction Strategies". In: Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology, Toronto, 2010
Björn-Oliver Hartmann und Klemens Böhm
- “Privacy-Aware Folksonomies”. In: “Proceedings of the 14th European Conference on Research and Advanced Technology for Digital Libraries”, 2010
Clemens Heidinger, Erik Buchmann, Matthias Huber, Klemens Böhm und Jörn Müller-Quade
