• search hit 10 of 70
Back to Result List

Achieving Collaboration In Distributed Systems Deployed Over Selfish Peers - An Illustrative Case Study With Publish/Subscribe

Erreichen der Kooperation von egoistischen Peers in in verteilten Systemen - Eine Studie mit Publish/Subscribe

  • Up to a few years ago, the typical operation of a distributed architecture was modelled as the enactment of a collaborative protocol by networked nodes. In this context, all nodes were under the system designer’s control, faithfully executing the programmed behaviour. However, today’s networks are often characterized by a free aggregation of nodes. Thus, the possibility increases that a selfish party operates a node, which may violate the collaborative protocol in order to increase a personal benefit. If such violations differ from the system goals they can even be considered as attack. Current fault-tolerance techniques may weaken the harmful impact to some degree but they cannot necessarily prevent them. Furthermore, the several architectures differ in their fault-tolerance capabilities. This emphasizes the need for a systematic approach to achieve collaboration in distributed systems. In this PhD thesis we consider the problem of attaining a targeted level of collaboration in a distributed architecture deployed over rationalUp to a few years ago, the typical operation of a distributed architecture was modelled as the enactment of a collaborative protocol by networked nodes. In this context, all nodes were under the system designer’s control, faithfully executing the programmed behaviour. However, today’s networks are often characterized by a free aggregation of nodes. Thus, the possibility increases that a selfish party operates a node, which may violate the collaborative protocol in order to increase a personal benefit. If such violations differ from the system goals they can even be considered as attack. Current fault-tolerance techniques may weaken the harmful impact to some degree but they cannot necessarily prevent them. Furthermore, the several architectures differ in their fault-tolerance capabilities. This emphasizes the need for a systematic approach to achieve collaboration in distributed systems. In this PhD thesis we consider the problem of attaining a targeted level of collaboration in a distributed architecture deployed over rational selfish-driven nodes, which have interest in deviating from the communication protocol to increase a personal benefit. In order to reach this goal and to cover a broad spectrum of systems, we do not modify the architecture or communication protocol itself. Instead, we add a monitoring logic to inspect a node’s behaviour in terms of the correct interaction with the system. With this approach, the system designer needs to contrast several aspects such as the specific environmental circumstances, the inspection effort or the node’s individual preferences. Furthermore, he should consider the fact that each agent could be aware of the other agents’ preferences and selfishness, and perform strategic choices consequently. The natural frame for modelling such complex, interdependent and possibly interactive decision landscape is Game Theory (GT). In this context, the monitoring setup proposed in this thesis corresponds to a class of GT models known as Inspection Games (IG). Such games were introduced 1962 in their simplest formulation by Dresher in the context of non-proliferation treatises and arm control. They model the general situation where one inspector verifies through inspections the correct behaviour of another party, called inspectee. However, inspections are costly and the inspector’s resources are limited. Hence, a complete surveillance is not possible and an inspector will try to minimize the inspections. Finally, a game strategy combination (violating/inspecting or not) that is considered optimal by the parties represents a Nash equilibrium for the game. In this thesis, the initial IG model is enriched by the possibility of false negatives, i.e. the probability that a violation is not detected during an inspection. Both the initial and the enriched model remain abstract and can thus easily find interdisciplinary application. However, as solution approach in this thesis considering the context of distributed systems, it models the network participants’ strategy choice. As outcome, the IG model enables to calculate system parameters in order to shift the Nash equilibrium to the desired target collaboration. The approach is designed as framework. It can be therefore applied to any architecture considering, any selfish goal and any reliability technique. For sake of concreteness, we will discuss the IG approach by means of the illustrative case of a Publish/Subscribe (pub/sub) architecture. In this way messages over the communication infrastructure will have a specific associated semantics. The Inspection Game approach of this thesis secures the whole collaborative protocol in order to attain a correctly working system up to a specific degree (in the sense of collaboration). This represents a completely new way in terms of reliability mechanisms. Hence, this thesis can be considered as fundamental research. In order to enable a broad application, the generality of this approach is supported by further contributions. This is among others the software library RCourse for practical robustness evaluations of overlay networks and a simulation environment for further research of the abstract IG model. All developments will finally be published as open source software.show moreshow less
  • Bis vor ein paar Jahren konnten verteilte Systeme durch die Anwendung eines gemeinsamen kollaborativen Protokolls realisiert werden. Die Netzwerkknoten (Software/Hardware eines Systemteilnehmers) standen unter der vollständigen Kontrolle eines Systemadministrators. Heutige Netzwerke wie z.B. Peer-to-Peer (P2P) Systeme bilden sich jedoch häufig aus einem dynamischen und freien Zusammenschluss von Netzwerkteilnehmern. Dabei steigt die Wahrscheinlichkeit deutlich, dass ein Knoten von egoistischen Individuen betrieben wird, welche bewusst das Protokoll verletzen um ein persönliches Ziel zu verfolgen. Ein Beispiel ist die Verringerung des eigenen Ressourcen-Verbrauchs durch die Nicht-Weiterleitung von Nachrichten anderer Netzwerkteilnehmer. Ein solches Verhalten kann nicht nur als schädlich sondern auch als Angriff betrachtet werden. Die Fehlertoleranz aktueller Systeme kann die negativen Auswirkungen abschwächen jedoch nicht vollständig verhindern. Weiterhin unterscheiden sich die Systeme in diesem Punkt zum Teil dramatisch. DiesBis vor ein paar Jahren konnten verteilte Systeme durch die Anwendung eines gemeinsamen kollaborativen Protokolls realisiert werden. Die Netzwerkknoten (Software/Hardware eines Systemteilnehmers) standen unter der vollständigen Kontrolle eines Systemadministrators. Heutige Netzwerke wie z.B. Peer-to-Peer (P2P) Systeme bilden sich jedoch häufig aus einem dynamischen und freien Zusammenschluss von Netzwerkteilnehmern. Dabei steigt die Wahrscheinlichkeit deutlich, dass ein Knoten von egoistischen Individuen betrieben wird, welche bewusst das Protokoll verletzen um ein persönliches Ziel zu verfolgen. Ein Beispiel ist die Verringerung des eigenen Ressourcen-Verbrauchs durch die Nicht-Weiterleitung von Nachrichten anderer Netzwerkteilnehmer. Ein solches Verhalten kann nicht nur als schädlich sondern auch als Angriff betrachtet werden. Die Fehlertoleranz aktueller Systeme kann die negativen Auswirkungen abschwächen jedoch nicht vollständig verhindern. Weiterhin unterscheiden sich die Systeme in diesem Punkt zum Teil dramatisch. Dies verdeutlicht den Bedarf von Systemen, die aktiv eine Befolgung kollaborativen Protokolls aufrechterhalten und damit die korrekte Funktion eines verteilten Systems. In dieser Dissertation betrachten wir daher das Problem ein bestimmtes Kollaborationsniveau in einem verteilten System zu erreichen, in dem egoistische Knoten agieren. Für eine möglichst hohe Anwendbarkeit wird dazu weder die Architektur noch das kollaborative Protokoll selbst verändert. Stattdessen überwacht ein Monitoring-Ansatz das Verhalten der einzelnen Netzwerkteilnehmer und induziert bei Bedarf Kooperationsanreize. Aufgrund begrenzter Ressourcen erfolgt dies nicht für alle Operationen sondern nur stichprobenartig in Form von Inspektionen. Mit dem Monitoring-Ansatz muss ein Systemdesigner diverse Aspekte abwägen wie zum Beispiel den aktuellen Systemzustand, Inspektionsaufwand oder individuelle Ziele eines egoistischen Knotens. Dies führt zu einer komplexen, gegenseitigen und möglicherweise interaktiven Entscheidungslandschaft für die Monitoring-Logik und Knoten. Ein typisches Werkzeug zur Modellierung solcher Situationen ist Spieltheorie. In der Tat entspricht der Monitoring-Ansatz einer Klasse der Spieltheorie, Inspection Games (IG), erstmals vorgestellt 1962 von Dresher im Kontext der Einhaltung von Rüstungsabkommen durch Inspektionen an Grenzposten. IGs modellieren die generelle Situation wo ein inspector durch Inspektionen das korrekte Verhalten eines anderen Individuums, dem inspectee, überprüft, welches vom vorgegebenen Protokoll abweichen möchte um einen individuellen Nutzen zu erhöhen. Inspektionen sind jedoch aufwändig; der Inspektor versucht daher dessen Anzahl zu reduzieren. Eine für die Individuen optimale Strategiekombination (Abweichen bzw. Inspizieren oder nicht) repräsentiert schließlich das Nash Equilibrium. In der Dissertation wurde der IG Ansatz als Lösungsvorschlag für das gegebene Problem auf verteilte Systeme adaptiert. Dazu wurde der initiale IG Modell zunächst durch false negatives erweitert, d.h. die Möglichkeit, dass Protokollverstöße während einer Inspektion nicht entdeckt werden. Es wurden weiterhin Generalisierungen für mehrere Individuen sowie deren Lösungen (Nash Equilibria) erarbeitet um als Basis für weitere (auch interdisziplinäre) Arbeiten zu dienen. Bei der konkreten Adaption auf verteilte Systeme erlaubt der IG Ansatz die Modellierung des Kollaborationsverhaltens, d.h. die Strategiewahl der einzelnen Individuen (Protokollverletzung bzw. Inspektion oder nicht). Als Ergebnis ermöglicht der IG Ansatz die Berechnung von Systemparametern um das Nash Equilibrium zur einer Strategiekombination zu verschieben die dem anvisierten Kooperationsniveau entspricht. Der gesamte Ansatz ist als Framework konzipiert. Er kann daher individuellen Bedürfnissen angepasst werden; dies umfasst insbesondere die Systemarchitektur, das individuelle Ziel und verwendete Techniken. Die gesamte Thematik wird in der Dissertation anhand eines konkreten Anwendungsbeispiels mit Publish/Subscribe Systemen diskutiert. Der Inspection Game Ansatz der Dissertation hat das Ziel der Absicherung des gesamten Kollaborations-protokolls selbst. Dies ist ein vollständig neues Konzept zum Erreichen der Zuverlässigkeit und der korrekten Funktion eines verteilten Systems (im Sinne der Kollaboration). Es kann daher als Grundlagenforschung betrachtet werden und erlaubt eine Vielzahl fortführender Forschungsarbeiten. Diese werden durch weitere Beiträge der Dissertation sollen unterstützt. Beispiele sind unter anderem die Softwarebibliothek RCourse für simulative Evaluierungen der Robustheit von verteilten Systemen sowie eine Simulationsumgebung für Untersuchungen des IG Modells. Alle Entwicklungen werden weiterhin als Open Source Software veröffentlicht.show moreshow less

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Tobias Rene Mayer
URN:urn:nbn:de:bvb:739-opus-27118
Advisor:Harald Kosch
Document Type:Doctoral Thesis
Language:English
Year of Completion:2013
Date of Publication (online):2013/11/05
Publishing Institution:Universität Passau
Granting Institution:Universität Passau, Fakultät für Informatik und Mathematik
Date of final exam:2013/09/24
Release Date:2013/11/05
Tag:Inspection Games
game theory; inspection games; modeling of distributed systems; reliability
GND Keyword:Zuverlässigkeit; Verfügbarkeit; Sicherheit; Netzwerkverwaltung; Netzwerkanalyse; Modellierung; Spieltheorie
Institutes:Fakultät für Informatik und Mathematik / Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik
CCS-Classification:C. Computer Systems Organization / C.0 GENERAL
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
open_access (DINI-Set):open_access
Licence (German):License LogoStandardbedingung laut Einverständniserklärung