Keywords: Reliability, availability, and security, Network management, Modeling of distributed systems, Game Theory, Inspection Games Zuverlässigkeit, Verfügbarkeit, und Sicherheit, Netzwerkmanagement, Modellierung von Computerarchitekturen, Spieltheorie, Inspection Games Remote Procedure Call SOA Service Oriented Architectures sCRE Simple Comprehensive Reliability Evaluation

Today's networks are often characterized by a free aggregation of independent nodes. Thus, the possibility increases that a selsh party operates a node, which may violate the collaborative protocol in order to increase a personal benet. If such violations dier 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 always prevent them. Furthermore, the several architectures dier in their fault-tolerance capabilities. This emphasizes the need for approaches able to achieve collaboration from selsh nodes 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 selsh nodes. They have interest in deviating from the collaborative protocol to increase a personal benet. In order to cover a broad spectrum of systems, we do not modify the collaborative protocol itself. Instead, we propose to add a monitoring logic to inspect the correctness of a node's behaviour. The designer of the monitoring system is faced with a complex and dynamic situation. He needs to consider aspects such as the specic circumstances (e.g. message trac), the inspection eort or the node's individual preferences. Furthermore, he should consider that each agent could be aware of the other agents' preferences as well as selshness and perform strategic choices consequently. This complex and interdependent setup corresponds to a class of Game Theory (GT) known as Inspection Games (IG). They model the general situation where an inspector veries 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.

In this thesis, the initial IG model is enriched by the possibility that a violation is not detected during an inspection (false negatives). Applied to distributed systems, the IG is used to model the network participants' strategy choice. As outcome, it enables to calculate system parameters to attain the desired collaboration value. The approach is designed as generic framework. It can be therefore applied to any architecture considering any selsh goal and any reliability technique. For the sake of concreteness, we will discuss the IG approach by means of the illustrative case of a Publish/Subscribe architecture.

The IG framework of this thesis secures the whole collaborative protocol by a monitoring approach. This represents a new way in terms of reliability mechanisms. The applicability is furthermore supported by the software library RCourse. Simplifying robustness evaluations of distributed systems, it is suitable for model verication and parameter calibration.

RÉSUMÉ

Les réseaux actuels sont souvent caractérisés par une intégration dynamique de noeuds étrangers. La possibilité qu'une entité dissidente égoïste exploite un noeud augmente alors, ce qui peut constituer une violation du protocole de collaboration en vue d'accroître un avantage personnel. Si de telles violations dièrent des objectifs du système, elles peuvent même être considérées comme une attaque. Si des techniques de tolérance aux fautes existent pour aaiblir l'impact sur le système, celui-ci ne peut pas totalement se prémunir de ce type d'attaque. Cela justie la nécessité d'une approche pour maintenir un degré de collaboration noeuds égoïstes dans les systèmes distribues.

Dans cette thèse, nous considérons le problème d'atteindre un niveau ciblé de collaboration dans une architecture répartie intégrant des noeuds égoïstes, qui ont intérêt à violer le protocole de collaboration pour tirer parti du système. L'architecture et le protocole seront modies le moins possible. Un mécanisme d'inspection de chaque noeud sera mis en place pour décider de la légitimité de ses interactions avec ses voisins. Le concepteur du système d'inspection est confronté avec une situation complexe. Il doit corréler plusieurs aspects tels que les circonstances particulières de l'environnement ou des préférences individuelles du noeud. En outre, il doit tenir compte du fait que les noeuds peuvent connaitre l'état de ses voisins et construire ses décisions en conséquence. La surveillance proposée dans cette thèse correspond à une classe de modèles de la théorie des jeux connus sous le nom « Inspection Game » (IG). Ils modélisent la situation générale où un « inspecteur » vérie par des inspections du comportement correct d'une autre partie, appelée « inspectee ». Toutefois, les inspections sont coûteuses et les ressources de l'inspecteur sont limitées. Par conséquent, une surveillance complète n'est pas envisageable et un inspecteur tentera de minimiser les inspections.

Dans cette thèse, le modèle initial IG est enrichi par la possibilité d'apparition de faux négatifs, c'est à dire la probabilité qu'une violation ne soit pas détectée lors d'une inspection. Appliqué sur des systèmes distribués, cette approche permet de modéliser les choix collaboratifs de chacun des acteurs (violer le protocole ou pas, inspecter ou pas). Comme résultat, le modèle IG retourne les paramètres du système pour atteindre le niveau de collaboration souhaité. L'approche est conçue comme un « framework ». Elle peut donc s'adapter à toutes les architectures et toutes les techniques de abilité. Cette approche IG sera présentée à l'aide d'un exemple concret d'architecture Publish/Subscribe. L'approche du jeu d'inspection de cette thèse pour objectif de sécuriser l'ensemble du protocole de collaboration. Ceci constitue un nouveau concept de mécanisme de abilité. An de permettre une large application, la généralité de cette approche est renforcée par la contribution RCourse. En simpliant les évaluations de la robustesse des systèmes, elle permet la vérication de l'approche IG et le calibrage des paramètres du système.

: Fiabilité, disponibilité et sécurité • Gestion de réseaux • Modélisation des systèmes répartis • Théorie des jeux • Inspection Games ZUSAMMENFASSUNG Heutige Netzwerke entstehen häug durch einen dynamischen Zusammenschluss von Knoten. Dabei steigt die Wahrscheinlichkeit, dass ein Knoten von egoistischen Individuen betrieben wird welche bewusst das Protokoll verletzen um ein persönliches Ziel zu verfolgen. Dieses Verhalten kann nicht nur als schädlich sondern auch als Angri betrachtet werden. Die Fehlertoleranz aktueller Systeme kann die negativen Auswirkungen abschwächen jedoch nicht vollständig verhindern. Aktuelle Systeme unterscheiden sich in diesem Punkt zum Teil dramatisch. Dies verdeutlicht den Bedarf von Systemen, die aktiv eine Befolgung des kollaborativen Protokolls aufrechterhalten und damit die korrekte Funktion eines verteilten Systems.

In dieser Dissertation betrachten wir das Problem ein bestimmtes Kooperationsniveau von egoistischen Knoten eines verteilten Systems zu erreichen. Für eine möglichst hohe Anwendbarkeit wird das System selbst so wenig wie möglich verändert. Stattdessen überwacht ein Monitoring-Ansatz die Korrektheit des Verhaltens der einzelnen Knoten. Der Designer des Monitoring-Systems ist mit einer komplexen und dynamischen Situation konfrontiert. Er muss Aspekte berücksichtigen wie den aktuellen Systemzustand (z.B. Nachrichtenverkehr), 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. Dies entspricht exakt einer Klasse der Spieltheorie: Inspection Games (IG). 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. Aufgrund begrenzter Ressourcen versucht der inspector die Anzahl der Inspektionen zu reduzieren.

In

LIST OF FIGURES

Limiting bandwidth is a realistic issue. The functionality is integrated in the settings of the PP software BitTorrent (left) as well as in the low-budget router D-Link DIR-(right). . . . . . . . . . . Figure .  The gure illustrates a classication from Nielson et al. [], which is used in the thesis. In this context, selsh behaviour is considered as synonym to rational behaviour, assuming further a personal goal that diverges from the system goal(s). . . . . . . . . . . . . . . . . . . Figure .  Graphical overview to the Publish/Subscribe communication paradigm showing the interaction-style (left) and the position in the network stack (right). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  Vision: The objective is a design concept to enable a system deployment over selsh peers to attain a targeted collaboration level. . . . . Figure .  General approach: An inspection target maintains a peer's collaboration proofs. It is controlled by an inspector, who gives collaboration incentives (punishment) in case of detected PoM. The desired collaboration level is reached by an appropriate inspection rate. . . . . . . Figure .  Methodology: The IG is considered as framework for the system design. The application to an illustrative use case shows the utilization in detail and how collaboration is achieved. . . . . . . . . . . . . . . . Figure .  Thematical overview to the main contributions of the thesis . . . . . Figure .  Outline of the relation of approaches suitable to face selsh peers in distributed systems. Note that this distribution outlines only the author's impression of the reviewed works. . . . . . . . . . . . . . . Figure .  Transformation of broker overlays to PP overlays by aggregating interests of clients. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  The two pub/sub algorithms are oppositional in terms of reliability and eciency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .

The Scribe system has a tree-based dissemination style. Two operations are exemplary illustrated for a multicast group: the subscription (left) and the publishing (right). . . . . . . . . . . . . . . . . . . . Figure .  Informed gossiping realizes a deterministic dissemination ring based on the overlay ids. Further random transfers (r-links) improve the dissemination speed. . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  RCourse supports the user in the workow of simulative studies by performing up to all steps after the algorithm development. Each step can be individually adapted (dashed lines). . . . . . . . . . . . . Figure .  RCourse Java library consists of six main classes. . . . . . . . . . . .

The result analysis with R scripts is organized in phases: the analysis scripts are started in phase (I), the result les are processed in phase (II) and pdf result graphs are generated in phase (III). . . . . . Figure .  Three examples show the utilization of RCourse components in the source code. The related code is indicated in blue/italic. . . . . . . . . Figure .  If using the Eclipse IDE for running simulations, Experimentation Scenarios may be dened as presets as shown here for ES.. . . . . . Figure .  Some example graphs are shown for the Scribe [] system, which have been generated with RCourse. This is the (sorted) node stress distribution (upper graph), the distribution of subscription table entries (middle graph) and message loss due to selshness-driven message drops (bottom graph). . . . . . . . . . . . . . . . . . . . . . . . . Figure .  Peersim supports only single-threaded simulations. However, RCourse enables a parallel simulation to some degree and an automated result aggregation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  The graphs show evaluation results of selshness-driven message drops of Scribe (upper graph) and basic gossiping (lower graph). Latter one used a fanout value of . . . . . . . . . . . . . . . . . . . . . Figure .  The extensive form for an IG with one inspector and one inspectee. . Figure .  Inspection Game G(1, 2) in extensive form. . . . . . . . . . . . . . . Figure .  Inspection Game G(2, 1) in extensive form. . . . . . . . . . . . . . . Figure .  The Inspection Game Γ(1, 1) is shown in extensive form. It corresponds to G(1, 1) but is extended by the possibility of false negatives. Figure .  This gure illustrates synchronized (left) and not synchronized (right) inspectors in terms of the inspectee selection. The id space is represented in a two-dimensional way with dots as inspectees. The dashed squares indicate the assignment of id regions to an inspector. . . . . Figure .  This thesis considers for the sake of simplicity a linear dependency between violation opportunities and possible violation benet. However, non-linear relations are generally possible. . . . . . . . . . . . . Figure .  The IG must be adapted to a possibly innite operation of distributed systems. To this end, each of the the operations is mapped to single game and each game is then independently played. The inspection target holds collaboration proofs and is controlled by the inspector. . Figure .

Two possible inspector implementations are illustrated: as individual peers (with possibly multiple inspector instances on the peer) and as network layer at the inspectee's peer. . . . . . . . . . . . . . . . . . . Figure .  Four exemplary inspection architectures are illustrated. . . . . . . . . Figure .  A network layer can be added to the inspectee for maintaining collaboration proofs. It may also monitor system values or impose punishments as collaboration incentive. . . . . . . . . . . . . . . . . . . .

Figure .

Two possibilities for a reactive game mode are shown. The left gure shows an external inspection initiation. Here, an external individual or logic (here a game master) instructs the actual inspector to perform an inspection. The right gure shows the internal initiation, where the inspectors decide on their own to induce the inspection. . Figure .  In proactive systems, the inspectees decide themselves when to prove correct behaviour in terms of the collaborative protocol. To this end, they transmit on their own -corresponding to an assigned policycollaboration proofs to an inspector. . . . . . . . . . . . . . . . . . . Figure .  Several (not mutually exclusive) ways to initiate an inspection are possible. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  An architectural overview is shown left in the gure. Dark boxes show the most important parts to be specied during an application of the framework. The corresponding inspection architecture is shown on the right side. . . . . . . . . . . . . . . . . . . . . . . . . . Figure .

The inspection sequence of a two player Inspection Game is shown in the context of a distributed system (left) and schematically focusing on the players' interactions (right). . . . . . . . . . . . . . . . . . Figure .  Overview to the inspection procedure. . . . . . . . . . . . . . . . . . Figure .  Best response strategy (BRS) graphs present the game result by visualizing the player's behaviour in an easy comprehensible way. . . Figure .  The left BRS graph illustrates the specied IG and the right possible parameter adjustments. . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  Two networks are used for the application of the Inspection Game: the Scribe system disseminates by means of a tree-based network and basic gossiping creates a clique network. . . . . . . . . . . . . . . Figure .

These MQ graphs verify the prediction of the EIP function, which are ., . and . for the given parameters. The predictions are precise although some outliers exist with up to about . (%)

from the arithmetic mean (see VD graphs in gure B., page ). . . Figure .  The result graphs for the gossiping system show the inspectees' payo (rst row), message load (second row) and collaboration values (third row). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  The graphs show the simulation results for the Scribe system (all corresponding VD graphs are presented gure B. in the appendix on page ). The results comprise the inspectees' payo (rst row), message load (second row) and collaboration values (third, fourth row). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  In the enhanced IG approach, an inspector is completely deployed at the inspectee's peer (left in gure). The resulting inspection architecture is shown right in the gure. Inspectors control only the local inspectee, which creates sets of two-player games. . . . . . . . . . .

The inspection sequence of the enhanced IG is shown in the context of a inspection architecture (left) and schematically focusing on the players' interactions (right). . . . . . . . . . . . . . . . . . . . . . . . Figure .  The graph indicates the players' best response strategies (BRS) for the enhanced IG approach and the given parameters (see notation summary). Three inspection probabilities are indicated with the resulting collaboration degrees according the the IG model. . . . . . . Figure .  During the simulation, the message load and inspection rate, are changed twice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  The graph shows the inspectees' approximations to the varying inspector game strategy in the Scribe system. The curves -median with quartiles -are analogue to the gossiping system (not shown here). See gure C. (page ) for the corresponding VD graph. . . . Figure .  The graphs show the simulation results for Scribe (left column) and gossiping (right column). The corresponding VD graphs are given in the appendix (gure C., page ). . . . . . . . . . . . . . . . . . . . Figure .  The inspection probabilities were increased by ., resulting in targeted collaboration values ⇠ 0.87, ⇠ 0.7 and .. Thus, the collaboration value variances are reduced for the epochs with 1p ⇡ 0.7.

The VD graphs are shown in gure C. (page ). . . . . . . . . . . . Figure .  The IG mechanics can interact the user interface, as exemplary shown here for BitTorrent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  Two commonly used examples of user notications are shown. . . . Figure .  The IG conguration for the administrator could also be realized as additional area in the control interface. In this gure this is shown for the general game parameters. . . . . . . . . . . . . . . . . . . . . Figure .  An IG control interface allows to specify manual and automatic collaboration incentives (warnings, punishment etc.). It may also give a statistical overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  The user applications setting cause practical problems for the IG. Two are illustrated in the right BRS graph, using the values of the user interface mockups. . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  The IG principle is shown as population with the square as twodimensional strategy space. Ideally, the population strategy (PS) moves directly to the Nash equilibrium (NE). . . . . . . . . . . . . . . . . . Figure .

The general dynamics of the inspectees strategies may lead to several PS movements. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure .  A stable orbit can also be reached by means of a dynamic inspection rate mechanism. The inspectee's collaboration value uctuates around the target collaboration. . . . . . . . . . . . . . . . . . . . . . Figure .  The IG approach represents a framework for the design of BAR tolerance capabilities. As outcome, it enables to calculate parameters to achieve the targeted collaboration degree. . . . . . . . . . . . . . .

The These results correspond to those of gure C. (and thus also . on page ), however, the three inspection probabilities are increased by .. As result, the variations are strongly reduced for the epochs with 1p ⇡ 0.7..............................

LIST OF TABLES

Table .

The heterogeneity of overviewing works hinders the architectural comparability of Publish/Subscribe systems. . . . . . . . . . . . . . . Table .  Overview of the Publish/Subscribe architectural classication scheme. Table .  Exemplary classication of three pub/sub systems and the dissemination system basic gossiping (A=active, P=passive, R=reliability, NM=not mentioned, (..)=implem.-dependent). . . . . . . . . . . . . . Table .  The evaluation shows BAR tolerance capabilities of examined systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table .  The pre-dened scenarios of RCourse base on the taxonomy of failures introduced before. . . . . . . . . . . . . . . . . . . . . . . . . . . Table .  RCourse enables to enrich BAR tolerance evaluations by quantitative values. This is shown (with regard to the prior simulative study) for violation probabilities . and .. . . . . . . . . . . . . . . . . . . . .

Table .

The payo matrix for the basic Inspection Game shows the four possible results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table .  Solutions for all IGs up to m inspectors and n inspectees. p ⇤ indicates the inspectee's equilibrium violation probability and q ⇤ the inspector's equilibrium inspection probability. . . . . . . . . . . . . . Table .  Summary of the results for the Inspection Games Γ( The preparations enable a comprehensive reliability evaluation. This is shown here for the two systems that were used during the thesis -Scribe and Basic Gossiping. . . . . . . . . . . . . . . . . . . . . . . Table .  RCourse contributes to enrich the evaluation by quantitative information. To this end, it assists performing quickly launched simulations, also providing pre-dened scenarios. . . . . . . . . . . . . . .

1

INTRODUCTION

This chapter gives a thematic introduction and an overview to the thesis' contributions.

. The today's distributed systems are realized as a mere enactment of a collaborative protocol. This protocol is typically implemented in the application logic and represents the system's objective. Violations of the protocol are considered as harmful due to the reduction of the system's performance. However, this is possible by selshness-driven individuals, who follow personal objectives. With full administrative power over their machines, also called peers in the remainder, they are able to modify the application logic or encumber its execution. Direct physical access is not needed. Administrative power can also be obtained by malicious code (worms, viruses etc.) that take advantage of a system's vulnerability . In fact, even software can operate selshly. An example is a peer with limited energy resources, where a scheduler reduces the performance of specic applications to reduce the energy consumption.

In general, selshness-driven protocol violations are even considered as system attack [, ].

Faults (e.g. caused by hard-/software) can result to failures of collaborative interactions in distributed systems. These are also denoted as Byzantine failure []. In a larger scale, the probability that one of the peers is faulty increases strongly []. This may be exploited by selsh individuals by trying to hide their harmful behaviour behind Byzantine failures. Then, the probability of undetected selshness-driven protocol violations is increased. Furthermore, tolerating Byzantine failures and selshness plays an increasing role to achieve interoperability of the heterogeneous system landscape, a key aspect of future middeware systems []. Fault-tolerance techniques can reduce the impact of selsh-driven actions. However, they cannot fully avoid or tolerate them. This emphasizes the need for reliability approaches that take the possibility of selshness-driven peers into account. Aiyer et al. [] introduced under the name BAR model -Byzantine, Altruistic, Rational (BAR) an abstract development concept. Selsh (rational) peers are considered already during the system design among cooperative (altruistic) peers and Byzantine failures. Such property is also denoted as BAR tolerance. A full collaboration is not necessarily needed by the selsh peers. The system inherent reliability (e.g. redundancy) can be leveraged, which reduces the needed resources for the BAR tolerance mechanism. To this end, the system designer considers a targeted collaboration level. It is meant to be an average since selshness-driven peers cannot be forced to collaborate. They may even sacrice themselves for the personal goal accepting any consequences up to an expulsion from the system. Recent research activities addressed the problem of selsh behaviour in general (see for instance [, , ]). However, there is no work existent for a BAR tolerance design that takes also a behaviour analysis into account to achieve a targeted collaboration level.

Approaches to avoid or tolerate selsh behaviour are manifold. They comprise for example trust-(e.g. [, ]) and reputation-based contributions (e.g. []) or introduce detection mechanisms (e.g. [, ]). In contrary, approaches for modelling systems with selsh peers are similar and typically done with Game Theory (GT). It enables to model the complex situations with circular dependencies. Hence, it is suitable for a behaviour analysis as done in this thesis. To this end, a concrete system is used as exemplary use case. Possible candidates are for example real world applications or mere communication models. An interesting compromise is Publish/Subscribe (pub/sub). It combines a communication paradigm (high generality) with the functioning of the BitTorrent system (real world relation). Thus, pub/sub represents an ideal representative of distributed systems for the thesis' studies.

:

Let us consider now a scenario that illustrates the problem of selshness-driven individuals in distributed systems. The scenario consists of distributed video streaming based on the peer-topeer (PP) application BitTorrent. The content dissemination (or a good portion of it) is done by the peers itself, which reduces the expenses for a complex server infrastructure. This scenario corresponds to an existing service, known under the name BitTorrent Live . However, such video streaming systems are still under active research. In order to improve the throughput in presence of failures, they address among others general reliability approaches (see for example [, , ]) or the workload balancing and optimization (e.g. [, ]).

In this scenario, a selsh user has the personal goal of reducing the utilization of communication resources by limiting the outgoing bandwidth. This represents the problem of message loss since some network messages are omitted if the limit is reached. BitTorrent provides bandwidth limitation even as a settings feature in the application user interface (see gure . left). Furthermore, it can be realized at the network side without special knowledge. As an example, gure . shows on the right side the control panel of the router D-Link DIR-(about ). These examples show that message drops is a realistic issue for PP systems.

. . For a better understanding of the remainder, some thematic context is shortly claried here.

.. A Clarication of Terminology

This section targets to unify the reader's interpretation of important terms used in this work.

, ? Dependability has several characterizations in literature. Denitions of two works are shown below. These are the one of Laprie [] (upper quotation) and the IFIP WG . on dependable computing [] (lower quotation):

D

Computer system dependability is the quality of the delivered service such that reliance can justiably be placed on the service.

... the trustworthiness of a computing system which allows reliance to be justiably placed on the service it delivers.

Further taxonomies that structure terms such as dependability, reliability, fault-tolerance or survivability were proposed by Al-Kuwaiti et al. [] and Avizienis et al. []. Based on the denitions of the literature we interpret the term dependability as the following characterization: A service should -to some qualitative degree -exactly full the service as it is specied and therefore expected. The term dependability is not further discussed since it is considered as too abstract for concrete evaluations in this thesis. Instead, we focus on the other two notions -reliability and robustness -for the study of BAR tolerance in the remainder of the thesis. To this end, we rely on the denitions of the IEEE standard glossary for software engineering terminology []:

R

The ability of a system or component to perform its required functions under stated conditions for a specied period of time.

R

The degree to which a system or component can function correctly in the presence of invalid inputs or stressful environmental conditions.

Three major dierences can be identied in these denitions. First, reliability focuses on the ability to perform specied operations, while robustness considers the degree of correct system functioning. Second, the notion of reliability assumes stated conditions. This species a broad range such as the ability to tolerate failures, system dynamics or to guarantee a specied amount of service quality (e.g. latencies). In contrast, robustness rather considers fault-tolerance issues, which may lead to stressful working conditions for the system. Finally, the denitions dier in the considered duration. Reliability takes account of stated conditions only for a specied period of time, while robustness assumes the stressful conditions as not limited in time. To summarize, reliability has a qualitative character. It considered as the ability to perform the system operation "to some degree". In contrary, robustness has a quantitative character and denotes the degree of system functioning under stressful conditions.

Reliability is also explained by means of safety and liveness properties. They were initially introduced by Lamport [] as an abstract approach to characterize correct operation of distributed systems. They are outline in the following or the sake of completeness. However, analogue to dependability, they will not be further used in the thesis due to their abstractness.

S/L P

A safety property is one which states that something will not happen. ... A liveness property is one which states that something must happen.

() In contrast to the IEEE standard glossary for software engineering terminology [], we do not consider that a fault may only be caused by a defect in hardware or an incorrect logic. Instead, we follow for this thesis the comprehensive taxonomy of faults of Azinienis et al. [], who state that faults actually cause any type of failures. Hence, this taxonomy comprises all faults, that may aect a system during its life. For example, a fault may -among others -not only be caused by hard-or software but also by human actions or natural phenomena. In this context, we denote failures as the direct result of a fault, i.e. the system performed an erroneous action, is in an erroneous state or even not able to full the functions within specied requirements. Occurring in distributing systems, failures may harmfully aect the mutual collaborative interaction and thus, the functioning of the whole distributed system itself. This is denoted as Byzantine failure. This term is wellknown in the computer science community and relies on the Byzantine Generals Problem []. For ease of comprehension, we will consider also the term failure as synonym for Byzantine failures int the remainder of the thesis.

In order to characterize the notion selsh behaviour, we follow the denition of rational behaviour from Nielson et al. [], whose classication of peers in a distributed system is based on game theoretic model and mechanism design []. Their classication, visualized in gure ., distinguishes between peers that do strategize and those that do not strategize. Peers that do strategize can be further divided into rational (with system which is used in the thesis. In this context, selsh behaviour is considered as synonym to rational behaviour, assuming further a personal goal that diverges from the system goal(s).

. knowledge) and irrational ones (without or only incomplete system knowledge). Rational peers are therefore strategizing peers, which use their knowledge about the system to act in a selsh way (increase personal benet). In contrary, irrational peers aect the system without being aware of the complete system mechanics, e.g. a Denial-of-Service (DoS) attack.

In this thesis, a peer's selsh behaviour considered as the behaviour of a rational peer that follows personal objectives. Hence, a peer is considered as selsh if its behaviour diers from the expected one specied by the collaborative protocol. To be more precise, this means the case where a Proof-of-Misbehaviour (PoM) is detected.

A selsh peer's objective is assumed to be divergent from the system goals. Hence, it is harmful for the system functioning and can be considered as an attack [, ]. Ideally, it should be always possible to distinguish between selsh behaviour and a failure. This is not always possible due to the peer's ability to hide the malicious actions behind a failure (e.g. pretending message losses). However, if some degree is exceeded -being a real failure or not -a peer can be considered malicious just as a selsh one. Selsh behaviour is not necessarily caused by human beings but can also be caused software logic. One example has already been mentioned in the introduction, where a scheduler aects the functioning (e.g. in terms of communication resources) in order to reduce the energy consumption.

Nielsen et al. discussed [] three general mechanisms against selshness. Eliminating selsh behaviour as a concern (e.g. out-of-band trust, trusted software) is not always applicable. Genuine incentives give peers collaboration incentives by the system design. An example is the encryption of message content for a data storage service. Being unable to distinguish the owner, a peer will abstain from deleting others' data to save on its resources. Articial incentives always make use of auditing to detect misbehaviours and give some kind of collaboration incentive. Typical examples are the collection of proofs of misbehaviours (PoM) or reputation tables in combination with punishments (e.g. excluding a malicious peer from the system) when a misbehaviour is detected.

The BAR model [] was introduced as abstract development model. It species that rational (selsh) behaviour should be considered already during the system design process among Byzantine failures and altruistic (collaborative) peers. In other words, a BAR tolerant system is assumed to implement fault-tolerance techniques as well as techniques against selsh behaviour in order to tolerate or prevent violations from the collaborative protocol. The BAR model increases the general reliability of a system but it lacks in preciseness due to its abstract denition. Therefore, the thesis intends to ll this gap by providing a structured approach to maintain BAR tolerance mechanisms. This vision is detailed hereafter.

.. The Publish/Subscribe Paradigm

The Publish/Subscribe (pub/sub) paradigm realizes application-layer multicast (ALM) communication. It provides an event-based interaction-style characterized by full decoupling in time, space and synchronization []. Thus, it is also considered as event-based middleware for the development of distributed applications (see for instance [, , ]). Pub/sub sys- In pub/sub systems, the subscriber can subscribe to a multicast group of interest by informing the NS. Similarly, the publisher can publish an event message (or just event) by transferring it to the NS, which is then responsible to the delivery to interested subscribers. The process of identifying the interested set of peers is called subscription matching. The actual NS functioning remains a black box for the interacting publishers and subscribers.

The simplest NS realization is a single component or peer, which represents a client/server architecture. However, more advanced system consider usually a distributed architecture where the notication responsibility is distributed over dierent notier peers. Indeed, they may also hold dierent roles. A peer may be publisher, subscriber and notier at the same time, depending on the specic implementation. Due to the pub/sub logic at the application layer, overlay networks is maintained being independent from the implementation details of underlying network layers. Therefore, applications over networks such as the internet are possible without requiring specialized hardware or protocols. The pub/sub paradigm is illustrated in gure . from the interaction-style (left in gure) as well as technical point of view (left in gure), i.e. position in the network stack.

The pub/sub paradigm has attracted much research eort over the last decade, leading to a large number of heterogeneous systems. The rst systems followed a deterministic dissemination structure and targeted mainly core aspects such as subscription type (e.g. topic-, content-based) or overlay organization. Later on, unstructured approaches [, , ] introduced systems with non-deterministic dissemination schemes. Among general architectural developments, researchers focussed also on other aspects such as scalability [], reliability [], quality of service [] or security []. Furthermore, distributed optimization algorithms have been applied to Publish/Subscribe []. Worth to mention is also the PSIRP project , which tries to redesign the internet architecture from a pub/sub point of view. Several works reviewed the research (e.g. [, , ]) and outlined architectural specications.

. . Several works considered selsh behaviour and introduced systems that are BAR tolerant to some degree. Typically, selshness aspects focus only on specic selsh goals and circumstances (see for example [, , ]). Other threats are ignored and they are not considered to be coupled with other techniques or reliability mechanisms. Furthermore, implementing subsequently mechanisms with regard to other selsh goals becomes complicated due to the deep protocol modications. To summarize, there is a design gap in terms of reliability mechanism considerations between the high level BAR model and the low level system implementations. This is illustrated in gure . left.

The vision of this thesis (gure . right) is to ll this gap by providing a design concept that supports the development of a system's BAR tolerance capabilities. To this end, two requirements are given and the corresponding . A solution approach shall be abstract enough to cover any Byzantine failure, any selsh goal and any system architecture. At the same time, it shall be precise enough to achieve specic implementations.

. It should be able to leverage given reliability mechanisms or technique by attaining a targeted collaboration level of selshness-driven peers.

In order to cover the vision's rst requirement, a solution approach will be formulated as framework to achieves a exibility in terms used mechanisms. In this context, genuine mechanisms are not possible. They require deep adaptions of system internal processes and are therefore in conict with the abstractness of the vision. Hence, a distributed systems' functioning shall be aected as little as possible to increase the applicability to dierent system architectures. To this end, an articial mechanism, a system monitoring approach will be used, which controls the peers' interactions in combination with giving collaboration incentives. The monitoring of all interactions is considered as too costly for the general case and performed by sampling. The principle of this monitoring approach is shown in gure .. The system itself is considered as a black box and its original functioning is kept basically unchanged. Instead, a data structure denoted as inspection target maintains proofs of a peer's behaviour. It is controlled during an inspection by an inspector, which works on behalf of the system administrator. He has the power to stimulate a collaboration by positive incentives (rewards) for collaboration or negative incentives (punishment) in case of detected misbehaviours. The latter one is a common technique (see for instance [, ]) and thus used in this thesis. Finally, a desired collaboration level is reached by an appropriate rate of inspections. The determination of the inspection rate is a challenging task due to the behavioural interdependencies of the peer (violating or not) and inspector (inspecting or not). However, the monitoring approach corresponds directly to a class of Game Theory (GT): Inspection Games (IG). Hence, it makes sense to leverage the power of GT to model the complex and interdependent decision landscape. The modelling of the players' (the peer and the inspector) behavioural choice as IG enables a behaviour analysis of the players. As outcome, a system designer is able to calculate an inspection rate to reach the desired collaboration value.

During the thesis, the IG approach is applied to an illustrative use case. To this end, we consider the aforementioned selshness-driven message drops scenario and Publish/Subscribe The IG is considered as framework for the system design. The application to an illustrative use case shows the utilization in detail and how collaboration is achieved.

. as system type. As a communication paradigm, it provides naturally a broad applicability. Furthermore, it realizes Application Layer Multicast (ALM) communication. This represents directly the BitTorrent application of the scenario with the multicast groups as the several video streams. Thus, pub/sub is considered as ideal system candidate. The IG application in the thesis stays general but provides at the same time a relation to an illustrative real world application. The methodology to meet the vision is illustrated in gure ..

.

In the context the thesis' vision, the main research challenge can be formulated as in the following:

M R C

Enable the deployment of a distributed system over selsh peers and obtain a targeted collaboration level in average. This challenge is similarly abstract as the vision itself and opens a bunch of further research questions. For example, what types of distributed system architectures are available and what are there general reliability capabilities. A crucial aspect concerns the selshness-driven violations and the impact on the collaborative protocol or, in other words, on the whole functioning of a specic system. Further aspects to examine are how to integrate the specic mechanisms in a theoretic model, how does it perform under real world conditions and how could it be realized in current applications. The possible research question are manifold. However, there is a general design principle recognizable. During the top-down design it is important to have a mutual calibration feedback between the system behaviour and the theoretical model. For example, determine a system's BAR tolerance capabilities has inuence on the targeted collaboration level. At the same time, it must be examined if the theoretical model's outcome corresponds the expectations, possibly resulting in further calibrations and evaluations.

In order to meet the broad main challenge, it is split into three straightforward research challenges that are listed hereafter. The rst challenge (A) evaluates the reliability of current systems as part of the state-of-the-art. As we will see later, some preparations are needed, resulting in two further tasks (A.) and (A.). Challenge (B) refers to quantitative evaluations such as the system impact of selshness-driven violations. It represents the practical side of the aforementioned principle, the mutual feedback during system design. Challenge (C) comprises not only the (generic) theoretical framework but also an application to distributed systems. It represents therefore the theoretical side of the design principle and the main research contribution.

(A) Evaluate the BAR tolerance capabilities of current distributed systems.

(A.) Provide an architectural classication during the evaluation. (A.) Specify possible failures that can be used as evaluation metrics.

(B) Develop a tool that supports the simulative evaluation of selshly operating peers' impact on the system functioning.

(C) Develop an approach to attain a targeted (average) level of collaboration if a distributed system is deployed over selsh peers.

The thesis' contributions are directly related to the research challenges. They interact as described before in the top-down design principle, which is illustrated in gure .. The interactions of the contributions are outlined here and will be detailed during the conclusion of the thesis (chapter ).

• Preparations for comprehensive evaluation Related to the tasks (A.) and (A.), this contribution serves as preparations to the BAR tolerance evaluation of challenge (A). It is presented in part and comprises of an architectural classication and a taxonomy of elementary failures. Thus, this contribution discusses the lacks of current system and introduces preparations for a BAR tolerance evaluation. It was published in [] and is part of [].

• Reliability evaluation of pub/sub systems Also presented in part as part of the state-of-the-art, this contribution evaluates the BAR tolerance capabilities of current pub/sub systems. It is related to challenge (A) and performs the evaluation in a qualitative way based on the prior work, the architectural classication and a taxonomy of failures. This contribution was published in [].

• RCourse: An extension library for peersim to robustness evaluations RCourse represents the practical contribution in terms of the aforementioned design principle. It simplies simulative studies with a special focus on robustness capabilities to enable quickly launched evaluations. Hence, it serves as tool to evaluate the impact of selshness-driven violations and to verify the IG approach or parameter calibrations. Furthermore, it provides simulation scenarios that are based on the BAR tolerance evaluation. Thus, RCourse is suitable to enrich it by quantifying information. Published in [], RCourse addresses challenge (B) and is introduced in part .

• Inspection Game approach to deploy distributed systems over selsh peers The whole part is related to research challenge (C) and introduces with the enhanced IG approach (chapter ) a solution approach. It is preceded among others by GT foundations and is followed by a discussion with regard to real world applications. During presents the current state-of-the-art in terms tolerating selshness-driven harmful impact on the system functioning. The following two chapters are related to this objective:

• Chapter discusses the related work of the scientic community with regard to the research challenges.

• Chapter reviews BAR tolerance capabilities of systems. This chapter is dedicated to meet challenges (A), (A.) and (A.).

introduces an approach for practically evaluating the robustness of distributed systems with Publish/Subscribe in particular:

• Chapter details the RCourse library, which intends to meet challenge (B).

is related to research challenge (C), i.e. attaining a specic degree of collaboration for distributed systems being deployed over selsh peers. This part consists of several considerations as outlined in the following:

• Chapter provides theoretic foundations used by the IG approach in the remainder.

• Chapter discusses several aspects that need to be considered for the application of the IG to distributed systems.

• Chapter introduces the IG approach as possible solution for research challenge (C). All game and implementation details are provided that are needed for a realization.

• Chapter presents an enhanced dynamic IG approach, which is based on the one of the foregoing chapter . Hence, this chapter focuses on the dierences to the initial one.

• Chapter discusses the applicability of the IG to real world systems as well as the meaning for user and administrator.

nalizes the thesis with two chapters:

• Chapter concludes the thesis by discussion the meaning of the contributions in terms of the research challenges.

• Chapter provides some possible future work related the main contribution, i.e. the IG approach to attain a targeted collaboration level.

RELATED WORK AROUND THE RESEARCH CHALLENGES

This chapter introduces related work around the research challenges stated before and also for Inspection Games due to its critical role for the thesis' solution approach.

. :

We discuss now the related work for research challenge (A), the BAR tolerance evaluation of distributed systems. This section covers also the tasks (A.) and (A.) since, as we will see, a BAR tolerance evaluation is not available. Several reliability related works are presented before as an outline to the vast progress in this eld.

Reliability has been a design issue from the beginning of the distributed systems development. In fact, Freeman [] discussed already in the year -far before modern and exible networked architectures -design concepts to achieve reliable software. Lamport formulated in safety/liveness properties [] as abstract requirement for reliable systems and a variety of works addressed further foundations or reliable systems (see for instance [, , , , , , , ]). In the following decades, the research community developed several practical approaches to reach reliability in distributed systems. General fault-tolerance [, , , , , , ] was addressed (typically using redundancy and cryptography) but also specic issues such as recovery from failures [, ], security [, , ], trust and reputation [, , , ], accountability [] and Quality of Service (QoS) [, ].

The contributions are manifold but can roughly be separated into general reliability concepts (e.g. [, , ]) and specic approaches or implementations (e.g. [, ]). During the last years, the scientic community draw increasing attention the problem of selsh peers -in addition to (Byzantine) fault-tolerance -for system reliability and security. Nielson et al. characterized in [] the notion of rationality in the context of selshness driven attacks. The BAR model was proposed by Aiyer et al. [] as an abstract development concept to deal with selshness already during systems design. It was applied to several systems (e.g. [, ]) and a broad range of works considered selshness. A closer look will be given in section .. Several surveys reviewed the numerous contributions in the domain of reliability and BAR tolerance. In the beginning, they focused on general methodologies and mechanisms [, , ]. More recent overviewing works aggregate the foregoing research works and discuss rather general shortcomings, analysis models or reliability concepts. In other words, they concentrate on the review of reliability evaluation " A safety property is one which states that something will not happen. ... A liveness property is one which states that something must happen."

models. This corresponds also to a recent survey [] of Isa et al. The authors argue the need for an intermediation approach to correlate reliability models with performance aspects. In their work, they review existing metamodels and discuss dierences in terms of concepts, modelling and analysis. A further survey of Tyagi and Sharma [] estimated the reliability of component based systems in terms of their

• scope, e.g. component based systems, Service Oriented Architectures (SOA),

• models, e.g. path or state based models,

• technique, e.g. algebraic methods, mathematical formulas,

• validation scheme, e.g. fully validated, validation through experiments,

• and noticeable features.

This framework was used to review approaches but specic reliability details (e. introduced in [] an approach for a reliable and time-sensitive pub/sub middleware. They reviewed as preparation the reliability of pub/sub systems and introduced a taxonomy of Byzantine faults. However, their review is not fully satisfying for the study of this thesis. Important failures such as packet loss or link/node crashes were considered but no selsh peers or other possibilities with negative impact. Modied event content, injection of unauthorized messages and varying publishing rates (e.g. in streaming applications) are examples for missing scenarios. In addition, the taxonomy mixes peer failures (e.g. link anomalies, node crash) with more enhanced failure scenarios such as node churn or network partitioning.

To summarize, the given surveys concentrate basically on reliability evaluation concepts and models. There is currently no work available that reviews the actual reliability capabilities in a comprehensive way considering elementary failure types. Similarly, the additional possibility of selsh-driven peers and correspondingly needed mechanisms -BAR tolerance Node churn denotes the naturally dynamics of the system, i.e. entering/leaving peers. However, if some degree is exceeded, it may harmfully aect the system functioning.

. :

Table .: The heterogeneity of overviewing works hinders the architectural comparability of Publish/-Subscribe systems. -is not covered. This shows the lack of a comprehensive BAR tolerance evaluation and underline the need for research challenges (A) and (A.).

Despite the extensive research in the domain of reliability and dependability, there are still ambiguities in terms of notions and interpretations. The authors of the two aforementioned works [, ] identied this lack and targeted to counteract this situation. They compare several attributes as well as denitions, clarify possibly overlapping interpretations determine characteristics for common concepts (e.g. fault-tolerance, security). However, they concentrate only on reliability, security and similar aspects. A heterogeneous interpretation is also given for the architectural specication of distributed systems. An example is shown in table . for three works, which are reviewing pub/sub systems. Only two comparable architectural dimensions are shown here: the overlay organization and the routing (or dissemination) technique. Nevertheless, strong distinctions are in focus and terminology are noticeable. This heterogeneity hinders architectural comparisons. Overviewing books such as Distributed Systems: Concepts and Design [] or the Peer to Peer Handbook [] present primarily the general architectural concepts. Other aspects (e.g. data model, techniques to adapt system dynamics). This emphasizes the need for challenge (A.), an architectural classication, as preparation for a BAR tolerance evaluation.

. :

To quantify a system's robustness with regard to failures or the impact of selsh behaviour, theoretical analyses such as [] are not completely satisfying. The modelling is challenging and possibly not appropriate for all evaluation metrics. A common alternative is benchmarking through experimental evaluations. However, basically all works in the literature considering robustness benchmarks focus on the benchmarking model and its specication. They address among others the specication of an appropriate fault-load (e.g. [, ]) and fault-injection (e.g. []). Evaluating works concern only specic aspects or circumstances. Examples are robustness evaluations of web service interfaces [] or the routing in noncollaborative opportunistic networks []. An exception is the the recent work of Kim and Anderson [] who present an extensive robustness evaluation of a set of distributed systems. They examined network types (random and hypergrid graphs, etc.) with three peer removal attacks (random, high-degree, high-centrality) and present more than result graphs. This vast evaluation frames well the systems' robustness in terms of crashing peers or their communication links. However, it does not cover other systems or failures. Nevertheless, the complexity of this work emphasizes the sense of individually adapted evaluations. Industrystandard benchmarks such as the SPECjms concentrate on performance related evaluations (see also []). Thus, robustness evaluations are typically done by means of network simulation environments (e.g. Omnet++ ), which may provide some visualization capabilities. However, there is currently no work that eases robustness evaluations as a whole. Such approach should comprise among other simulation scenarios for several failures, measurement value aggregation as well as analysis. The lack of such an approach underlines the need for research challenge (B) to ease robustness evaluations with regard to selsh peers.

. :

We consider now the important challenge (C), i.e. achieving a targeted degree of collaboration from selsh peers in distributed systems. Due to the tremendous amount of works dealing with selshness, this section highlights only the major approaches. They can be roughly distinguished in game theoretic and non game theoretic, each one with subdivisions, which is illustrated in gure .. This separation represents also the structure of this section, while Inspection Games are discussed independently due to the similarity to the thesis vision & methodology.

Game Theoretic Approaches

The majority of works considering selsh peers are done in the context of game theoretic modeling. This frequent utilization of Game Theory (GT) can be explained by its denition: "... the study of mathematical models of conict and cooperation between intelligent rational decision-makers. " [ ]. Hence, GT is well-suited for the analysis of selsh peers' behaviour in collaborative environments, possibly forming complex situations with circular dependencies. Modern GT started in the context of economic analyses with von Neumann's and Morgensterns book []. Later on, the research community in this eld achieved many classes of games (a recent overview is given in [, , , ]). GT found application in economics and other disciplines such as political sciences or biology. Shenker [] discussed GT and selshness in as one of the rst for distributed systems. However, the scientic community picked it eectively up in the early 's, at rst dealing with general challenges [, , , , , ].

The GT research community developed a set of works to face the problem of selshness. Typically, they consider specic reliability and security issues with regard to decision making in real-world situations. Several works address the exemplary scenario of the thesis, i.e. the correct packet forwarding in networks consisting of selsh peers. For example, Mei and Stefa introduce with GiveGet [] two forwarding algorithms. Both protect cryptographically the packet transfer, which is separated in three phases: message generation, relay and test. With game-theoretical considerations they formally show that their protocols attain Nash equilibria and that no player has interest in violating, i.e. dropping messages. Another interesting work is FlightPath [], which addresses to reduce jitter as possibility for selshness-driven violations in the context of streaming applications. The authors examine approximate equilibria (instead of targeting strict Nash equilibria) for designing incentives to limit selsh behaviour. To this end, the message transfer between two peers are among others cryptographically secured (e.g. by encrypted promises). The FlightPath system is analyzed and evaluated used the e-equilibrium . The approximate equilibria approach provides some exibility to handle dynamic situations such as node churn. The experimentations show a functioning in case of % malicious and % selshly acting peers.

A further interesting work is the cartel maintenance framework Han et al. [], which is based on repeated games. Here, participants of a cartel agree to some contract for a minimum degree of (average) collaboration and a punishment for non-collaboration. In the considered use case, each participant has a time slot for Media Access Control (MAC) of a wireless network. The collaboration degree is determined by observing the media access. If the collaboration falls below the agreed threshold, all noticing participants choose a non-collaboration strategy that reduces the players outcome of the game . The cartel approach is an elegant way to attain a (minimum degree of) collaboration in a distributed way. However, the whole game mechanism relies on a shared resource (here: media access) for estimating collaboration

In the context of internet streaming, jitter denotes the varying delivery delays such that the receiving packets do not arrive in time (too early or late). Hence, buers are typically used as compensation.

In such an equilibrium, rational selsh players deviate only if they expect to benet by more than a factor of e. Non-collaboration strategies are not further specied in the paper. An example by accessing the media during the violating peer's time slot. and triggering punishments. Other violations (message drops, access spoong etc.) require further modications.

The approaches introduced here address packet forwarding (see also [, , , ]). Other works target further aspects such as routing [, , ], resource/bandwidth allocation [, , , , , ], multicast dissemination [, ], load-balancing [], service orchestration [, , ] or wireless sensor networks [, ]. They cover several characterizations such as (non-)zero-sum, (non-)cooperative, Bayesian, dierential, single-round or repeated games. Recent overviews to IT-related models and applications can be found in [, , , , ] and the references therein. Although numerous works are given in the literature, they represent only solution approaches for specic issues. Hence, they are not able to secure a whole collaborative protocol as addressed by challenge (C). Some contribution such as the one of Saleh and Debbabi [] face the problem of selsh peers from a more comprehensive point of view. Their contribution is based on some prior work (e.g. []) and follows the idea of using games in logic specications. This idea was initially proposed by Lorenz []. Saleh and Debbabi introduce a modeling framework of security protocols with concepts of game semantics. It models the specic protocol functionalities (e.g. digitally signing a message) as strategies over a game tree that represents the protocol. This approach enables a system designer to express a broad range of security properties (secrecy, authentication, fairness, etc.) and to specify and verify the resulting (cryptographic) protocols.

Proposing a general game-theoretic framework, Moscibroda et al. [] study the eciency reduction of a system consisting of selsh peers in case of malicious behaviour. The collaboration incentive is given by the impact of malicious peers, which reduce the selsh peers' utility. The introduce the term price of malice, which is "... the ratio between the social welfare or performance achieved by a selsh system containing a number of malicious players and the social welfare achieved by an entirely selsh society." Hence, in contrast to the price of anarchy the reference point is orthogonal. It is not a socially optimal welfare but the welfare of system consisting of selsh peers. This framework is applied to an abstract network graph playing a virus inoculation game (installing anti-virus software or not). The authors study the bounds of the price of malice and a fear factor in terms of utility loss through malicious peers.

These two approaches are examples for a large number of GT approaches that address general reliability issues. Similar works to secure collaborative network protocols are for example [, , , ] and several approaches for general reliability analysis of distributed systems are available (see for instance [, , , , ]). These works represent important contributions and can indeed be (partially) used as mechanism against selsh peers. However, they remain either protocols for specic issues or they represent too general analyses for concrete applications. Thus, they are interpret as not fully sucient with regard to the thesis vision and research challenge (C) in particular.

. :

Non Game Theoretic Approaches

Non game theoretically approaches use typically basic techniques such as redundancy and cryptography to increase the reliability/security of a system. For example, the work of Garg and Grosu [] introduces a way to secure multicast dissemination systems that are based on the Shapley Value mechanism []. To this end, they implement signatures for message authentication and auditing/verication to detect cheating of the peers. As further example, Fotiou et al. [] discuss security requirements, attacks and possible cryptographic solutions in rendezvous node based PP systems. Such approaches are only capable to harden specic aspects of a system. Therefore, we concentrate now on three predominant approaches of the scientic literature that intends to face malicious actions, possibly caused by selsh behaviour. This is misbehaviour detection, trust and reputation systems and accounting methods.

Detection systems only focus on the detection of misbehaviours but also to make them known to other participants in the system. In a recent work of Serrat et al. [] for example, so-called watchdogs at a peer can detect misbehaviours during interactions with the others. The watchdog is assumed to be collaborative to some degree, i.e. to disseminate information about selsh peers. In this context, the network is modelled with continuous time Markov chains to study the dissemination performances in terms of speed and message overhead. A work related to the vision of this thesis is the work of Cristea et al. []. They propose an architectural model, which combines monitoring with analysis and response mechanisms. The data are assumed to be continuously collected in real-time by an external monitoring system. The basic idea of the authors is the data analysis to detect failures by pattern matching and to predict failures, e.g. by using articial intelligence (neural networks, moving average distributions etc.). Other works concern misbehaviour detection in terms of packet forwarding [], backo algorithms and media access [, ] in wireless networks or the detection of colluding attackers [, ]. More information can be found in the recent review of Raghuvanshi et al. []. The detection of misbehaviours is considered to be combined with further mechanisms such as failure-recovery or collaboration incentives (punishments, rewards etc.). In contrary to this concept, the thesis targets to prevent failues by giving collaboration incentives. Hence, the cannot directly serve as solution approach for research challenge (C) but could be an alternative or extension to monitoring techniques.

A further approach against malicious attacks or selfish behaviour are Trust Management Systems (TMS)[, ], typically realizing reputation systems []. They aggregate and distribute feedback about the peers' behaviour to calculate reputation values. These quantify the peers' trustworthiness and serve as decision support in terms of collaboration. Thus, the collaboration is encouraged in a passive way. A peer can decide to work only with trusted peers, e.g. by denying requests from untrusted ones. A typical approach is the work of Shah and Pâris []. They enable trusted relations for the Bittorrent protocol by means of a local and a global score. The local score is determined by surveying the collaboration result (e.g. packet forwarding). The global score is maintained by tracker peers, which only assist in communication by providing complete membership information.

The global trust score is attached to each reply of a communication request and thus automatically disseminated to the peers in the network. The recent CAST system of Li et al. [] introduces a context-aware approach for MANETs. By aggregating various contextual information (e.g. communication channel status, battery status), they are able to distinguish between malicious behaviour and faulty peers. With the CONFIDENT mechanism [], Buchegger and Le Boudec introduce an extension to Dynamic Source Routing (DSR) protocols for the specic use case of correct packet forwarding. It consists of four major components . They monitor the correct forwarding and exchange positive (collaboration) as well as negative (violations) feedback with other peers for a trust value calculation. Evaluations show a functioning of up to % malicious peers in the system. However, falsied misbehaviours (false positive) can be exchanged to blame other peers. This is solved by the similar CORE mechanism [], which exchanges only positive feedback for the reputation calculation. Apart from that, it uses also surveillance and reputations to evaluate a peer's trustworthiness. Other approaches (see for instance [, , , ]) use similar mechanisms as those that were outlined here. Several surveys [, , , , , ] review trust and reputation systems.

Trust and reputation systems are indeed a promising approach with respect to challenge (C). This especially due to the loose coupling of the application logic and a given (passive) collaboration incentive. Reaching a targeted collaboration is generally imaginable but requires further research. Two major drawbacks are noticeable: The reputation is determined over time, possibly leading to a low reactivity, and the reputation is very simplistic (typically a collaboration or trust value). Hence, such approaches not able to take the complex decision landscape (possibly strategies over time) of selsh peers into account.

Accounting methods model the interactions of peers within economic model, typically using some kind of virtual currency (other notions are credits, debts or tokens). An example is the PastryGrid system of Abbes et al. [] in the context of grid systems. Each machine has a budget. The resource usage of other machines (in terms of computation or communication services) has a cost value and reduces the budget. Similarly, the budget can be increased by cooperating (selling own resources). Selsh behaviour, i.e. predominantly using the others' resources, is prevented by a limited budget. Being zero or a negative value, a peer must collaborate before using the others' resources. Further examples with economic models are [, , , ]. Accounting methods are an elegant way to reach collaboration and indeed practically used by applications such as Bittorrent clients. They are usually developed as built-in mechanisms, which hinders the adaptability and integration with other mechanisms. Furthermore, accounting mechanisms are not approaches for reliability from a comprehensive point of view. The focus typically on specic aspects relevant for a fair system functioning such as a up-/download ratio. They suitable for other threats possibly caused by selsh peers, e.g. attacks or malicious behaviour (e.g. content pollution, message drops). Thus, they are considered as not fully sucient for challenge (C). Over the last years, research eort was spent to the IG models. Unfortunately, there is currently no work available with applications to communication infrastructures, ensuring the reliable functioning of communication protocols or research challenge (C) in particular. An adaptation of the basic IG model of Dresher is however reachable with some further eort. This consists basically in an extension by false negatives (non detection of misbehaviours) due to limited resources.

. This chapter introduced related work with regard to the thesis' research challenges. The given works related to challenge (A), a BAR tolerance evaluation, draw a clear picture. Although a multitude of works addresses reliability, evaluations or corresponding surveys, there is no work providing a comprehensive evaluation of BAR tolerance capabilities. Given works concentrate only on evaluation models/concepts, focus only on specic aspects (e.g. link/node crash) and lack in the consideration of selshness. In addition, there are still some ambiguities in the interpretation of terminology and architecture.

The situation is similar for challenge (B), evaluating robustness capabilities of distributed systems. The given works discuss benchmarking models (e.g. fault injection) or evaluate the robustness only for specic circumstances. Only one recent contribution evaluates by a vast simulative study the capabilities of network types -however, only in terms of link/node crash (with three types though). This shows the need for an approach that eases simulative robustness studies as a whole, which represents challenge (B).

Numerous works dealed with selshness in distributed system, which is related to research challenge (C). The related work was discussed by separating game theoretic and other appraoches. The majority of works to contribute by of GT models for specic application scenarios. Only few GT works have a broader point of view as needed for challenge (C) to secure a whole collaborative protocol. The broad utilization of GT is comprehensible since this discipline deals by denition with models of cooperation between intelligent rational players. The discussed non GT works represent three predominant types of approaches: misbehaviour detection, trust and reputation as well as accounting systems. The amount of works dealing with selshness is tremendous. However, there are several drawbacks with regard to the thesis' vision. The game models are not directly applicable, they are too specic or provide too general analyses. Hence, the given works are not suitable for the thesis' monitoring approach and not satisfying for challenge (C). In contrary to other game models, Inspection Games found only little application in distributed systems and a directly suitable work is not available. Nevertheless, the general game model ts well to the thesis' methodology and will be used, after some needed adaptation, as solution approach for challenge (C).

ASURVEYOFBARTOLERANCEINDISTRIBUTEDSYSTEMS

In this chapter, we review the BAR tolerance capabilities of a set of systems as representatives for distributed systems. As discussed in the last chapter, a comprehensive comparison is hindered due to several reasons. Hence, some preparations for the evaluation are introduced beforehand, which represent at the same time the evaluation structure.

. The preparations for a BAR tolerance evaluation consist of an architectural classication and a taxonomy of elementary failures of a peer. They will be detailed in the following.

.. Architectural Classication Scheme

The classication scheme consists of nine architectural architectural dimensions, which are described in the following. They are clearly arranged in table . providing example categories for each dimension. For illustration reasons, these nine dimensions are exemplary applied to a sample of four systems in table .. To design these architectural dimensions of the classication, previous surveys as well as other overviewing works around pub/sub such as [, , ] were aggregated. The following criteria were used:

. The dimensions should not overlap.

. The dimensions should be sucient to fully classify a set of works of the literature that considered as important.

. The dimensions should completely cover all options for the selected works, that are critical for the functioning of a system .

The subscription model enables the specication of interest. Common models are topic-, content-[] and type-based [], which mainly dier in their expressiveness. Topics represent only whole multicast groups by means of a unique identier, while content-based models classify event messages not by an attribute but rather by the content itself. This enables a more ne grained specication of interest up to single messages at the price of higher resource usage. Type-based subscription models are rather related to (objectoriented) application developers and can easily be deployed on top of a content-based model. An event represents an object related to a specic type. Hence, it can implement attributes and methods, which brings improvements such as type-safety. Other examples are XML-[] or context-based [] subscription models. More details can be found in []. The event data model species the representation of event messages in the system. In systems with a high rate of published events, the data model can cause signicant delays due to the amount of messages to be processed. The event data model can be classied into three general types. Tagged formats such as XML structure information hierarchically into elds that are accessed by an identier (tag). On the contrary, untagged binary formats (e.g. IP or TCP header) provide a xed structure, which makes processing ecient as lookup costs are constant. A comparison of tagged and untagged binary format has been done by The Gryphon Team []. Serialized formats such as the Java serialization format can represent complex information such as objects in object-oriented programming languages. However, they are computationally intensive compared to simple event messages.

. Matching algorithms are used to identify the subscribers that are interested in a given event (subscription matching). They gain in importance in large-scale systems as the amount of subscriptions and/or processed events increase(s). Then, similar to event data processing, the subscription matching may require a signicant amount of time. Subscription matching algorithms can be classied into two main groups [], predicate indexing algorithms and testing network algorithms. Predicate indexing algorithms divide subscriptions into their elemental constraints, which are then used to identify a matching event message. Testing network algorithms use subscriptions to create ecient data structure for the matching process []. Examples are matching trees [, ] and binary decision diagrams. A formal comparison and analysis of matching algorithms is given in [].

This species the organization of the logical overlay infrastructure. It includes among others the choice of communication partners and the group management policy. Thus, it has a strong correlation with the dissemination technique. Three common types are hierarchical systems, which follow the client/server principle, PP systems with a at hierarchy and clustering approaches. The hierarchical organization (e.g. in form of a tree) enables logarithmic hop counts on the logical overlay. PP systems can be further divided into structured and unstructured systems []. Structured Peer-to-Peer (S-PP) overlays use a deterministic approach to set up a static dissemination structure. In contrast, Unstructured Peer-to-Peer (U-PP) overlays use non-deterministic techniques such as random walks create a dynamic dissemination structure. Clustered overlay organization denes independent domains of administrative control. They are typically used to increase performance or scalability. Another organization option are Broker Overlays (BO) [, ], which distinguish between peers that publish/subscribe (clients) and forward (servers). The latter type of peers are also called brokers. Client peers have exactly one broker as their access point to the overlay network (which is in turn realized by brokers). BOs can be interpret as a hybrid between a one-level-hierarchical and a PP overlay. Therefore, they are classied here as subdivision of PP overlays by aggregating the clients' interests into the peer (gure .).

The dissemination technique species the routing of messages in the overlay network. It is a crucial factor of the scalability of the system. Flooding algorithms forward a received message to all known peers and we distinguish between event ooding and subscription ooding. Selective algorithms make use of a deterministic routing process. In selective/ltering, the subscription matching is done in a decentral way: a peer forwards events only to those outgoing links that have (matching) subscribers behind it. In ... selective/rendezvous, a specic peer (the rendezvous node or r-node) is responsible for subscription matching of an event. It is typically chosen by applying a mathematical function such as a hash functions on parameters of the event (e.g. topic identier). All events of an event group are sent to the rendezvous node, which is aware of subscribers and forwards the event to them. Thus, a dissemination tree is realized, also known as DHT-based approach []. Basic gossiping follows the principle of epidemic algorithms [], in which events are forwarded to a set of randomly chosen overlay links. In informed gossiping, this set is partially dened in a deterministic way, e.g. to form a logical ring for a guaranteed delivery.

Two methods are possible to enable a system's adaption to topological changes. Here, we focus only on failure situation, omitting the case where a peers logs o correctly. The active way checks the state of another peer by sending periodically a heartbeat message. If the recipient fails to respond within a specied time window, it is considered as having left the system -the system must thus be adapted to this new state. With the passive method, a peer identies the need for adaptation reactively when observing a deviation from standard behaviour. Common triggers are timeouts or exceeded thresholds. This dimension denes how the communication is technically performed. It does not aect the overlay structure but may have signicant inuence on its characteristics such as performance or interoperability. Three common types are mentioned here. Socket connections are a platform-independent possibility for data exchange. They enable ecient communication by reducing the communication overhead, while the message format is not specied. A Remote Procedure Call (RPC) enables function calls in distributed environments, e.g. the event notication call at a peer. Many RPC implementations are available, which are not necessarily compatible to each other. Furthermore, web services can, similar to RPC, request launching a function on a remote peer. They are standardized and enable the integration of heterogeneous programming languages and systems.

An underlay-aware system has knowledge about the underlying physical network, which allows an overlay optimization. The underlay-awareness can be classied as proximity-based (e.g. hop distance, knowledge about subnets/clustering) and quality-based (e.g. bandwidth usage, round-trip-time). These types are not mutually exclusive and a system may combine several approaches. Quality of Service (QoS) mechanisms target to provide guarantees for specic quality aspects, which is however hardened by the loosely coupled communication. Therefore, the operation is often done in a best-eort mode. Research eorts aimed at extending pub/sub systems to make QoS guarantees possible [, ]. Mahambra et al. have proposed a QoS taxonomy for event-based middleware in [], consisting of guarantees for latency (L), bandwidth (B), reliability (R), delivery semantics (DS) and message ordering (MO). Due to space constrains, the abbreviations indicated in brackets are used for classications in tabular form such as table .. Note that in this example only R is indicated since no other QoS mechanisms are implemented.

. Table .: Exemplary classication of three pub/sub systems and the dissemination system basic gossiping (A=active, P=passive, R=reliability, NM=not mentioned, (..)=implem.-dependent).

N S M E D M M A O O D T A T C T U A S Scribe [] topic NM (tagged) lookup table S-PP selective (rendevous) A NM - R Gryphon [] content untagged binary predicate matching BO/S-PP selective (ltering) P NM prox. R SpiderCast [] topics NM NM U-PP gossiping (informed) A NM - R Basic Gossiping * - - - U-PP gossiping (basic) P NM - R
* Basic gossiping is a pure dissemination technique and may be used to realized Publish/Subscribe systems. Thus, only general characteristics are given. Note that the classication of all dimensions depends on the specic implementation.

.

. Classifying Scribe and Gossiping

The two systems that are used during the thesis -Scribe and (basic) gossiping -are part of the exemplary classication in table .. The pub/sub system Scribe realizes a deterministic tree-based dissemination style on the network overlay, using the location-based routing service Pastry []. Hence, it is classied as a selective dissemination system with a rendezvous node and as S-PP in terms of overlay organization. Scribe uses topics and for subscription matching, maintained by a subscription table. The topic id is represented by a hash value (SHA-) of the textual topic name and the creator's name. TCP is used as message protocol, however, the actual event data model is kept implementation specic. Here and in the remainder, we assume commonly tagged formats such as XML or JSON. Although relying on TCP, Scribe implements (through Pastry) with periodic heartbeats an active adaption technique. Together with retransmissions in case of message losses (through TCP), the system provides QoS only to some degree in terms of reliability. Finally, specic communication techniques are not mentioned and Scribe provides no underlay awareness. Since basic gossiping is not a pub/sub but a pure dissemination system, the corresponding dimension are blanked out with "-" in table .. Nevertheless, to make it comparable to Scribe, we assume the same values (i.e. topic-based, tagged and a lookup table). Furthermore, it realizes a clique network and diers thus to Scribe in terms of the system architecture. By realizing a non-deterministic structure based on randomness it is classied as U-PP. Gossiping provides a passive adaptation techniques based on timeouts.

.. Taxonomy of Byzantine Failures

A taxonomy of Byzantine failures is introduced as further preparation for the review. The taxonomy is listed below is distinguishes between operation and message anomalies. To sup-port evaluations from a comprehensive point of view, the taxonomy consists of elementary failures, which may in turn lead to more enhanced failure scenarios.

• Operation Anomalies

-Link/Node unavailability: A communication link or peer is temporarily unavailable and can no longer interact with the system.

-Link/Node crash: A communication link or the whole peer crashes (with all links). It does not interact anymore with the system and needs to be restarted.

• Message Anomalies

-Delay: The forwarding of a message is delayed, the message is delivered later than expected.

-Information Leak: The message header and/or body are fully readable allow to draw conclusions as preparation for an attack.

-Loss: A message is lost while being delivered to subscribers (e.g. while being transmitted through a lossy link or at the peer between transmissions).

-Content Pollution: A message of arbitrary content (or type) is sent to a set of overlay neighbours, polluting the actual information in the system.

-Misusage: Protocol coherent messages are used in an arbitrary way (e.g. repeated sending), possibly disturbing the system function.

-Tampering: The message (header and/or body) is modied while being delivered but remains protocol coherent.

Information leaks are not directly a danger for the reliability but important with respect to privacy and security. The gained knowledge can be used to design a selsh strategy. Therefore, it should be prevented in addition to the other failures. Message Misusage is manifold and kept abstract here. An example is (in combination with Message Tampering) the sending of a falsied DNS response to get control over the address translation for a set of peers. These failures can cause more complex failure situations; some examples are the following:

• Catastrophic Failures: A specic failure appears simultaneously at a large number of peers. This may for example arrive for the failures Link/Node Crash, Message Loss or Message Tampering.

• Node Churn Attacks: Node churn represents actually the typical dynamics of a distributed system, i.e. joining/leaving peers. This can be exploited for system attacks by producing unnaturally high churn rates by continuously (mis-)using leave/join messages of a group of peers. Then, the system functioning is aected due to the extra resources and time needed for disseminating changes in the network.

• Network Partitioning: The overlay network gets split into independent networks due to crashes of a communication link or the whole peer. The events originating in a partition can no longer be transmitted to the others.

• Message Ordering: Messages are not received in the same order as they were sent.

. /

After introducing the preparations, we will review some works to evaluate their BAR tolerance capabilities. To this end, the evaluation model is described in the beginning. The evaluation is then presented and nally its meaning for system development discussed.

.

. The Simple Comprehensive Reliability Evaluation Model

The Simple Comprehensive Reliability Evaluation (sCRE) model enables a qualitative reliability evaluation considering the architectural classication and failures based on the taxonomy. This allows to draw conclusions between the system architecture and reliability aspects. Evaluations with the sCRE model are user-centric, i.e. the failures or architectural dimensions can be freely chosen. Nevertheless, the architectural dimensions Dissemination Technique and Overlay Organization should generally be considered due to their critical role in the functioning of the system. In addition, we also consider here the Subscriptions Type. The failures of the taxonomy of failures are adopted with the following modications. First, the failure Message Delays is not considered since resulting failure scenarios (e.g. Message Ordering) are typically not aecting the system's general functioning. In the context of the video streaming scenario, we assume some buers to compensate this failure. Moreover, as link and node crashes have a similar inuence on the system (a node crash implies the crash of all of its links), they are considered as one failure type. The dimensions used by the sCRE model are the following, which are shown on the right-hand side in the evaluation table .. The evaluation with the sCRE model is done in a qualitative way and comprises " " (yes) and " " (no) as possible values. A " " indicates the presence of techniques against the regarding type of failure but not does not necessarily guarantee that the impact is completely avoided/tolerated. The symbol " " is used if mechanisms for the corresponding failure are not implemented or not mentioned. This qualitative evaluation does not reveal the robustness capabilities but enable a visualization of the systems' reliability capabilities (i.e. considered failures during system design) in a clearly arranged way. Hence, it contributes to determine the current state-of-the-art by revealing reliability issues in terms of the thesis' vision.

.

. A Qualitative Reliability Evaluation

Several systems are evaluated that were proposed over the last ten years. The studied sample is composed of pub/sub systems and pure dissemination algorithms, selected based on their popularity (estimated from their number of citations), date of publication (more recent works were favored) and thematic representativeness. The results are presented in table .. Clear conclusions can be drawn from the evaluation. Almost all systems implement at best techniques against the common elementary failures link/node crash and message loss. Techniques against selsh behaviour are in general not considered. The only exception is Flight-Path, a dissemination algorithm for streaming applications, thanks to its implementation of the BAR model. However, a closer look reveals a number of clear limitations. FlightPath supports only one streaming source per multicast group and uses a tracker that is responsible for subscription matching (each of both, source and tracker, is assumed to be deployed on a dedicated peer). The message transfers are appropriately secured, however, the behaviour of the tracker peer is not. The reliability for the multicast groups can no longer be guaranteed if the corresponding tracker itself is malicious or selsh.

The evaluation reveals a dramatic situation, which is interpret as in the following. Distributed systems provide some inherent reliability capabilities (depending on the architecture). Further functionalities, e.g. to tolerate failure type C (Message Tampering) or F (Information Leak) are considered as optional and implemented on demand. However, some techniques or failure types such as E (Message Misuse) or G (Selsh Behaviour) require deep architectural modications. Thus, the consideration of reliability techniques as optional modules is not feasible in general. Furthermore, especially in complex systems, the interaction of the several implemented techniques can be hard to determine. This emphasizes the need for an approach that is abstract enough to cover the complexity but precise enough to take into account the specic techniques or selsh goals.

. The BAR tolerance evaluation developed before addresses the research challenge (A) of the thesis with the architectural classication related to (A.) and the taxonomy of failures related to (A.). In the thesis' research context, the evaluation (and the related work) showed that selfishness in distributed system is only slightly considered by some recent systems . It showed furthermore how reliability mechanisms are typically considered for distributed systems. Basic capabilities are a result of the system architecture. In contrary, the lack of reliability is usually interpret (taking approaches of the related work discussion into account) as the consideration of mechanisms as optional modules during system design. However, this is not always feasible due to possibly deep architectural modications. Several mechanisms in such complex systems can even interfere each other (e.g. redundancy and QoS). This emphasizes the need for more comprehensive reliability approaches as for example the one described in the thesis' vision.

.

RCOURSE: ROBUSTNESS STUDIES WITH THE PEERSIM SIMULATOR

This chapter introduces the RCourse library for the Peersim simulation environment. It targets to simplify simulative studies in terms of robustness of performance. Furthermore, RCourse enables to enrich the evaluation of the last chapter with quantifying information. Before detailing RCourse, two pub/sub algorithms are outlined. They are used for all exemplary simulations in this chapter and for the evaluations of the IG approach of part .

. /

Two pub/sub systems are detailed in the following that will be used in the remainder of the thesis and in the exemplary RCourse experimentation in particular. This is Scribe and a system based on basic gossiping. They dier signicantly in their dissemination style. In short, Scribe realizes an ecient dissemination but lacks in fault-tolerance mechanism. In contrary, gossiping has higher system inherent fault-tolerance capabilities but is less ecient due to some redundancy. This is illustrated in gure .. .. Scribe

The Scribe system [] is one of the rst pub/sub systems and realizes topic-based application layer multicast. The routing on overlay level is done by the id-based routing service Pastry [], realizing a dissemination with O(logN) forwarding steps to the target peer. Scribe is characterized by a deterministic structure, i.e. it uses deterministic algorithms to calculate the next hop on the dissemination path. This deterministic structure leads to a tree-based dissemination approach, which is also denoted as rendezvous node -or r-node -based approach.

1 Process calls publish operation to a specific group 1 Process calls subscription operation to a specific group 2

Message is sent to next forwarder node (on the route to the rendezvous node) and to subscribed children nodes 2

Subsciption is sent to next forwarder node (on the route to the rendezvous node), which updates his subscription table 3 Message is forwarded to subscribed children nodes 3 Rendezvous node updates his subscription table

Operation: Publish to Group Operation: Subscription to Group Here, publisher and subscriber send their messages to the r-node, making it to the root node of a tree for one multicast group. Thus, the r-node is responsible for subscription matching in last instance. A peer holds implicitly the role of a rendezvous node for a specic multicast group if his overlay id is equal or the closest one to an identier, which is typically a hash value of the topic descriptor of the multicast group. Figure . shows the dissemination principle of the Scribe system exemplary for two operations, the subscription and publishing. If a peer on the route to the r-node receives a subscription, he adds the subscribing peer to his subscription list. Afterwards, he subscribes himself to the group. If a peer on the route to the r-node receives a published event message, it its further transferred to the r-node but also to interested peers in the subscription list (if any). The functioning of the Scribe system should only be outlined here; the reader is referred to [] for further specic details. Scribe has been chosen due to its ecient dissemination technique. In other words, it has only limited fault-tolerance capabilities (only link/node crashes) and no further redundancy techniques are implemented. Therefore, the impact of faults is directly shown without being moderated by fault-tolerance techniques.

.. Gossiping

Gossiping is an information dissemination protocol, which relies on the fundamental manner of epidemic algorithms [, ]. It is characterized by a non-deterministic structure, which makes use of some randomness during dissemination (dynamic dissemination structure). Hence, the message delivery can only probabilistically be guaranteed.

Current approaches (e.g. [, , ]) have only a partial view on the network containing possible candidates for a message transfer. It is maintained by membership protocols, which provide a peer sampling service [, ]). In an optimal case, all partial views should form a connected random graph. Hence, membership protocols are a critical component for the dissemination quality several approaches were developed in the in recent years. [, ]. The partial view typically holds additional information such as the subscriptions of a peer, which are exchanged during the procedure of the membership protocol.

The dissemination diers mainly in the way how these peers are chosen from the partial view for a message transfer. Two general types are basic and deterministic gossiping. In basic gossiping, the peers are randomly selected for the message transfer. In contrary, informed gossiping combines the probabilistic manner with a deterministic structure. Typically, the dissemination is done to randomly chosen peers (r-links) and to deterministically chosen peers (d-links), illustrated in gure .. The RingCast approach [] uses for example the d-links to create a dissemination ring (to guarantee a delivery), while r-links speed up the delivery.

Two parameters (see also []) are crucial for the performance of gossiping systems:

• Fanout: The fanout value denes the amount of peers, which are chosen from the partial view as target for the dissemination of a message. Typical fanout values are aboutfor informed gossiping andin basic gossiping. Then, a delivery is probabilistically guaranteed []. A probabilistic calculation of the delivery is given in [].

• Maximum Rounds: This value denes, similarly to the Time-To-Live (TTL) value in IPnetworks, how long a message shall circulate in the network. Therefore, it means a trade-o between resource usage and delivery probability.

The random dissemination of basic gossiping results in a homogeneous load distribution. Furthermore, the redundancy in dissemination creates inherent fault-tolerance capabilities. Due to these reasons, basic gossiping is used in the remainder of the thesis for all experimentations.

Cyclon [] is used as membership protocol due to its frequent usage in research works.

.

In contrast to the BAR tolerance evaluation, a system designer must -due to the given diversity -concentrate on a subset of selshness-driven violations that shall be considered. To this end, he chooses the corresponding reliability mechanisms, which are parametrized with regard to the designers' objectives, i.e. the targeted collaboration level. This is challenging since the mechanisms may interact each other and the given systems have dierent inherent reliability capabilities. Hence, in order to develop BAR tolerance mechanisms, a system designer must examine the system behaviour in presence of failure situations and reliability mechanisms. A typical way to do this are simulative studies.

In this context and to reach the main research challenge, a design principle was mentioned in the introduction (see section ., page ). A mutual feedback should be considered between the practical system behaviour evaluation and the theoretical model of reliability mechanisms. In other words, a simulation determines the impact of failures or selshness-driven violations on the system behaviour and enables to adjust the mechanism parameters correspondingly. By easing simulative studies, RCourse represents the practical side of this design principle. To be more specic, the practical side of this design principle must enable the system designer to perform the following tasks:

• Evaluate the isolated impact of failures caused by specic selshness-driven violations on the system behaviour considering or not reliability mechanisms.

• Evaluate the system behaviour under user specic circumstances (e.g. dynamics) considering or not reliability mechanisms.

The system designer uses simulations as a tool within the development process of BAR tolerance mechanisms. The following design principles are formulated to meet the designer's practical needs in terms of the main research challenge.

.

Simplicity of utilization

Performing simulations shall be simplied as much as possible to provide time and work gains. Ideally, they should be able to be launched once the peer logic is implemented.

.

Isolated failure evaluation

The impact of specic failures (comprising also selsh behaviour) on the system behaviour shall be evaluated independently from others.

. Adaptability to individual needs Due to the diversity of selshness-driven violations, a system designer shall be able to easily adapt the simulation to individual needs.

Several simulation environments are available to meet these principles, each one providing individual characteristics; examples are Omnet++ , PlanetLab , ns-or NetSim . The Peersim simulator [] has been developed for the study of overlay networks in particular. Since pub-/sub realizes overlay networks, it is a good option for the evaluations in this thesis. Peersim omits the simulation of the actual network stack and is as open-source software available for free usage. However, there is currently no extension for statistical result aggregation and analysis available for Peersim. Thus, performing network simulations requires additional work to obtain practically usable results. Furthermore, no benchmarking application for Peersim specically targeting robustness is available. RCourse serves as an approach to ll this gap.

. .

Enriching the simulation environment Peersim, RCourse contributes to meet research challenge (B) and the design principles stated before. Therefore, RCourse targets to simplify simulative studies with a special focus on robustness and performance aspects. Although it is especially prepared for studies on pub/sub systems (for example, it comes with several preimplemented pub/sub algorithms), it is designed to be easily adaptable to evaluations of PP systems in general. RCourse is, as Peersim, freely available under the GPLv open-source license and downloadable at the Sourceforge project page .

.

. Design Goals

The development of RCourse strictly considered the following four design goals, which are directly based on the principles mentioned before.

. Time/work savings As many tasks as possible shall be automated in order to spare work/time to the user.

. Architectural modularity Each step of a simulative study shall be adaptable to specic user needs.

.

Stand-alone simulations in terms of robustness and performance

The RCourse library shall enable complete simulative studies in terms of robustness and performance without requiring other software products or further calculations.

. Free tool for research community RCourse shall be designed as a free tool and available under an open-source license.

Figure . illustrates the simulation workow with the supported steps by RCourse (continuous lines) as well as the possibilities for individual adaptations (dashed lines). RCourse enables time/work savings (goal .) already beginning with the rst workow step -the development of the dissemination algorithms that shall be simulated. By means of a set of Java classes, RCourse provides among others functionalities for data aggregation and write-out. Thus, the user can concentrate on the development of the algorithm itself, all other steps may be taken over by RCourse components. Further support is given for example by means of pre-dened simulation scenarios and scripts in the R programming language. They analyze the simulation result data set and automatically generate result graphs as pdf les. The design goal . was reached by modularizing the RCourse components among the workow steps. This loose coupling results in a modular architecture and facilitates the adaptation of the dierent steps to user specic needs. In order to fulll goal ., the RCourse library is complete in the sense that a simulative study can be directly launched once the algorithm development is completed. Indeed, two pub/sub systems have been developed for use with RCourse, which are included in the library. These are Scribe and gossiping that were described before. RCourse provides a basic as well as informed gossiping implementation, based on the membership protocols Cy research community. Thus, in order to fulll design goal ., it makes only use of free software -indeed, this is only Peersim and the programming languages Java as well as R -and is itself published as open source under the GPLv license. As mentioned before, the RCourse library as well as additional les (scenario/graph overview, example result les etc.) are available for download on the RCourse project homepage.

.. RCourse Components

RCourse is realized as a loose coupling of basically three components:

• A set of Java classes support the user among others in value aggregation and write out as SQLite result les.

• Pre-dened simulation scenarios can be directly used to simulate and evaluate a system after nishing the development of the dissemination algorithm.

• Analysis scripts (written in the R programming language) aggregate the SQLite result les, analyze the data and generate result graphs as pdf les.

A simulation that makes full use of these components is completely reduced to the development of the dissemination algorithm. For a given algorithm, the development concerns basically the implementation of a measurement value aggregation and write-out. Simulations can then be executed using the pre-dened scenarios and result graphs created by means of R analysis scripts. These components will now be explained in more detail.

The Java classes of RCourse mainly provide six essential components. They are indicated in gure . and outlined in the following.

• The class RCParamStorage holds simulation-wide conguration parameters as well as other global values and is accessible by the peers.

• RCTracGenerator and RCTurbulenceGenerator are helper classes for the simulation:

RCTracGenerator generates an appropriate workload and RCTurbulenceGenerator creates dierent stressful situations such as crashing nodes and node churn. • The class RCStatsCont represents the container for measurement values. It must be maintained by each simulated peer in order to record measurement values.

• The RCObserver plays a key role in RCourse. It collects at specied time points all measurement containers and passes them to the RCResultWriter.

• The RCResultWriter class extends RCResultWriterBase (not shown in gure .) and generates the SQLite result le (as well as the csv le output if dened in the conguration).

To make a Peersim algorithm compatible with RCourse, a user needs to maintain the RC-StatsCont and RCParamStorage objects. The interaction with the other classes such as RC-TracGenerator is realized through a Java interface (that also needs to be implemented) and specied in the conguration les. For more details, please refer to the reference implementations of RCourse, which are available on the project's website.

In order to enable quickly launched simulations, the RCourse provides a set of simulation scenarios as Peersim conguration les. For each considered failure type, they consist of one or more Experimentation Scenarios. Each such scenario enables the automated generation of some result graphs. The term simulation scenario is also used as synonym to Experimentation Scenario in the remainder of the thesis. An overview of these scenarios is shown in table .. Appendix A (see table A., page ) details these scenarios by providing all possible result graphs of RCourse in list form. The scenarios are based on the failure types of the BAR tolerance evaluation. However, the two failures D (Content Pollution) and F (Information Leak) are ignored. The reason is that they can easily be avoided by techniques such as access control or cryptography mechanisms. The scenarios are simplistic to some degree to enable drawing conclusions from the specic failure. For representative results, the use of real world workload and failure traces is recommended, e.g. those of the Failure Trace Archive . RCourse but an implementation is facilitated thanks to the architectural modularity: only the RCTracGenerator as well as RCTurbulenceGenerator need to be adapted.

RCourse provides scripts in the programming language R to process the simulation result analysis. This concerns basically the read-in of SQLite data les for an automatic graph generation. All analysis scripts have been developed corresponding to the pre-dened scenarios. One script initiates the analysis for each scenario , while several les are responsible for the graph generation. The analysis is be structured into four general phases, which are shown in gure .. In phase (I), the user initiates the analysis for a simulation scenario by calling the corresponding analysis script, which invokes further script les. Phase (II) is dedicated to the accomplishment of two important tasks. First, the simulation result les are read-in. Second, further information such as variance or standard variation are calculated for all numeric values. These information are then directly used for the graph generation in phase (III). As an example, the script for the Experimentation Scenario ES. considering a Loss Rate Variation (LRV) in terms of message loss is shown in the appendix in listing A. (page ). After phase (III), all result graphs are available and can directly be used for presentation purposes. As an impression, a sample result graphs are shown in the next section in gure . (page ).

. After an outline, we focus now on the practical utilization to launch simulations.

The scripts have the naming scheme diRgrams_*.r, with '*' being replaced for a specic scenario. Please note that this gure is a simplied visualization to convey the logical process. .

. Utilization and Experimentation

The setup and utilization of RCourse is now detailed among all steps of the simulation workow. This is done by means of the scenario ES. Message Loss with Loss Rate Variation, which corresponds to the example scenario of the introduction.

:

The RCourse library consists of three folders, each one providing the content for a RCourse component. The Java classes are stored in folder src/, the scenario denitions in cong/ and the R analysis scripts in folder analysis/. The Java classes need only to be referenced in the Peersim project and the scenario denitions are used by specifying them when launching a simulation. Similarly, the analysis scripts are used by calling the appropriate one within the R user interface. Thus, a typical RCourse library setup may consist of just copying the RCourse folder into the simulation project folder and calling/referencing the les when needed.

A crucial task is the source code extension to record measurement values. To this end, each peer must maintain a RCStatsCont container object and implement all method calls for value aggregation. Figure . shows the interaction with the data container for three examples with the Scribe system, indicating the RCourse related code in blue/italic. The shortest example (bottom-right in gure) records the amount of published messages and the medium one (up-right) the actions when an unsubscribe message is received. This is the counter of received messages and a counter for overlay hops. The biggest example (left in gure) shows the recording of the message dissemination time in terms of overlay hops as well as the delivery completion as a percentage. Please note that RCourse provides two types of calculation for the latter value. The simple method uses the conguration parameters to calculate the number of packets that should be delivered. Here, the message publishing must start after a subscription phase (plus some stabilization time) to provide correct values. The complex method calculates delivery completion based on the current situation of subscriptions and published messages in the system. Therefore, it is slower and computationally more intensive but also more suitable for dynamic workload situations such as node churn.

The three examples only outline the interaction with RCourse in the Java source code. For more information, the reader is referred to the source codes of the exemplary applications to the Scribe and gossiping systems (see project website indicated in footnote before). • cong/rcourse_Base.txt

This conguration le denes the general network setup and the structure of each peer's stack of protocols.

• cong/Scribe/ES.-MessageLossLRV.txt

The second cong le represents the scenario and comprises all scenario-related parameters such as time steps for the observer execution or workload generation.

• rcourse.distrProcId = 1

The distrProcId parameter denes the id for the current simulation in case of parallel processing. See section .. for more information.

Important are the terms simulation run and experiment repetition. A simulation run means the execution of one simulation with a specic set of parameters. An experiment repetition represents the execution of a simulation scenario as a whole, which may consist of multiple simulation runs. The amount of simulation runs is automatically calculated based on the conguration le (experiment repetitions times the amount of parameter sets caused by possibly specied value ranges). Each run is processed independently from the others. Furthermore, a generated SQLite le encapsulates all results of one experiment repetition.

To launch simulations, RCourse must be executed with peersim.rangesim.RangeSimulator as main class instead of the default class peersim.Simulator. This is due to the fact that several To start the analysis of simulation results, scenario scripts need to be called (stored in folder analysis/ ). Each of them is related to an Experimentation Scenario and responsible for the generation of all related graphs. Scenario scripts have the naming scheme diRgrams_*.r, with "*" being replaced by the corresponding scenario abbreviation. For example, the script le diRgrams_ES..r is related to Experimentation Scenario ES.. Scenario scripts make use of further scenario congurations, that are also prepared as R scripts (stored in folder analysis/cong/ ). Furthermore, some default values being dened in analysis/util/default_values.r. These les should be checked before starting the analysis process. As example, the le diRgrams_ES..r is shown in listing A. on page . After a successful execution, several result graphs are generated as pdf les. Figure . shows three examples, which have been generated with the Scribe system []. These graphs serve only as an impression; graphs for all scenarios (Scribe and basic gossiping) are available on the RCourse project page. The upper graph in gure . is related to the prior discussed example scenario ES., showing the graph D. Delivery Loss Rate with the amount of malicious nodes in the systems on the x-axis and the delivery loss on the y-axis.

.. A Note on Multi-Process Simulations

Modern processors have multiple cores and/or central processing units (CPU), a feature that could be used for simulations by implementing parallel processing. However, Peersim only allows the single-threaded execution of a simulation. RCourse enables parallel processing through a parallel execution of independent simulation runs. This can even take place on dierent machines by means of parallelizing experiment repetitions. This workaround makes sense since a simulation should be repeated several times to achieve representative results. Let us assume for instance that we have ve cores at our disposal and a simulation that should be repeated ten times, i.e. ten overall experiment repetitions. For the sake of simplicity, it is assumed that each experiment repetition consists of only one simulation run. Then, each core

: • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 0 50
• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • sum forwarded received direct sent
RCourse Benchmark -ES1.1 Standard Operation -D2.6 Node Stress Distribution (sorted)

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 0
• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •

Selfish Message Loss

RCourse Benchmark -ES8.1 Selfish Message Loss -D5.1 Delivery Loss Rate

• dropMsgProbability p=1.00 (3/3) dropMsgProbability p=0.66 (2/3) dropMsgProbability p=0.33 (1/3) Figure .

: Some example graphs are shown for the Scribe [] system, which have been generated with RCourse. This is the (sorted) node stress distribution (upper graph), the distribution of subscription table entries (middle graph) and message loss due to selshness-driven message drops (bottom graph).

.

.. Adaptation to Individual Measurements

RCourse records already a wide range of measurement values, which are clearly arranged in the le RCResultWriter.java. In addition, it is specically designed to be easily adaptable to individual values. To this end, one may extend the RCStatsCont data container. Then, only two components of RCourse have to be modied to let it record a new value. First, the RCStatsCont class must be extended by the new value to be recorded. This may also include appropriate methods to add data to the container object. Please note that the RCStatsCont.mergeStats(...) method may have to be modied as well depending on the value type. It is called by the RCObserver to merge the statistical values of all peers into one data container with global values (e.g. summarized counter values). Hence, it must be adapted if the new value considers network-wide values such as the average dissemination delay or even more complex data structures (linked lists, vectors etc.). The second component to modify is the RCResultWriter class, which is responsible for writing out all values. The required modication consists in adding the new value as an additional database column. Finally, the scripts for read-in, data analysis and result graph generation must be adapted to make use of the new value(s).

:

.

RCourse meets research challenge (B) by simplifying each step in the simulation workow. This eases simulative studies with a focus on fault-tolerance issues. Providing simulation scenarios related to specic failure types, robustness evaluations can be quickly launched. This is now illustrated by a short evaluation. As before, we consider again the simulation scenario ES. Catastrophic Message Loss. It corresponds to the video streaming scenario with selshness-driven message drops mentioned in the introduction. The results are shown in gure . for Scribe (upper graph) and basic gossiping (lower graph). Message loss indicates the violation probability, e.g. . means to collaborate only for . (%). The lack of Scribe's fault-tolerance results in a fast decrease of the system functioning. In contrary, the redundant dissemination of gossiping can tolerate the failures to some degree. This changes at a loss rate of about % where the delivered messages decrease dramatically. This short study illustrates the benet of RCourse to reveal the individual robustness capabilities. Furthermore, it shows the need for individual targeted collaboration levels, as dened for challenge (C).

RCourse contributes also to challenge (A) thanks to the pre-dened scenarios that base on the BAR tolerance evaluation of the last chapter. It enables to enrich the still qualitative evaluation with quantitative information. This is exemplary shown in table . using the . This chapter introduced the RCourse library that meets research challenge (B). After a short outline, its components were described as well as the utilization to perform simulative studies. Two pub/sub algorithms were detailed in the beginning of this chapter -Scribe and basic gossiping. They were used for all exemplary result graphs and will also be used in the remainder of the thesis. The RCourse library targets to support the user in performing simulative studies of distributed systems' robustness and performance. By focusing only on the logic implementation -the rest is take over by RCourse -the user is able to quickly achieve simulation results.

Part IV ACHIEVING COLLABORATION WITH INSPECTION GAMES

This part is dedicated to the solution approach for research challenge (C), i.e. enabling a system deployment over selsh peers. To this end, a basic two-player Inspection Game (IG) is at rst adapted to the needs of distributed systems. Then, some practical issues for an application to distributed systems are discussed in chapter . A solution approach for challenge (C) is introduced in chapter , which is enhanced in chapter by the capability to adapt to system dynamics. Finally, we discuss the real world applicability of the IG approach.

ADAPTING INSPECTION GAMES TO THE NEEDS OF DISTRIBUTED SYSTEMS

The utilization of Inspection Games (IG) as solution approach for distributed systems was argued in the introduction (see section . in particular). However, the related work discussion demonstrated that there is currently no appropriate IG model available. Therefore, this issue is addressed now by adapting the basic IG to our needs. To this end, the considerations comprise the extension by false negatives (non-detected violations) as well as generalizations up to games with m inspectors and n inspectees. All derivations are based on the basic two-player IG, which is introduced in the beginning.

.

The IG is now detailed in its initial form as introduced by Dresher []: a two-player zerosum game. It is denoted as G(1, 1) in the remainder. An Inspection Game (IG) consists of two players: the inspectee and the inspector.Astrategy for a player is a complete plan of actions throughout the game. The goal of every player consists in adopting a strategy that maximizes his own payo, which represents the outcome of the game. Each player takes into account that it depends also upon the other players' chosen strategy. The Nash equilibrium (NE) is a solution that describes a steady state condition of the game. It corresponds to a combination of strategies, a strategy prole, such that no individual player would be better o by changing his own strategy unilaterally.

Game Setup

The inspector's set of strategies is { Inspect , Do not inspect }, i.e. he can choose between inspecting or not. Analogue, the inspectee represents the selsh peer and can choose between violating or not with the strategy set { Violate , Do not violate }. The players have to choose their strategy simultaneously (or equivalently such that they do not have any hint about the other's move before their own move). With real world distributed systems in mind, we do not use zero-sum payos but use more realistic ones. To this end, we assume for the sake of simplicity the following:

. The case without violation and without inspection does not bring any damage nor benet to any player.

. Violation will bring the inspectee a positive benet b if not detected but, if detected, it will bring him also a loss -a with |a| > |b|.

. The inspection has a xed cost -c for the inspector, but not detecting a violation would cost him a damage -d with |d| > |c|. Table . indicates the four possible states of aairs and the corresponding payos for the players. In each cell, the pair (x, y) means that the rst player (the inspectee) obtains a payo x, while the second player (the inspector) obtains a payo y. The table represents the IG in the so called normal form: the rows correspond to the possible moves of the inspectee (the inspectee's pure strategies), the columns correspond to the possible moves of the inspector (the inspector's pure strategies). The structure of the game can also be represented in extensive form as shown in gure .. Since b > 0 and 0 > (ba), the inspectee will prefer to violate when the other does not inspect and not to violate when the other inspects. Conversely, since -c > -d, the inspector will prefer to inspect when the other violates and not to inspect when the other does not violate.

Game Solution: Nash Equilibrium at Indierence Strategies

Due to the circular structure of the players' preferences, they cannot determine in advance their own best pure strategy. They have to resort to a suitable randomization between the two choices so as to maximize the expected payo, taking into account that the other will act accordingly. In other terms, each one will have to adopt a mixed strategy (dened by a probability distribution over the pure strategies). This mixed strategy will have to force the other party into adopting a strategy from which he has no incentives to deviate. This joint mixed strategy will represent the NE of the game. Each party's strategy at equilibrium is also called indierence strategy. This is due to the fact that the other party's expected payo will not change whatever mix of his own pure strategy is adopted. For example, let us consider the situation where an inspector chooses a mixed strategy that induces indierence in the inspectee. Then, all strategies of the inspectee will result in an equal payo for the inspector.

Table .: The payo matrix for the basic Inspection Game shows the four possible results.

I

Inspect

Do not inspect

I Violate ( b -a , -c ) ( b , -d ) Do not violate ( 0, -c ) ( 0, 0)
. Suppose now that the inspectee adopts the violation choice with probability p, and that the inspector adopts the inspection choice with probability q. Then, the solution of the game can be found by computing the pair (p, q) with is characterized by the following. Neither the inspectee can change his expected payo by deviating from p, nor the inspector can change his expected payo by deviating from q. If the inspectee wants to induce the indierence in the inspector, he will have to set his own parameter p so as to equalize two aspects. This is the expected inspector's payo for an inspection and the inspector's payo for lack of inspection. Similarly, if the inspector wants to induce the indierence in the inspectee, he will have to set his own parameter q so as to equalize the expected inspectee's payo for a violation and the inspectee's payo for lack of violation. Altogether we have (-c)=p (-d) q(ba)+(1q)b = 0 from which we get the simple solution ( p ⇤ , q ⇤ ) given by

p ⇤ = c d q ⇤ = b a
Notice that q ⇤ is determined by the quantities dening the payos of the inspectee. In the expression, the benet b for an undetected violation competes with the loss a for the detected one. Similarly, p ⇤ is determined by the quantities dening the payos of the inspector and the cost for an inspection plays the opposite role to the avoided damage d. It is worth to remark that the expression for q ⇤ is a legal expression for a probability only if a ≥ b. Analogue, the expression for p ⇤ is a probability only if d ≥ c, which is granted by the denition of the game.

. Distributed systems consist of multiple participants and works in the GT literature present indeed game models with multiple inspectees. For example, Avenhaus and Kilgour [] discussed a three-person non-zero sum IG with one inspector and two inspectees. However, the environmental setting is more complicated than the one of the thesis' monitoring approach.

They study how the game's equilibrium depends on the convexity/concavity of a function representing the inspection eort. Another work worth to mention with regard to a generalization is the contribution of Hohzaki []. It is formulated in the context of the International Atomic Energy Agency (IAEA) and directly based on the aforementioned paper of Avenhaus and Kilgour. Hohzaki introduces an IG with n inspectees and the complex situation that an inspector is characterized by several attributes (e.g. nationality). Then, the game model aims to calculate an optimal assignment (partitioning) of the inspection eort to the inspectees, i.e. certain facilities in an inspectee's country. However, the eort cannot be partitioned in our simpler case. Due to these dierences, the given models do not fulll our needs of a mere generalization of the basic IG. These IG models G(,n), G(m,) and G(m,n)) are presented now with a straightforward re-derivation of the solutions.

.. Game G(, n) -One Inspector, n Inspectees

Game Setup

Let us consider now a (n + 1)-player simultaneous single-round IG, which consists of one inspector and n inspectees. It has the same three payo assumptions as the basic one (see list in game setup section). As in the basic IG, q indicates the probability that the inspector decides to perform the inspection. Then, the inspection is done on a single randomly chosen inspectee and each inspectee has a probability 1 n to be inspected. The inspectees, from now on inspectee 1,•••, inspectee n, have respectively probability p 1 , ••• , p n of violating the rule. The solution of this game is represented by the values of q ⇤ , p ⇤ 1 , ••• p ⇤ n of the above (n + 1) parameters at the NE. For the sake of comprehensibility, we assume a symmetry between the inspectees, i.e. the same solution parameters

p ⇤ = p ⇤ 1 = ••• = p ⇤ n .
The tree diagram in gure . shows the dierent game result possibilities for n = 2.

Game Solution

An important point for the solution is that there is no coupling between inspectees. An inspectee's payo does not depend on the other inspectee's choices. Furthermore, this game does not have, in general, Nash equilibria in pure strategies. Therefore, the players have to nd the equilibrium in mixed strategies. The inspectees have to choose the strategy which induces indierence in the inspector. The inspector has to choose the strategy which induces indierence in the inspectees. The results can be derived through simple considerations.

' The inspectees have to equalize the expected inspector's payo for an inspection to the inspector's payo for lack of inspection. This means that p ⇤ will have to satisfy the simple equation equalizing

• the impact (value times probability) on the inspector for undetected violations due to lack of inspection

• with the balance between the impact of an unfruitful inspection and the one of a fully or partially successful inspection.

The impact for no-inspection is given by the expected number of the violations of n inspectees times the damage d created by each one: i.e. by np ⇥ d. The impact for inspection is given by the constant cost c plus the impact of the undetected violations. In this case, the inspector is securing with certainty only one inspectee. Hence, the impact of the undetected violations is given by the expected number of violations p of the remaining inspectees. The inspection impact is therefore c +(n -1)pd. Notice that the optimal p is the same as the one for a single inspectee: the presence of further inspectees does not change the best strategy of one inspectee. This is is a natural consequence of the lack of coupling between inspectees.

' Analogue to the inspectee, the inspector needs to make each inspectee indierent. To this end, he equalizes the expected payo for the inspectees' violation and the expected payo for non-violation. Looking at the structure of the game one can observe that they consider the inspection to another inspectee as equivalent to no inspection at all. Hence, the inspector has to behave as if each of them were playing against him an eective two-player game G(1, 1) game with rescaled parameters. We can describe this eective game by introducing an eective probability of inspection q ef f = q n . The extensive form of this game is the same as the one shown in gure . except that the probability q is substituted by q ef f = q n . The inspectee's indierence is obtained equalizing the impact for non violation, which is null, to the impact of violation. The latter one is given by the balance between the detected one and the undetected one. In case of a violation, there will always be a benet for the inspectee. The impact is therefore given by b added to the impact of the loss (loss times probability of inspection

q ef f = q n ). The indierence equation is b -a q n = 0 hence q ⇤ = b a n
The factor 1 n results from the fact that one inspector is shared by two inspectees. As mentioned before, there is no inuence on p due to the lack of coupling among the inspectees. The presence in q of a factor n represents the situation where each inspectee can see this IG as a two-player game with eective loss a n .

.. Game G(m,) -m Inspectors, One Inspectee

Game Setup

Beside the assumptions . to . already adopted so far, we are also forced to postulate some coupling between inspectors. They must share the damage of any occurring violation which goes undetected (i.e. detected by none). A detailed formulation is represented in gure . in extensive form for the exemplary case of m = 2 inspectors and n = 1 inspectee.

Game Solution

We can exclude the possibility of NE in pure strategies because all the pure strategy proles have at least one player which would benet from switching strategy unilaterally. The inspectee would prefer to violate when no inspection occurs and each inspector would prefer to inspect when there is a violation. We will exploit the symmetry between the inspectors since we know that the equilibrium is of the form q

⇤ 1 = ••• = q ⇤ m = q ⇤ .
' The equation for the inspectee's indierence should equalize the impact for no violation, which is null, to the impact for violation. This in turn is given by the balance between the impact of detection and that of non detection. Since the benet for violation is always present (be the violation detected or not), the balance is obtained by subtracting from b the impact of loss only (probability times value of loss). The probability of detection by at least one of the inspectors is 1 -

(1 -q) m , hence the overall indierence equation is b -a(1 -(1 -q) m )=0
which has solution for q ⇤ such that

(1 -q ⇤ ) m = 1 - b a
and therefore

q ⇤ = 1 -(1 - b a ) 1 m .
which has solution for

p ⇤ = c d (1 -q ⇤ ) m-1
or explicitly -taking into account that at the equilibrium value (1

-q ⇤ )=(1 -b a ) 1 m -for p ⇤ = c d (1 -b a ) m-1 m .. Game G(m,n) -m Inspectors, n Inspectees
In the game with m uncoordinated inspectors and n (non interacting) inspectees, the presence of n inspectees reduces the probability of any inspector visiting the i-th inspectee from q i to q ef f i = q i n . Hereafter, exploiting the symmetry among inspectors, we will use q in place of q i . Exploiting the symmetry among inspectees, we will use p in place of p i .

' The indierence equation for each inspectee, which is used here to determine q, is b

-a(1 -(1 - q n ) m )=0 which has solution for (1 - q ⇤ n ) m = 1 - b a and thus q ⇤ = n 1 -(1 - b a ) 1 m
The result is analogue to G(m,1) except that q is replaced by the eective q ef f = q n .

' The inspectors' indierence equation which is used here to determine p, should equalize

• the impact of no inspection. This corresponds to d times the expected value of the number n of inspectees' violations going undetected by the other (m-) inspectors.

• the impact of inspection. This is given by a constant cost plus the individual damage times the expected value of the number (n-) of inspectees' violations going undetected by the other (m-) inspectors.

In both cases, the answer depends on two aspects. This is the expected number of undetected violations when each inspectees violates the rule with probability p and that each inspector performs an inspection with probability q -a quantity which we can call u(m, q, n, p). The indierence equation will equate the following two impacts du(m -1, q, n, p)=c + du((m -1), q, (n -1), p)

which can be rearranged so that c d = u((m -1), q, n, p)u((m -1), p, (n -1), q)

The dierence at the second member represents the expected number of extra undetected violations, which occur when an inspector does not inspect. The missing inspection does not produce any extra undetected violations if the peer, which would be inspected, does not violate the rule, or if that peer is already inspected by the other inspectors. In other words, the missing inspection leaves one extra inspectee violating undetected only when that inspectee does perform the violation and the other (m -1) inspectors do not detect it. The former event happens with probability p and the latter with probability (1 -q n ) m-1 (since each inspector has probability q n of falling over that inspectee). Hence the indierence equation is

c d = p(1 - q n ) m-1
and has solution for

p ⇤ = c d
(1 -q n ) m-1 Overall, substituting q ⇤ , we have

p ⇤ = c d (1 -b a ) m-1 m
To summarize results of this section, the solution for all games are listed in table .. Notice that the p ⇤ of the various G(•, n) is equal to that of the corresponding G(•,1). Adding or removing inspectees does not change the p ⇤ because there is no coupling between inspectees. On the contrary, the q ⇤ of the various G(•, n) is n times larger than that of the corresponding G(•,1). Multiplying the inspectees' number by n does change q ⇤ since it requires a proportional increase in the inspectors' eort. Notice as well that both p ⇤ and q ⇤ of the G(m, •) are reduced with respect to the corresponding G(1, •). This is coherent with an increased and joint inspectors' pressure.

Table .: Solutions for all IGs up to m inspectors and n inspectees. p ⇤ indicates the inspectee's equilibrium violation probability and q ⇤ the inspector's equilibrium inspection probability.

p ⇤ q ⇤ G(1, 1) P ⌘ c d Q ⌘ b a G(1, n) P nQ G(m,1) P (1-Q) m-1 m 1 -(1 -Q) 1 m G(m, n) P (1-Q) m-1 m n 1 -(1 -Q) 1 m .
In real-world applications, a system designer is faced with limited resources (e.g. limited processing or memory capabilities of machines in distributed systems). Thus, violations are possibly not detected during an inspection, denoted here as false negatives. This is addressed . now by enriching the four IGs by a nite probability of non-detection. The enriched version of the game with one inspectee and one inspector G(1, 1) is exemplary shown in gure .. Similar extensions can be devised for the others. We will indicate the corresponding games with false negatives by Γ(•, •). Their NE can be found by straightforward considerations. Let us indicate by g the probability that an inspection does detect a violation that actually occurred. False positives are assumed to be not possible. When an inspection detects a violation, there is no doubt that the violation occurred.

A rst key observation for the development of the more general cases G(•, •) concerns the inspectee's indierence equation used to determine q ⇤ . Whenever an inspector sets the probability of inspection to the value q, the inspectee perceives an eective probability gq. Notice that due to this fact, all values q in the equations for the G(•, •) are substituted by gq in the equations for the Γ(•, •). Thus, the equilibrium values q ⇤ for the inspectors in all the games G(•, •) will be rescaled by a factor 1/g. For this reason we have to discuss in detail only the inspector's indierence equation in the following cases.

.. Game Γ(, ) -One Inspector, One Inspectee

The equilibrium equation for the inspector in Γ(1, 1) changes slightly with respect to G(1, 1). The payo for the inspection is not simply (-c). Instead, it is decremented by the term (-d)(1g)p due to possible inspection failure. The overall indierence equation is thus

-c +(-d)(1 -g)p =(-d)p or c = pdg . It has the solution p ⇤ = c gd
valid for gd ≥ c. As anticipated above the solution value for q, valid for ga ≥ b, is instead

q ⇤ = b ga
The solutions p ⇤ and q ⇤ are equal to the solution values for G(1, 1) rescaled by a factor 1/g. This represents an increased violation rate and a correspondingly increased inspection rate. .. Game Γ(, n) -One Inspector, n Inspectees

For the inspector's indierence equation in the game Γ(1, n), we have the non-inspection side npd of the equality. This represents the expected value of the damage from a set of n independent inspectee choosing to violate with probability p. The inspection side consists of the inspection costs also present in G(1, n), i.e. c + d(n -1)p, plus the failed inspection term (1g)pd. Hence, the indierence equation is

npd = c + d(n -1)p +(1 -g)pd ⌘ pd = c +(1 -g)pd
which is equivalent to gpd = c. It provides the solution

p ⇤ = c gd
As anticipated above, the solution value for q is instead

q ⇤ = n b ga
Again, the two solutions p ⇤ and q ⇤ are equal to those of G(1, n) rescaled by a factor 1/g.

.. Game Γ(m, ) -m Inspectors, One Inspectee

Anticipating the prior results, the solution value for q ( inspectee's indierence) is such that

(1 -gq ⇤ ) m = 1 - b a
and its explicit form can be found in table .. As for p, the inspector's indierence equation should equalize the impact of inspection to the impact of no inspection. The latter term corresponds to the expected impact of the violation (probability times impact) by the only inspectee when no other inspector performs a successful inspection. This is represented by (-d)p(1gq) m-1 , while the successful inspection has probability gq. The impact of an inspection is given by the constant cost (-c) plus the expected inspection failure. For the latter one, there is only a damage (-d) if the inspectee violates (probability p), the inspection fails (probability 1g) and no other inspector performs a successful inspection (probability (1gq) m-1 ). Hence, the indierence equation is

c + dp(1 -g)(1 -gq) m-1 = dp(1 -gq) (m-1)
with solution p ⇤ = c gd(1gq) (m-1) In terms of the solution q ⇤ it is

p ⇤ = c gd(1 -b a ) (m-1)/m
As before, the two solutions p ⇤ and q ⇤ are equal to those of G(m,1) rescaled by a factor 1/g.

g p ⇤ g q ⇤ Γ(1, 1) P ⌘ c d Q ⌘ b a Γ(1, n) P nQ Γ(m,1) P (1-Q) m-1 m 1 -(1 -Q) 1 m Γ(m, n) P (1-Q) m-1 m n 1 -(1 -Q) 1 m .. Game Γ(m, n) -m Inspectors, n Inspectees
The solution for q yielded by the inspectee indierence is presented in the following equation. It is analogue to Γ(m,1) but with q replaced by q/n. The explicit form is shown in table ..

✓ 1 -g q ⇤ n ◆ m = 1 - b a
The inspectors' indierence equation to determine p should equalize two information. On the one hand, this is the expected impact (on a single inspector) in case of no inspection. This corresponds to d times the expected value of the inspectees' violations going undetected by the other m-inspectors. On the other hand, it is the expected impact (on a single inspector) of inspection. Considering the derivation of G(m, n), the value (-c) of the certain cost for an inspection and needs to be equated with the expected impact of the extra detected violation. The latter one represents the damage (-d) times the violation probability p times successful detection probability g of a violation undetected by the other inspectors. This leads to

c = dpg (1 -g q n ) m-1 or c gd = p (1 -g q n ) m-1
and has the solution

p ⇤ = c gd (1 -g q n ) m-1 Overall, substituting q ⇤ , we have p ⇤ = c gd (1 -b a ) m-1 m
Again, the solution values p ⇤ and q ⇤ are equal to those of G(m,1) rescaled by a factor 1/g. The results for the games Γ(•, •) are summarized in table ., they are equal to the solution values for the corresponding G(•, •) rescaled by a factor 1/g. It represents an increased violation rate and a correspondingly increased inspection rate.

. The derivation showed that the solutions of Γ(•, •) are equal to those of G(•, •) divided by a factor g. This is due to the following reasons. The function g has two impacts on the game Γ(1, 1). This is an increased violation rate (some violations are undetected) and an increased inspection rate. Both increases are in balance, which causes the rescaling for this game. The game with n inspectees Γ(1, n) is played by each inspectee as two-player game due to their independence among each other. For an inspectee i, the inspection of another inspectee j is considered as no inspection. Hence, the rescaling is directly transferred to this generalization. Similarly, the game Γ(m,1) can also be considered as agame since the inspectors work on the administrator's behalf and share a damage d. Thus, they appear as one inspector with a correspondingly adapted inspection rate. The rescaling of Γ(m, n) follows then straightforward considerations.

. This chapter introduced the game theoretic foundations for the remainder chapters. The initial two-player game G(1, 1) of Dresher [] was introduced in the beginning. It was then generalized up to G(m, n) with m inspectors and n inspectees. All games G(•, •) were then extended by the possibility of false negatives (not detected violations). This is represented by function g and the corresponding games denoted as Γ(•, •). The solutions, Nash equilibria in form of indierence strategies, are given for all games. The games Γ(•, •) with possibly multiple players provide an IG model that is suitable for an application to distributed systems.

ON THE INSPECTION GAME APPLICATION TO DISTRIBUTED SYSTEMS

This chapter discusses now some issues that arise during an application to real world systems. It focuses on two major aspects: the IG model itself and possible implementations. Please note that this discussion does not intend to be exhaustive. Instead, it targets to call the reader's attention to the most relevant issues. This is meant as a preparation for an IG application.

.

At rst, we consider several aspects related to the IG model.

.. Independency of Players and Games

As for the the IGs of the last chapter, we assume that all players are independent: the strategy choice of one player has no inuence on those of the others. Nevertheless, since all inspectors work on the system administrator behalf, there is some inherent relation among the inspectors.

The IG type such as Γ(1, 1) or Γ(m, n) depends on the players' point of view, i.e. with who the game is actually played. Let us consider again gure . (page ) for the game G(,) with one inspector and two inspectees . If the inspector does not inspect, the system damage caused by the inspectees' violations (if any) is summed up. Here, it is assumed that both inspectees are controlled with only one inspection. This is not realistic: in real world distributed systems, each inspection causes some inspection costs. Hence, the game G(,) or in general G(,n) can be considered for the inspector as a set of independentgames, one per inspectee. This is similar for the generalization G(m,), shown as game G(,) in gure . on page . A violation is punished only once even if both inspectors detect the violation at the same time. In other words, the m inspectors appear for the inspectee as one inspector with a correspondingly higher inspection probability. This is also denoted as Eective Inspection Probability (EIP) in the remainder. Hence, the generalized game G(m,) can also be considered as agame with all m inspectors representing one inspector with the EIP value as inspection probability.

To summarize, all IG generalizations can be considered as sets ofgames. From the inspector's point of view, he plays multiple games (one per inspectee) since all are independently played. Analogue, the inspectee fears to be inspected by any inspector, whose exact number aect the EIP, i.e. the violation detection probability. The EIP value is also aected by the way how inspectees are selected for an inspection. This is addressed by the next paragraph.

The games G(•, •) are only used here since the corresponding gures have already been discussed. .

. Synchronization of Inspectors

In general, an inspectee may be controlled by multiple inspectors at the same time if no mechanisms are implemented to avoid it. Such double inspections bring -in our case with only unique punishments -no benet for the games G(•, •). For Γ(•, •), they yield only a slight increase of the violation detection probability. Hence, double inspections are considered as a waste of resources. To avoid them, inspectors should coordinate their inspectee selection. This is denoted synchronization of inspectors in the remainder. It can be realized statically (e.g. assignment of id ranges) or dynamically based on some runtime criteria (e.g. hop distance).

Let us consider the term Inspection View (IV) as the set of inspectees that represent inspection candidates for an inspector. Figure . illustrates the inspector synchronization for a two-dimensional id space (e.g. the IP address or overlay id) with the inspection candidates as black dots. Synchronized inspectors are shown left in the gure: the id space is separated into four equal IVs, each one assigned to exactly one inspector. On the right side, the inspectors are not synchronized and id regions not assigned to an inspector are indicated grey. Double inspections are possible when the inspectee is inside of overlapping IVs. This is shown for candidate , who is assigned for two inspectors. Candidate and are assigned to only one inspector and candidate can violate without fearing to be punished (inspections will not occur). The separation of the id space is a comfortable yet ecient way to attain synchronized inspectors. It is in particular ecient for systems with id based routing such as the Scribe system. Further systems are reviewed in the survey of Lemmon et al. []. In general, it is not applicable in systems with non-deterministic dissemination such as gossiping. An alternative is the setup of the IV based on the network distance (e.g. hops). Then, a separation takes place in the space dimension, i.e. the network topography. In such systems, a system designer should be aware that non-assigned inspectees may also arrive through failure situations or even system dynamics (e.g. node churn). This is not the case for approaches with id space separation. .

. Payo in the Real World

For an IG application, we are faced with the question what payo actually means in the real world? In general, it is supposed to precisely quantify the players' outcome of a game and is established by payo values. These values are crucial for the general IG mechanics, however, the interpretation of real world conditions and the mapping to appropriate values is a hard task due to the context dependency. This comprises several aspects such as the system state or individual preferences. Therefore, it is challenging task and an important drawback.

The complexity is now shortly outlined. The inspection procedure is known to the inspector. Hence, function g and the inspection costs c can be evaluated in an -to some degree -objective way for the average case. To determine the system damage, the actual impact of a peer's violation and the meaning of the serviceability loss needs to be evaluated. This can be done with simulative studies. In contrary, the specication of the inspectee's benet b and the punishment a is dicult. They depend completely on the inspectee's individual personal goal(s). The values are typically determined by the system designer's correct interpretation. This is challenging and more objective approaches should be used. Feedback mechanisms may support the designer's choice or even specify the values dynamically. A simple example is the inspection rate adaptation until a desired collaboration is reached .

A further aspect concerns the question how worth a violation is over time for the inspectee. Intuitively, there is a linear relation: the more violation possibilities are, the more violation benet is possible. This is illustrated in gure .. However, non-linear dependencies are also possible as indicated on the right side of the gure. The wave curve represents a relation to the time of the day. The dotted step-like curve represents a situation, where for example an internet connection contract provides a graded price in terms of data consumption. The dashed curve corresponds to a situation where especially the rst violations have a high benet. An example is a tampered response to an initial DNS request in order to redirect the further communication to a fake server.

Studies of such mechanisms are actually not in the scope of this thesis. However, an exemplary simulation result of this mechanism is presented in gure . (page ) during the discussion of chapter .

.. Inspection Games for Continuous Operation

In contrary to IGs distributed systems are supposed to operate indenitely. An approach to cope with this problem is outlined in gure ., where the several operations are split into groups. Each group is related to a specic game and each game is played independently from the other ones. Then, a game strategy is chosen for each game, which is applied to all corresponding operations.The inspectee needs to collect collaboration proofs for each operation, which are denoted as proof messages. To this end, we introduce a container, the inspection target. It stores the proof messages for a game and is controlled during an inspection by the inspector. The size of the inspection target is a game parameter and should ideally be able to store all proof messages related to a game. In order to obtain stable violation benet values over time, a system designer should target equally composed games in terms of proof messages. One possibility is a game splitting method based on the amount of operations (loaddriven split). Other common methods are based on time (e.g. periodical split), operation type (type-driven split) or even network message content (semantic-driven split). In addition to the game splitting method, equally composed games can also be achieved by means of the inspection target. Providing an appropriate or a dynamic size the inspection target is able to tolerate uctuations in terms of proof messages.

In distributed systems, we cannot expect that the users are aware of playing games or that they are independently played. Hence, we specify three further assumptions:

. For real world systems, users are informed about an IG and its mechanics (except the other player's strategy) as reliability method, for example in the settings user interface.

. The game players are informed about possible inspections and punishments.

. The players can draw conclusions from circumstances such as undergone inspections.

As we will see in the next paragraph, this is important for the practical objective of research challenge (C). Nevertheless, the games itself remain independent and their outcome has no inuence on the other games' strategy choice. Especially strategies over multiple games remain impossible. This would change the game characterization to evolutionary games and require another IG model.

.. General Principle for Collaboration Achievement

IGs of the GT literature focus on the Nash equilibrium analysis in terms of payo values. This was also done in the prior chapter for G(•, •) and Γ(•, •), respectively. However, corresponding to research challenge (C), the system administrator has the practical objective to achieve a targeted collaboration 1p in average. Hence, the collaboration value becomes for the inspector more important than the payo value itself. In this context, the IG model enables to calculate an appropriate inspection strategy for the inspector. This strategy yields in a shift of the NE to a strategy combination that corresponds to the targeted level of collaboration. For a better understanding, let us introduce the term Best Response Strategy (BRS). It denotes the strategy that results in maximal possible payo, given the imaginary situation that the other player's strategy is known. Considering the assumptions of the last paragraph, the players can approximate the other player's strategy -not in real time but over several games. With such approximation, the rational inspectee is able to calculate a BRS in order to increase the own payo. This rationality, i.e. trying to optimize the payo, is then leveraged by the inspector. By means of the IG mechanics, he is able to specify and inspection strategy that leads to the desired collaboration value 1p. In more detail, the inspector choses a strategy such that the inspectee's BRS lies exactly at the target collaboration value 1p.

.

As counterpart to the last section, we discuss now some possible implementations. This comprises the inspection architecture, the collaboration incentive and some game characteristics.

.. Inspector & Inspection Architecture

Still dealing with two types of individuals, the following question comes up: How can the IG be realized in terms of the network architecture with multiple user machines? This is answered by considering two aspects separately: the inspector and the inspection architecture.

The inspector logic can be implemented in several ways. Figure . illustrates two general approaches. On the left side, the inspector is realized as individual peer beside the inspectee peer. They are loosely coupled over the network in terms of inspections. On the right side, the inspector is realized as a network layer within the inspectee's peer. These approaches have several advantages and drawbacks, which are outlined in the following. Please note that they are only examples; other solutions (e.g. mobile software agents moving over the inspectees' peers) are possible.

Systems with independent inspector peers are very exible. The amount of inspectors can be easily adapted to the corresponding needs. However, it requires some overhead due to the inspections over network but also in terms of inspector synchronization. with an inspector as network layer, the inspector is directly present at the inspectee. Hence, local inspections are eciently performed since there is no overhead in terms of network communication. Even the full monitoring of all network messages passing the layer is in general possible. However, the inspector competes with the inspectee for the same limited resources possibly aecting the application's performance. In a worst case, the inspectee may even be encouraged to circumvent the reliability mechanisms.

Four exemplary inspection architectures are illustrated in gure .. Examples ) and ) represent the two discussed inspector implementations, i.e. ) as independent node and ) as network layer at the inspectee. They represent PP based systems, while ) and ) also correspond to more centralized architectures. Example ) provides exactly one inspector on a dedicated machine, which lies -for illustrative reasons -outside of the actual system. A realistic scenario is drawn by example ): several dedicated inspectors (e.g. a server infrastructure) control the inspectees in the system. Heres, inspectors are synchronized, although not in an optimal way (double inspection are possible).

.. Collaboration Proofs & Incentives

In any case, some (secured) logic is required at the inspectee's machine in order to maintain proofs of the behaviour and to monitor system values. This is shown in gure . (left), where the logic as well as the inspection target is considered as part of an additional network layer. A further example is a database with some secured logic, where a table entry contains proofs for the processing of database queries. The realization as network layer of this example is also suitable to directly apply collaboration incentives. This is shown on the right side in gure . with two examples for negative incentives, i.e. punishments. The rst one is a reduction of the messages passing the layer and the second one an expulsion form the system.

We consider in this thesis only negative collaboration incentives by means of punishments. Positive ones (rewards for collaboration) are also possible; however, they do not change the IG mechanics in our case. The incentive mechanisms that are articially added (such as the .

. Game Characteristics

The last sections discussed some theoretic and practical aspects, however, independently from each other. We outline now the glue, which brings all together to a usable game implementation. To this end, let us consider the term game characteristics. It denotes the further implementation details that describe how the game is played. They comprise the following points, which are detailed afterwards.

• mode of inspection initiation

• when a game is initiated • who is actually playing a game

• what is controlled during an inspection : The game mode species which player initiates the inspection. Two modes are in general possible, described from the viewpoint of the inspectee:

In systems with a reactive game mode, an inspectee waits until an inspector requests a collaboration. The inspectee can fully concentrate on the actual system operation and proves the collaboration reactively to an inspection request. In reactive mode, the power about the inspection kept by the system designer and is is initiated either externally or internally. With an external initiation, there are some external individuals such as game masters as shown in gure . (left). They do not actively participate at the system operation but induce the inspection. In case of the internal initiation, the inspectors inside the actual system decide when to initiate the inspection (gure . right).

In systems with a proactive game mode, the inspectees decide on their own when to transfer collaboration proofs to an inspector (see gure .). The system designer imposes an inspection policy to specify when an inspection must be initiated or which inspector is responsible. Inspectees in proactive systems have gain some exibility. They can coordinate the inspections with the current work load or further interests (e.g. energy eciency). However, a drawback is the higher maintenance overhead to verify if the inspectees adhere to the policy.

:

The second implementation characteristic is related to the question when an inspection shall be initiated. The general possibilities are outlined in the (non-exhaustive) schema shown in gure .. An inspection probability could be initiated depending on some time constraints (e.g. periodical inspections) or on the time of the day. The inspections may also depend on some values or system parameters. An example is the message load or the uctuations of an inspectee's inspection regularity (in proactive systems). Context-driven approaches initiate an inspection depending on the given environmental circumstances. Imagine for example a Mobile Ad-Hoc Network (MANET), where an inspection could be done if an inspectee comes into the reach of an inspector.

: A further question to be claried consists in the selection of the other player. This means the question which inspectee(s) is chosen by the inspector in the reactive mode and which inspector(s) is chosen by the inspectee in the proactive mode. As a short recall, note again that all players are assumed to work independently. Implementation possibilities for this characteristic are manifold but three are shortly outlined. An intuitive approach is the randomized choice. It is fast in terms of computation and distributes the inspection load equally over all (known) players. However, it ignores the specic architectural circumstances and system states. Another possibility is to choose the other player in terms of the distance. This approach reduces the network load used for inspections by increasing the locality of the game. A further approach, applicable only for the reactive game mode, is the inspectee selection based on the amount of detected violations. Such feedback mechanism enables the IG to adapt the inspection resources to the danger for the system (in terms of protocol violations).

:

The last point is related to the question what is actually controlled during an inspection. This depends on the considered selsh goals. For example, in the use case of this thesis we consider message drops, i.e. the correct message transfer is veried. To this end, the IG approach makes use of some secured logging that serves as proof for the peer's behaviour. Secured logging is indeed under active research. The interested reader is referred to [, , , ] and the references therein.

. This chapter serves as connection between theory, the game theoretical foundations, and practice, an IG application to distributed systems. A possible application was discussed with regard to two aspects. At rst, several aspect and modications of the IG model were considered that arise for a practical utilization. Second, some realization details and implementation possibilities were introduced.

The discussion identied benecial aspects but also challenges for an application. An important outcome is the insight that all IG generalizations can be considered as sets of independent two-player games. This simplies the modelling and analysis. A signicant challenge is the determination of appropriate payo values and game parameters in general. They are crucial for the IG mechanics but depend on the individual user preferences and system states.

AN INSPECTION GAME FRAMEWORK FOR DISTRIBUTED SYSTEMS

This chapter introduces an application of the Inspection Game (IG) with false negatives Γ(•, •) to distributed systems as solution approach for research challenge (C). In order to provide an illustrative use case, we consider the video streaming scenario of the introduction with selshness-driven message drops. Furthermore, we use the two pub/sub systems Scribe and basic gossiping for an application.

. In order to modify a given system as less as possible, we add a network layer at the inspectee's machine. To reduce the possibility of vulnerabilities, it provides merely some secured logic responsible for two tasks. At rst, it deposits proofs of the peer's system interaction into a inspection target, which has a xed size to ease the comprehensibility. Furthermore, the logic is responsible to apply a punishment as collaboration incentive. The actual inspector is realized as independent peer, loosely coupled with the inspectees. The architectural overview of this approach is shown in gure ..

The IG is operated in (internal) reactive mode, i.e. the inspectors initiate the inspections. This is done time-dependently in a periodical way. In other words, the system operation is split into time intervals T, each one related to one game. With all games being played sequentially, the IG can be considered as a sliding window moving over the several intervals. The length of a time interval T itself is not relevant since it serves only as point of reference. However, for the sake of simplicity, an equal interval T is assumed for all inspectees and inspectors.

The system consists of m inspectors and n inspectees. Each inspector selects randomly (covering the whole id space) n i inspectees for an inspection per interval T to support a broad range of systems. Hence, the inspectors are not synchronized. Furthermore, all played IGs are considered asgames as described in the previous chapter. Therefore, this approach is related to the IG as presented in the extensive form in gure . (page ).

. :

Before providing details of the IG mechanics, we introduce a possible implementation of the inspection target and procedure. It targets to harden the system against selshness-driven messages drops as described in the scenario of the introduction. Please note that the details presented here represent only one example for possible reliability mechanisms.

.

. Inspection Target

The inspection target stores proof messages that prove a peer's behaviour in a First-In-First-Out (FIFO) manner and is also denoted as proof history. With an amount of r stored proof messages per message transfer and a history size h, the inspection target is able to secure h r of such operations. All messages are assumed to be cryptographically secured.

The inspection target is used to enable the detection of possible protocol violations in terms of two aspects. First, the hop-to-hop transfer itself is protected. Second, the existence of an omitted forwarding is checked. The hop-to-hop transfer protection is realized by a simplied version of the one presented in []: cryptographically secured promises and acknowledgements. A transfer from peer A to peer B consists of the following four phases. Note that all messages are digitally signed, which is omitted here for the sake of clarity if it is not essential part of the phase.

. Peer A wants to sends a signature of the message to be sent as promise to peer B.

. Peer B responds with to the promise.

. Peer A sends the actual message.

. Peer B replies the correct reception with another acknowledgement. Both peers store the received r = 2 messages (the actual message is part of a receiver's proof message). In the remainder, we consider a history size h = 200 and thus, 200 2 = 100 message transfers are secured. This value as well as other values used later, are chosen only for illustrative and comprehensibility reasons.

The second aspect checks whether a message has been correctly forwarded. An inspectee is only allowed to drop a message in each of these cases:

(a) A message with the corresponding ID has already been handled.

(b) The TTL value is zero to avoid unlimited disseminations.

(c) There are no subscribers behind the remaining outgoing links.

The TTL value is typically in the message header. To control (c), we assume the existence of a secured Next Hop Table (NHT), a data structure that maintains the possible next hops. This could be for example the routing table (Scribe) or the partial view (gossiping). Furthermore, we assume that changes in the NHT are tracked for one time interval to prevent covering violation tracks by system dynamics. Secured NHTs are under active research; see for example the secured peer sampling of Jesi et al. [] for gossip-based systems. With the NHT information and the proof messages, a correct forwarding can be veried.

.. Inspection Sequence & Procedure

In the context of an inspection we denote with inspection sequence the several interactions with other network participants. Furthermore, we denote with inspection procedure those operations needed to control an inspectee's inspection target.

The inspection sequence is outlined in gure .. An inspector requests at rst a copy of the inspection target. After receiving it, he requests also a copy of the inspection targets of those communication partners that have proof messages in the inspectee's history. Then, they are controlled (inspection procedure). In case of a detected violation, the inspector disposes a punishment, which is applied by the secured logic at the inspectee's peer. Note that any inspectee's non-collaboration during the inspection sequence is treated as violation.

The inspection procedure consists of controlling the two aforementioned aspects as shown in gure .. Each message transfer related to the inspection is secured as for the hop-tohop transfer itself. We omit these messages for the ease of comprehensibility. To verify a hop-to-hop transfer, the inspector controls not only the r proof messages of the inspectee but also the other r messages of the corresponding communication partner. Overall, two histories are controlled during one inspection. The second part (correct message forwarding) is veried by requesting the NHT and controlling it among the proof history. For example, an inspector controls among others if the receiving peer had -at the corresponding time point -a subscription in the NHT of the sending peer. To ease the comprehensibility, we assume this forwarding verication is done during the control of the two histories and covered by the corresponding cost values. Then, the costs for the inspection of one peer consists of the control of two histories. .

We introduce now all details needed for an application of the IG framework to pub/sub systems. All variables and functions as well as their values used for the simulative evaluation are clearly arranged in table .. As mentioned before, the values listed in this table have been only chosen for the sake of comprehensibility and illustrative reasons.

.. Specication of Payo Values

The IG payo values are determined as detailed in the following.

• b: violation benet

As incentive for a violation, we assume the inspectee considering that violating (i.e. dropping a message) is worth twice as collaborating (i.e. forwarding a message). This is modelled by the weighting value w b = 2. The benet b depends on w b and on the message load l and is dened as:

b = w b l (.) • d: non-detection costs
The damage represents the costs to the system in case of non-detected violations. It is equally shared over all m inspectors since they work on the system designer's behalf and inherently collaborate therefore to some degree. In order to cover any system architecture, we assume the simplied situation where the violating inspectee is in the middle of the dissemination route, i.e. he aects the half of all n ⇤ g s subscribers.

Again, a weighting value w d enables individual parameter adjustments. Note that, due to the message load dependency, the assumption |d| > |c| of the abstract game model (see page ) is not always guaranteed. The cost value is dened as:

d = w d lng s 2m (.)
• c: inspection costs The inspection costs value depends on mechanisms used for the inspection target. Considering the prior described concept of a proof history as inspection target, an inspector needs to control two proof histories (the one of the inspectee plus its corresponding entries of the communication partners) for the inspection of one inspectee. For the sake of simplicity, we assume that the inspection of one secured transfer has a unitary cost value. Then, the cost value is determined as in the following:

c = 2h r (.)
• a: punishment costs The punishment costs represent the decrease of the inspectee's payo due to a detected misbehaviour. It does not depend on the system architecture and can be specied by the system designer. As discussed before, the punishment (as well as the benet) depends on an individual inspectee's importance and preferences. Here, this cost value is calculated relative to the non-detection costs for the whole systems. Therefore, since d represents the costs divided by m, it is multiplied again with m. a = w a dm (.)

.

. EIP & MEIP: Eective Inspection Probabilities

All inspectors operate independently but work on the system administrators behalf. Hence, they collaborate in some sense. For an inspection, each inspector selects a set of n i inspectees.

From a practical point of view, an inspectee fears to be inspected by any inspector. For the sake of comprehensibility and to cover all architectures, we consider the simple case of not synchronized inspectors. This means that all n i inspectees are randomly chosen over the whole id space for an inspection. As a result, double inspections are possible. Punishments are only done once per game. Thus, double inspections can be eectively represented as single inspections with a correspondingly increased inspection probability. This forms an EIP for the inspectee and is described by function s (or EIP function) in equation .. The calculated value denotes the ratio of inspectees in the system that are in average inspected per T for given q and n i . For example, . means that a quarter of all inspectees are inspected per T and a value . that an inspection arrives twice per T.

s(q, n i )=1 - ✓ n -qn i n ◆ m (.)
Similarly, the Maximal Eective Inspection Probability (MEIP) describes the maximal amount of the inspectees that can be inspected per T. It serves therefore as upper bound for the EIP value and is shown in equation .. The MEIP requires that all inspectors are perfectly synchronized (no double inspections) and that they choose a value q = 1. Since the inspectees are rational and have system knowledge, we assume that the EIP value is known or communicated by the administrator. Alternatively, an inspectee can monitor the inspections and calculate an approximation over time.

s ⇤ (q = 1, n i )= qmn i n (.)

.. Violation Detection Function g

The function g indicates the probability that -given an inspection on a peer where a violation occurred within the last interval T -the violation is actually detected, i.e. the PoM is found. Function g is presented after the clarication of some timing details.

. With history ushing we denote the correct removal of all PoMs from the proof history. This is done if the peer transfers at least h r messages and replaces the current proof messages in the history. Let us consider T sa f e = T ⇤ t s as the time for the history ushing relative to an interval T. Then, t s has the following time value:

t s = h r l = h rl
Similarly, T insp = T ⇤ t i is the average time after that a peer is periodically inspected exactly once. We specify t i as in the following:

s(q, n i )t i = 1 ⌘ t i = 1 s(q, n i )
Withe notion of these time intervals, let us now consider the realistic situation where the inspectee target maximum payo and assumes periodical inspections. In this case , the inspectee can violate T insp -T sa f e but should collaborate afterwards for T sa f e to ush out all violation proofs before the next inspection. Then, a violation is detected during an inspection if at least one PoM remains in the history. This happens in two cases:

. The inspectee violates (probability p).

. The inspectee violated but is still occupied to ush all violation proofs out of the history (by collaborating) as preparation for the next expected inspection . This happens with a probability of

T sa f e T insp = t s t i .
Furthermore, we need to take into account that the collective of inspectors achieve an amount of n i ⇤ m inspections done per T and done relative to one inspectee (factor 1 n ). Then, the detection function g is dened as in equation .:

g(n i , q, p)= ⇣ p + T sa f e T insp ⌘ n i m n (.) = ⇣ p + t s t i ⌘ n i m n = ⇣ p + h rl 1 s(q,n i ) ⌘ n i m n = ⇣ p + hs(q, n i ) rl ⌘ n i m n
Please note that function g may exceed the probability bounds. Hence, the payo function makes use of the adapted functions g ⇤ :

g ⇤ (n i , q, p)= 8 > < > : 1 if g(n i , q, p) ≥ 1 g(n i , q, p) else (.)
.

. Payo Functions

With the detection function g ⇤ we are now able to specify the complete payo functions for the inspector and inspectee. They are created by directly transferring the IG in extensive form (see gure ., page ) into equations. These complete payo functions are shown in equation . with C(p, q) for the inspector and with I(p, s ⇤ (q, p)) for the inspectee. Please note that the inspectee needs to consider the EIP value instead of q.

C( p, q )=p q

⇣ g ⇤ (q, p)(-c)+(1 -g ⇤ (q, p))(-d -c) ⌘ +(1 -q)(-d) ! +(1 -p) q(-c) ! I( p, q ⌘ s ⇤ (p, q)) = p q ⇣ g ⇤ (q, p)(b -a)+(1 -g ⇤ (q, p))b ⌘ +(1 -q)b ! (.)
The payo functions are essential for the inspector's practical objective to attain a targeted degree of collaboration 1p. To this end, the inspector leverages the inspectee's rationality to choose a payo maximizing strategy. In other words, the inspectee will choose the best response strategy (BRS) given that the inspector's strategy q is known. The inspectee's BRS calculation for a given q is formalized in equation . (the inspector's BRS is analogue but not shown here). Knowing this equation, the inspector needs to determine a value q such that the targeted inspectee's strategy p represents a BRS. The determination of such a value q can in our case be carried out by examining the whole strategy space. In more complex situations, e.g. when the strategy consists of a combination of multiple values, a solution could be found by optimization algorithms.

f( q )={p | I(p, q)= max p2[0,1] I(p, q)} (.)
.

Payo matrices (see for instance table ., page ) are a common mean to outline and evaluate two player games. This is visualized with best response strategy (BRS) graphs to provide a mean for graphical system analysis. The players' BRS, i.e. the strategy with maximal possible payo, is indicated with regard to a given strategy of the other player. The curves are calculated as dened in equation . for the inspector and in an analogue way for the inspectee. BRS graphs are outlined in gure .. The continuous line shows the inspector's BRS for a given p while the dashed line represents the inspectee's BRS for a given q. Finally, a NE is given at the strategy combination where both lines are crossing. Please note that the inspectee (fearing to be inspected by any inspector) must consider the EIP value instead of q.

The strength of BRS graphs lies in illustrating the players' (cost-optimal) strategy decision landscape in a comprehensible way. This is shown in gure . outlining the players' behaviour for the IG approach with the values indicated in the notation summary (table .). The two used pub/sub architectures have only small inuence on the resulting payo and are visually identical. Therefore, only the graphs for the Scribe system are presented. The players' strategies are clearly visible in the left graph of gure . by a vertical and horizontal run of the curves. The NE is indicated at p ⇡ 0.95 (1p ⇡ 0.05) for the inspectee and at q ⇡ 0.14 for the inspector. Due to the high inspection intensity of n i = 20, an inspector is able to detect an inspectee's violation for several strategy values p. Hence, it is only worth to violate for low EIP values. Here, full collaboration is reached at EIP ⇡ 0.14 for Scribe and EIP ⇡ 0.155 for the gossiping architecture. Both is reached with q ⇡ 0.3. On the right hand side, gure . shows an example for the suitability of BRS graphs as technique for evaluating parameter adjustments. Here, a reduced history size shifts the NE point correspondingly.

Note again that the used values (e.g. payo) were chosen for comprehensibility reasons.

The BRS curves in gure . have apparently dierent characteristics: the inspectee's (dashed) curve is increasing while the inspector's curve has a binary nature. Considering the game mechanics (see gure ., page ), we can determine the reason. It is obvious that a higher inspection probability increases the violation detection probability. Thus, an inspectee is encouraged to collaborate for a higher value q. The actual collaboration value is aected by function g, producing an increasing curve. In contrary, the inspector perform a quasi binary strategy: fully inspecting or fully not inspecting. For situations p > 0 with d > c, an inspector is encouraged to inspect as much as possible to increase the violation detection probability. For d < c (e.g. through high collaboration), he prefers to not inspect. Intuitively, he would switch to fully not inspecting when the expected damage pd equals the inspection costs. This is indeed the case but in detail slightly more complex. At the transition point (inspecting to not inspecting), the possibility of false negatives produces a small anomaly: the inspection probability is increasing for an increasingly collaborating inspectee. This is shown in the circle(s) in gure ., indicating also two situations S and S. At situation S, the expected payo gains by partially not inspecting equals the correspondingly increased losses. The inspector can now improve his payo by intensifying inspections and reduce damage caused by non detection. The yielded payo outbalances the additional inspection costs. At situation S, the expected damage pd equals the inspection costs and the inspector changes to not inspecting for higher collaboration values.

.

The IG approach introduced before is now evaluated by a simulative study. This is done straightforward way beginning with the network setup.

.. Network Setup

The system comprises of m + n peers with m = 5 trusted peers (inspectors) as well as n = 200 selsh peers (inspectees). We assume furthermore that each peer has a unique role, either as inspector or as inspectee. Each inspectee subscribes in T = 20 to g s ⇤ g = 0.1 ⇤ 30 groups and publishes each T (beginning in T = 40) with a probability of p p = 0.04 one message to g p ⇤ g = 0.25 ⇤ 30 groups. Hence, there are n ⇤ g s ⇤ g = 600 subscriptions in the system and p p ⇤ n ⇤ g p ⇤ g = 60 new published messages per T. The actual interval length is not relevant for the IG evaluation. An interval represents a game here but does . not aect the game mechanics itself. Instead, an appropriate amount of games should be considered for representative results. This is the case with a simulation duration of T and correspondingly . published messages. As mentioned before, the two pub/sub systems Scribe and basic gossiping are used for the evaluation. The latter one makes use of Cyclon [] as membership protocol with a fanout of and a partial view size of . These system realize dierent network structures, which are illustrated in simplied form in gure ..

.. Parameter Calibration

Though the two systems realize dierent architectures, they dier only in the message load parameter l for the IG. As an important value for the payo calculation, it is essential for the IG mechanics. In the given case of message drops, the message load is not only aected by the architecture but also by some game parameters such as n i . For example, a low eective inspection leads to higher violation rates with correspondingly reduced load value.

In order to specify an appropriate value, we omit a theoretical load analysis for the sake of comprehensibility. Instead, we use load values obtained from a calibration procedure. The values l occurring in the explicit expressions of the payos are obtained by a Monte Carlo simulation (using q = 1 and n i = 20) and they indicate the average message load of a peer. These are a l = 5.8 for the Scribe system and l = 7 for gossiping. An overview is presented within the simulation results gure . for gossiping in gure . for Scribe. These load values lead to payo values that are listed in table .. To summarize them, an inspectee in the Scribe system needs to violate at least 1740 11.6 = 150 times to balance a possible punishment of with a violation benet of . (analogue in the gossiping architecture with 1740 11.6 = 150). Similarly, the system damage of is almost . times the inspection costs.

.. Simulation Setup

The simulative evaluation of the IG approach is done with the Peersim simulator [] and an adapted version of the RCourse library. Both systems are simulated under the conditions stated before and evaluate the IG approach in terms of the interesting point of costoptimal full collaboration. To this end, all inspectors adjust an inspection probability q ⇡ 0.3 (EIP ⇡ 0.14), which nally results in full collaboration according the IG model. This is shown in the BRS graph (a) of gure . since it has been generated with the parameters used for the simulation. The IG is played from the beginning of the simulation. In contrary, the subscription to multicast groups starts in T = 20. The publishing of information starts in T = 20 and lasts until the end of the simulation with a duration of time intervals T.

.. Simulation Results

At rst, the simulation graphs for the EIP values are shortly presented. The main simulation results concerning the inspectees' collaboration value are presented afterwards. The graphs present the inspectees' values as median with quartiles and are therefore denoted Median Quartile (MQ) graphs. Result graphs that show the value distributions of all inspectees (with arithmetic mean) are denoted Value Distribution (VD) graphs in the remainder. They are placed in the appendix and only presented here for the sake of clarity.

The simulation results concerning the EIP value are shown in gure .. In addition to the network setup of with n i = 20 and q = 0.3 (centre) and q = 1 (right), a simulation was also done for the sake of comparison with n i = 1 and q = 1 (left in gure). The EIP function (equation ., page ) predicts an eective inspection probability of s(1, 1)=0.025, s(0.3, 20)=0.141 and s(1, 20)=0.41. The MQ result graphs show that the predicted values are veried with only low variances. However, the VD graphs (see gure B. in the appendix on page ) show that some values slightly dier up to about . (%) from the predictions. for the given parameters. The predictions are precise although some outliers exist with up to about . (%) from the arithmetic mean (see VD graphs in gure B., page ).

/ The simulation results for gossiping are shown in gure . with the payo distribution in the rst row, the message load distribution in the second row and the collaboration values (1p) in the third row. The dissemination style leads to a homogeneous load distribution for the peers. Hence, the quartile curves are almost equal to the median. Thus, the prediction of q = 0.3 is precise and sucient to reach full collaboration at all inspectees. There are some outliers during a short stabilization period as can be seen in the VD graphs given in the appendix (gure B. on page ).

The left column in gure . simulation results for Scribe using the same parameters and graph placement as for gossiping. The additional fourth row shows the collaboration values (1p) as VD graph for comprehensibility reasons. Due to Scribe's to the tree-based dissemination, the load distribution diers strongly to gossiping. There are several uctuations since the actual load depends on the position in the tree. Nevertheless, Scribe provides an ecient dissemination relative to gossiping (see y-axis scales). The desired collaboration value is exactly reached as shown in the MQ graph. This is veried by the VD graph (bottom in gure): the mean hits almost exactly the targeted full collaboration. However, the VD graph reveals several outliers due to the heterogeneous load distribution. These variances are not visible in the MQ graphs due to the median's statistical robustness. Thus, the predicted inspection value q = 0.3 (left column), resulting in EIP = 0.14127, is considered not completely sucient.

As a comparison, the right column of gure . shows the results with the inspection probability being dramatically increased from q = 0.3 to q = 1. Here, the amount of inspections is high enough to prevent violations from the early beginning. This outlines the diculty in terms of specifying an appropriate inspection probability value. In systems such as Scribe, the message load value depends on the position in the dissemination tree. However, this is typically not known to the IG model (e.g. the root node of a tree is typically elected by a hash value of the group id and the inspectee's overlay id). As a result, the tree-based dissemination such as Scribe always provides a variance in terms of load. Thus, precise predictions of the needed inspection probability remain dicult for this IG model.

. In this chapter, the IG approach was applied to distributed systems using two Publish/Subscribe systems. The scenario of the introduction with selshness-driven message drops was considered as illustrative use case and details for an application were introduced. The simu- lation addressed among others the inspectees' collaboration degree and veried the general functioning of the IG approach. It can already be considered as a promising approach that reaches the thesis' vision. The evaluation outlined also some drawbacks caused by the IG model's stiness: it is not yet able to deal with dynamic conditions. This is addressed in the next chapter.

n i = 20 q = 0.3 n i = 20 q = 1

AN ENHANCED DYNAMIC INSPECTION GAME FRAMEWORK

This chapter presents the enhanced Inspection Game (IG) approach that enriches the initial one of the foregoing chapter by some degree of dynamics. This chapter introduces basically the several dierences to the initial approach. For specic details (e.g. IG fundamentals, inspection target details, payo functions), the reader is referred to the foregoing chapter.

.

The improvements address two important shortcomings of the initial version: varying message load as well as varying inspection rates. The enhanced IG approach considers not only the same scenario as the initial version, it has also basically the same characterization. It as played in (internal) reactive mode, i.e. the inspectors initiate the inspections. The continuous operation is also faced with periodical game splittings, i.e. the operation time is equally splitted into time intervals T. However, there are two major dierences, which are detailed afterwards. These are the adaptation to system dynamics (covering the aforementioned shortcomings) and a change of the inspection architecture.

.. Inspection Architecture as Additional Network Layer

The initial IG approach has some secured logic as network layer at the inspectee's machine. Hence, it makes sense to deploy directly the full inspector logic, e.g. as part of the application. The resulting inspection architecture is illustrated in gure .. With this architecture, each inspectee has inherently an inspector assigned. Furthermore, it makes sense to inspect always the local inspectee due to the ecient local inspection. Then, the whole IG logic is encapsulated into each peer. In other words, we deal with sets of two-player games. This architectural type has several advantages compared to the initial approach. In addition to the ecient inspection at least of the local inspectee's inspection target, the inspectors uniquely assigned to an inspectee in terms of inspections. Hence, they are inherently synchronized and double inspections are not possible. This simplies also the IG model: the EIP and MEIP values can be omitted. Now, only the one assigned inspector's strategy q must be considered by an inspectee during the own strategy choice. This supports the system designer applying the IG to individual needs and simplies BRS graphs as mean for system analysis.

.. Adaptation to System Dynamics

In order to attain a dynamic IG model, the enhanced version has the following objective: a whole interval T shall be secured by providing proofs for all operations within such time interval. To this end, the inspection target will be -in contrary to the initial IG approach -dynamic in its size. This normalizes the meaning of a peer's position in the dissemination structure. Those with a high message load need to maintain a correspondingly large inspection target. As we will see in the next section, this objective has also a simplifying eect on the violation detection function g.

The enhanced version does not use a parameter calibration. Instead, all payo values are calculated in a dynamic way by adapting the current system state. This is done by monitoring the message load value. Furthermore, a more stable approximation is calculated over time. The monitored message load is in the following denoted as l 0 and the approximation l + . Similarly, the players monitor the other player's behaviour in order to approximate the strategy over time. This is wanted by the system designer to sharpen the inspectee's possible calculations. The inspectee is informed when an inspection occurs, while the inspector approximates by means of detected violations. This information is denoted as q + and p + , respectively. The calculation of these values will be detailed in the next section.

. The details of the enhanced IG approach's major dierences to the initial one are introduced now. As in the last chapter, all variables and their values are clearly arranged in table ..

.. Inspection Target

The enhanced IG version uses the same inspection target mechanism as the initial version; it is thus not detailed here. However, the dierent inspection architecture causes a slight change of the inspection sequence, which is visualized in gure .. Being physically present at the inspectee, an inspector makes only a copy of the local inspection target. Then, he requests copies of those communication partners indicated in the local one. The actual control of the inspectee (inspection procedure) is done and a punishment induced in case of a detected PoM. A small implementation detail shall be mentioned here. The delay of requesting and transmitting the copy of the others may lead to a loss of the last recent proof messages and thus possibly a PoM. To cope with this problem, the inspection target contains a further backup history. Proof messages that should actually be removed from the history will be deposited in the backup history, again in a FIFO manner. However, this additional history serves only as mean to make the corresponding messages accessible. Proof messages that are not related to the corresponding IG are ignored.

The proof history is dynamic in size. It can be considered as a data structure such as a linked list, which grows with the message load that actual occurred. However, for the payo calculation, a history size must be determined for a game, whose exact message load value is not yet known. Therefore, an expected history size is used as shown in equation .. The expected history size h + considers an expected load value l + multiplied with the amount of proof messages r per message transfer. The value h + will be used during the payo value specication, while the expected load l + is detailed afterwards in section ...

h + = rl + (.)
.

. Payo Values

The payo values dier from those of the last chapter in terms of two aspects: the monitoring of the message load value (represented by l 0 ) and the the omission of the EIP value. Here, we concentrate rather on these dierences in the explanations. For further information about their composition, the reader is referred to the initial IG (section .., page ).

• b: violation benet As for the initial IG, violating is considered worth twice as collaborating, designed by means of a weighting value w b = 2. With the monitored message load, the benet calculated as in the following:

b = l 0 w b
• d: non-detection costs (damage)

For the system damage, we assume again that the violating peer is in the middle of the dissemination route to all n ⇤ g s subscribers. In the initial IG model, m inspectors were equally sharing the damage, thus having the value m in the denominator. This is not the case here due to the xed assignment of an inspector to an inspectee. Hence, m is omitted and the cost value is dened as:

d = w d l 0 ng s 2 (.)
• c: inspection costs This cost value depends on mechanisms used for the inspection target and is equal to the initial version. However, please remember that the history size h is actually a dynamic value, depending on the message load. Since actual message load is not yet known for the current game, the cost calculation uses the expected history size of equation .:

c = 2h + r (.)
• a: punishment costs The punishment costs are again calculated relative to the non-detection costs. Here, the variable m is -analogue to damage d -omitted due to the pure two-player game:

a = w a d (.)
.

. Value Approximations for System Dynamics

As mentioned the rational players may draw conclusions from the circumstances. Therefore, they monitor some values and calculate approximation to support their game strategy decision. To this end, several possibilities are available such as the arithmetic mean, a median calculation or exponential smoothing. The latter one is a well-known technique for time series of data. Hence, it is appropriate for value approximations over time and will be used here.

The load value approximation l + for the next IG related to interval T is calculated based on three values. This is the monitored load value l 0 (amount of transferred messages) for T -1, its prior approximation and a smoothing factor a l . The message load approximation is shown in equation .. For the simplicity's sake, we omitted the index T and use l + instead of l + T .

l + = a l l 0 T-1 +(1 -a l )l + T-1 (.)
Similar to the message load for the inspector, the inspection probability represents an important value for the inspectee, which possibly dynamic. The inspectee approximates for the BRS calculation a smoothed inspection probability q + . To this end, the inspectee takes into account if he suered or not from an inspection during the last interval, which is represented by q 0 T-1 2{0, 1}. The approximation is done with the same principle as for the message load and shown in equation . (analogue to l + we omit index T for q + T ).

q + = a q q 0 T-1 +(1a q )q +

T-1

(.)

. multiplier for T so that t i ⇤ T = T insp t s -multiplier for T so that t s ⇤ T = T sa f e q game strategy probability of an inspector to perform an inspection p game strategy probability of an inspectee to violate l 0 dynamic value monitored message load value of an interval T q 0 dynamic value monitored value if an inspection happened or not (q 0 2{0, 1}) p 0 dynamic value monitored value if a violation happened or not (p 0 2{0, 1}) l + dynamic value approximation to the message load (# of transferred messages) q + dynamic value approximation to the inspector's strategy q p + dynamic value approximation to the inspectee's strategy p h + dynamic value approximation to the expected history size (used for payo calculation) h dynamic value size of the proof history (inspection target) a q . smoothing factor for the inspection probability approximation a p . smoothing factor for the violation probability approximation a l . smoothing factor for the message load approximation r amount of proof messages to secure one hop-to-hop transfer g amount of multi-cast groups in the system g s . In the same way, the inspector may approximate the inspectee's chosen strategy, the violation probability p. This is shown in equation . with p 0 T-1 2{0, 1} for detected violations. To to take also non-detected violations into account, the factor 1 qg is added (again, omitting index T for p + T ).

p + = 1 qg (a p p 0 T-1 +(1 -a p )p + T-1 ) (.)
Approximating the inspectee's strategy is introduced here for the sake of completeness. Although not used in the remainder, the inspectee's strategy is possibly dynamic, too. Then, such approximation may be used to discover the individual preferences or as basis for feedback mechanisms in order to adapt the inspection intensity.

The low smoothing factors for the strategy approximations a q = a q = 0.1 provide some smoothness, i.e. statistical robustness against uctuations. In contrary, the factor a m = 0.5 is higher to adapt faster to the message load.

.. Violation Detection Function g

The violation detection function g is substantially aected by the modication that the inspection target is dynamic in size. In order to make the consequences comprehensible, we will shortly recall the timing details that were discussed for the initial IG in section .. (page ).

To ush the proof history, all PoMs need to be removed from proof history, which is done if the peer transfers at least h r messages. As in the last chapter, the needed time can be considered as T sa f e = T ⇤ t s with t s being detailed in the following. Since function g is used for the strategy choice, the expected values l + and h + are used here.

t s = h + r l + = h + rl + = rl + rl + = 1
Furthermore, the average time interval between two inspection shall be denoted by T insp = T ⇤ t i with t i being detailed as in the following:

t i q = 1 ⌘ t i = 1 q
PoMs are still in the history during an inspection for either of the following two cases. Being equal to those of the last chapter, they are only listed again for the sake of comprehensibility.

. The inspectee violates (probability p).

. The inspectee violated but collaborates now to ush all violation proofs out of the history.This happens with a probability of

T sa f e
T insp = t s t i . With this preparation, we can dene function g as shown in equation .:

g(q, p)=p + t s t i (.) = p + 1 1 q = p + q
Here, we can see the eect of the dynamic adaptation of the history size able to store all proof messages for one T. The system dynamics in terms of varying message load is compensated and the detection probability not any more depending on the proof history or message load values. Nevertheless, this function may still exceed the probability bounds. Analogue to the initial IG approach, this will be considered in the adapted function g ⇤ , which is used for the payo functions.

g ⇤ (q, p)=

> <

> : .) .

1 if g(q, p) ≥ 1 g(q, p) else (
.

Since the EIP value is not used anymore, the inspectee considers the inspector's strategy q instead of s ⇤ (p, q) for payo functions. These are I( p, q ) for the inspectee and C( p, q ) for the inspector. Both have the same structure as those of initial IG approach (see section ., page ) but make use of the formalizations of this chapter (e.g. payo values, function g).

Please not that, for an implementation, the inspector would replace p by the approximation value p + and the inspectee q by q + . The BRS graph based on the payo functions of the enhanced IG approach is shown in gure .. The omission of the EIP values increases its comprehensibility: the dashed purple curve indicates the inspectee's BRS only with respect to the inspector's game strategy q. The inspector's curve remains without changes: the continuous blue curve indicates his BRS for a given inspectee's game strategy p.

Three targeted collaboration values are indicated in this BRS graph together with the corresponding inspection probabilities. These are the collaboration value (1p)=0.6 with the predicted inspection probability of q = 0.2, a collaboration value (1p)=0.8 with the corresponding inspection probability q = 0.29 and nally a full collaboration (1p)=1.0, which is reached at q = 0.45 according to the IG mechanics. .

After presenting all game details, the enhanced IG is evaluated by a simulation. Again, this is done with Peersim and an adapted version of RCourse using Scribe and basic gossiping. All parameter values used during the simulation are indicated in the notation summary.

.. Network & Simulation Setup

The system consists of n = 200 inspectees but no dedicated inspector peers since the logic is integrated as IG network layer to the inspectee peers. In order to verify some dynamics, the simulation lasts time intervals T. The subscriptions as well as generated trac is equal to the initial IG of the last chapter. The published messages per T (each one having in average subscribed inspectees) is considered as basic load.

The evaluation especially focuses on the system dynamics. This is done by varying the message load as well as the inspection probability twice during runtime. Latter one represents a change of targeted collaboration levels through a varying inspection intensity. A simulation overview is shown in gure .. The simulation starts with basic load starts in time interval T = 40 and lasts until the half of the simulation (T = 500). Then, it is increased to the triple ( published messages per T). This high load persists until T = 800, where it is decreased to the double of the basic load ( published messages per T). This persists until the end of the simulation. Altogether, the simulation consists of published messages (further message transfers not included). In addition to the changing message load, the simulation provides dynamics in terms of the targeted collaboration levels by injecting new inspection probabilities q during the simulation. The three values are used that were already indicated in gure .. In the beginning, we target a collaboration value of . (q = 0.29). In T = 350, the targeted degree is changed to . (q = 0.20). Full collaboration is then targeted in T = 700, which lasts until the end of the simulation.

Let us denote the term epoch as a set of sequential time intervals that provide the same parameters. By changing two parameters (message load and inspection rate) twice, the simulation consists of ve epochs, i.e. four parameter changes (gure .). This dynamics is simplistic to some degree (e.g. no use real world work load traces). However, it enables to evaluate the general adaptability of the IG approach and to draw conclusions from its preferences. .

. Simulation Results

As in the last chapter, only the MQ graphs (median with quartiles) are presented here, while the corresponding VD graphs are available in appendix C (page ). Please note again that the arithmetic mean in VD graphs is not equal to the median due to statistical reasons.

Figure . shows the inspectees' approximations to the varying inspector game strategy. Precise approximations of the three adjusted inspection probabilities ., . and . are noticeable (though small variances are existent). The graph shows also the adaptation speed of the smoothed value. The actual value is approximated within about time intervals with the given parameters.

The further simulation results of the enhanced IG approach are shown in gure .. MQ graphs are given for both the Scribe system (left column) and the gossiping system (right column). The rst row shows the message load approximations as described in the game details section, the middle row the chosen collaboration values and the bottom row the inspectees' payo value. The load graphs clearly show the three adjusted load values. Here, the Scribe's ecient but heterogeneous load distribution provides some variances. In contrary, all values of the gossiping system are close to the median but has higher load values.

The middle row of gure . shows the simulation results in terms of the collaboration. Both examined systems attain -despite system dynamics and different dissemination styles -in average the three desired collaboration degrees ., . and .. This veries the general functioning of the IG approach and also the ability to adapt to system dynamics. A small variance is given of about . (quartiles) from the median. The adaptation speed is with about intervals analogue to gure .. This makes sense due to the importance of the inspection probability approximation for the inspectee. The collaboration graphs have one conspicuous feature: there are some uctuations for .. The reason is comprehensible by means of the BRS graph (gure .). For a targeted collaboration value of about 1p ⇡ 0.39, it becomes not worth anymore for the inspectee to collaborate. The value drops directly down to zero. Hence, due to variances, some inspectees consider a tar- geted collaboration below this threshold: they do not collaborate anymore. This is clearly shown in the corresponding VD graphs in gure C. (in appendix on page ). In order to verify this aspect, a further simulation has been done with an inspection probability slightly increased by .. This results in targeted collaboration values of ⇠ 0.87, ⇠ 0.7 and .. The result graphs are presented in gure ., arranged in the same way as in gure .. Now, the uctuation should be reduced. Furthermore, the targeted collaborations are again achieved as predicted.

Although using the same simulation setup, the payo graphs (bottom row in gure .) are diering signicantly for both systems. Hence, the dierent dissemination structure must be the reason, which is interpret as in the following. In the Scribe system, the heterogeneous message load values cause more outliers in terms of the targeted collaboration value. They are in turn detected and punished and the average payo keeps negative during the whole simulation. Especially for the targeted full collaboration value the punishments of detected violations aect the whole averaged payo without being mitigated (or only of a negligible amount) by the increase through non-detected violations. The payo values of the gossiping system are (due to the homogenous load values) more deterministic: the lower the collaboration value the higher the payo through violation benets. Similar to the Scribe system, some outliers are given for full targeted collaboration. The imposed punishments outbalance the increase of (also possibly not detected) violation benets.

. This chapter introduced the enhanced IG approach, which is based on the initial one of the last chapter . It enables a system deployment over selsh peers, adapting to system dynamics such as a varying message load or targeted collaboration levels. Hence, the IG meets the research challenge (C) stated in the introduction.

The dierences of the enhanced IG to the initial one consist basically in another inspection architecture and the ability to cope with system dynamics. The enhanced version realizes the inspector as network layer at the inspectee's machine. Furthermore, to cope with dynamics, it follows the general objective to secure a whole interval T. To this end, all related collaboration proofs are stored in an inspection target that is dynamic in its size.

The chapter presented all details and showed how to apply the IG framework to a specic use case. A simulative evaluation veried the functioning of the approach. The dynamics were evaluated by means of epochs, i.e. phases of not changing system parameters. Adaptations to new environmental parameters are done within about time intervals, which can be adjusted by game parameters.

ADISCUSSIONOFTHEAPPLICABILITYTOREALW ORLDSYSTEMS

After the introduction of the IG approach in the last chapter, we discuss now some real world aspects. This is the possible implementation into user applications and the practical meaning as reliability technique for user and administrator.

. The IG framework is not a reliability technique in itself. Instead, as a monitoring approach, the implemented mechanisms are taken into account to control the correct functioning of a peer. All information are integrated into the IG model and collaboration incentives are given as needed. It is independent from the system architecture and the considered reliability mechanisms can be chosen correspondingly to individual needs. The IG framework is versatile and can for example be applied to any system where logs are generated.

The practical objective of the IG framework is (among a behaviour analysis) to attain a targeted collaboration level. In contrary to the thesis' assumptions, real world systems provide typically altruistic peers. Hence, the actually reached collaboration will be (to some degree) higher than the targeted one. Due to this benecial eect, the resource utilization can be further reduced if the actual amount of violations is considered.

Despite its exibility, the framework design is not a universal remedy. The peer's goal(s) and preferences are typically not known but only how to prevent specic failures. The mechanism choice can also be challenging concerning the trade-o between reliability and resource utilization. From a comprehensive point of view, the IG framework has two major challenges:

• Technical: A peer's misbehaviour must clearly be provable.

This challenge consists of creating secured (not circumventable) proof logs and to provide means for a secured and correct inspection of these logs.

• Structural: A peer's individual preferences must be mapped to game parameters. Preferences such as the violation benet are diering along the peer's and unknown to a system designer. He must estimate them to design appropriate game mechanics.

The technical challenge are under active research and neglected for the discussion here. However, the structural challenge is an important and unsolved drawback for real world application. To demonstrate the proof-of-concept, it was compassed in the thesis by using values that are equal and supposed to be correct for all peers. This structural drawback will be in the following (among others) illustrated by means of the BitTorrent application. . This section discusses the related between and user interfaces. To this end, the BitTorrent application is used that was presented in the introduction (see gure . left on page ).

.. Meaning for the user

The majority of personal goals require modications of the application logic itself or the infrastructure. However, some applications provide options that can be considered as selshnessdriven violations. An example is the BitTorrent user interface, shown as mockup in gure .. Limiting or capping up-/download bandwidths is a feature of the application functionality. Then, only the permitted load is transferred and remaining network messages are dropped. This has direct impact on IG's collaboration value p.

However, the user interface can in turn be used to achieve collaboration as illustrated in gure .. A minimum upload rate of kB/s is required, while the user tries to use kB/s. Such regulating mechanism can already be interpreted as punishment by the user. In fact, reducing the bandwidth has been used in the last chapters as punishment in the IG. The lower part in the gure illustrates how a punishment could be realized with quota settings: the download rate is limited to GB for days. Here, the user is informed within the control interface.

Figure . shows two further possibilities: message boxes and an information area in the main window. Both are commonly used in several applications (e.g. the Firefox browser).

.. Meaning for the system administrator Similar to the user, the IG can be easily integrated in the administrator interface. An example is illustrated in gure .. The Game Parameters tab uses the values of the enhanced IG approach introduced before. The second tab, Mission Central, contains some elements for the IG operation. Additional tabs can detail further collaboration incentives.

Figure . illustrates the Mission Central tab with practical functionalities for the IG operation. It shows an implementation aspect, denoted here as Permitted Violation Range (PVR) covering, to trigger automatic warnings and punishments. Its principle is that failures can be permitted to some degree or time. In the PP video streaming, this corresponds to a slightly reduced frame rate. Collaboration values lower than the PVR are prohibited and should be directly punished; this region is also denoted as Non-Permitted Violation Range (NPVR). For example, warnings are sent if the PVR is used for at least %, i.e. for 0.65  (1p ⇤ ) < 0.665.

Figure . (left) illustrates the PVR (using the mockup settings) for the IG with BRS graphs. The PVR thresholds can for example be determined with simulations by evaluating the reliability capabilities. This illustrative example shows on the one hand the simplicity of an IG integration into the application user interface. On the other hand, it brings another question up: How correspond the user settings to the IG model with payo and collaboration values in particular? Practically spoken, why should we require bandwidth limitation value of kB/s (e.g. to reach a PVR of .) and not values such as kB/s or kB/s? This corresponds to the question of determining appropriate IG payo values (and possibly other secondary parameters), which may be even dynamic. For example, a system may need temporarily a higher bandwidth. Fixed game parameters (represented through a application's conguration) would change the actual meaning of the parameters for an IG. This shows the challenging aspect since serval circumstance or the users' individual preference are not necessarily known to the administrator. A promising solution approach are feedback mechanisms to automatically determine parameter values. This is considered as possible future work but further outlined in the remainder of the thesis. Ideally, the population strategy (PS) moves directly to the Nash equilibrium (NE).

.

The IG used in this thesis had the strong assumption of completely independent games. However, let us consider now the following more realistic assumptions:

• The game type is changed to a repeated or evolutionary game. The IG players' strategy may cover several games and the payo does not necessarily depend on a single game.

• An inspectee is not anymore fully independent but takes into account the other inspectees' strategies for the own game strategy choice.

Though these assumptions make the game mechanics more complex, the resulting IG model is closer the real world. Selsh individuals may now strategize over time and they may learn from other inspectees. An example is the situation where a user asks some friends for seemingly benecial bandwidth limitation settings of BitTorrent.

The adaption can cause further challenges. For a better understanding, let us consider the inspectees as a population. For the game designer, it appears as representative agent who plays the Population Strategy (PS) as mixed strategy. Then, the collaboration incentives shift the PS to the desired point, e.g. the Nash equilibrium (NE). This is visualized in gure . for a two dimensional strategy space. However, the strategy dynamics -especially in consideration of the group dynamics -may lead to other movements. Some examples are presented in gure .. In the following, we denote the term orbit as the abstract characterization of a random movement converging orbit departing orbit stable Orbit PS movement relative to a desired point, here represented by the NE (we omit the intuitive meaning of moving 'around' another object). Random movements will not necessarily result in a stabilized system state as the converging orbit. With a departing orbit, a stabilized situation is neither reached, while the PS is actually moving continuously away from the NE. Finally, a stable orbit is characterized by a periodical PS movement.

The PS movements can also be caused by other reasons than group dynamics. Figure .  shows the simulation results of a simple feedback mechanism applied to the enhanced IG approach. Based on an approximation of the inspectee's violation strategy, the inspection rate is in-/decreased until a targeted collaboration level (straight green line) is reached. The approximation delay causes the strategy uctuations around the target collaboration. In the context of this discussion, these uctuations represent a stable orbit, while the movement passes even the target collaboration value itself. In addition to a dynamic PS (or inspectee strategy for the two player game), also the NE itself can move, which possibly aects the targeted collaboration level. A dynamic NE is for example given when essential game parameters (e.g. damage) change. Analogue to a moving PS, reliability mechanisms may weaken the impact or even tolerate it. This is not feasible for the general case and the dynamics should be directly taken into account during the game theoretic considerations.

To summarize, the inspectee's strategy as well as the NE (i.e. the population strategy) point should be considered as dynamic values when the IG is applied to real world systems.

The system and strategy states should be evaluated over time and game parameters adapted appropriately in order to reach the NE and/or the targeted collaboration level. This requires another modied version of the IG able to handle these dynamics. Such an evolutionary game model is not in the scope of this thesis and declared here as possible future work.

Part V CONCLUSION AND FUTURE WORK

This last part concludes the thesis by discussing the contributions in terms of the research challenges. Finally, some possible future work is presented.

.

RCourse is a library for the network simulation environment Peersim. As practical contribution, it supports the user in performing simulative studies with a special focus on robustness issues. All essential steps in the simulation workow are facilitated or even completely taken over by RCourse. Meaningful simulations can be launched once the development of the peer's logic is completed. It allows to study the impact of selshness-driven protocol violations on the system functioning and meets thus challenge (B). RCourse contributes also to challenge (C) by interacting with the IG framework. Quickly launched simulations evaluate the functioning of the IG approach and obtain desired information e.g. needed collaboration level. In addition, RCourse contributes to improve the qualitative BAR tolerance evaluation by facilitating the aggregation of more objective quantifying values. To this end, RCourse provides pre-dened simulation scenarios based on the same metrics (the taxonomy of failures). An example is shown in table . with values from the simulation results of gure . (page ), enriching the prior table .. The additional values indicate the percentage of correct system functioning in the presence of peers that violate with the probabilities 0.1 and 0.3.

During the study of the thesis, RCourse turned out to be a crucial tool in terms of the IG model calibration and verication. By starting only one script, the whole simulation workow was taken over by RCourse, up to the result graph generation (see table A. in appendix A for an overview of all graphs). The design principle simplicity of utilization (comprising also time/work savings) is thus fully realized. The isolation failure evaluation is given by the pre-dened scenarios, which were helpful to identify specic reliability capabilities. Being simplistic to some degree, real world network traces would be an interesting extension. The principle adaptability to individual needs was reached in two aspects. A system designer can adapt the logic of a workow phase by relying on the given les (simulation scenarios, analysis script etc.). He can furthermore, due to the modularity of the workow itself, substitute a whole phase (e.g. result analysis) by individual tools. Overall, RCourse provides a broad exibility and provides insights to a distributed system's behaviour with high time/work savings at the same time. Ideally, simulation results can be obtained "with one click". .

The enhanced IG framework of chapter represents a solution approach to meet challenge (C). Exemplary applied to PP based video streaming use case, it showed the ability to deploy system over selsh-driven peer and to achieve a targeted collaboration level. An evaluation veried the functioning considering some system dynamics.

Although the IG framework itself is directly related to challenge (C), the whole part is dedicated to IGs as mean against selsh peers. This is done straightforward from theory to practice. As theoretical contribution, the initial IG of Dresher [] was generalized and extended by the the possibility false negatives. This enables to model the realistic situation where violations are not detected during an inspection due to limited resources. A NE calculation for all games showed furthermore that the extension shifts the NE linearly proportional to the probability of non-detection. The introduced models can be used for a broad spectrum of (possibly interdisciplinary) applications. The subsequent chapter discusses several real world implementation details such as inspection architectures. An interesting outcome was identied for the case where multiple inspections impose only one punishment. Games with multiple players can be represented as sets ofgames, which simplies the analysis. After the IG framework as practical contribution, a possible implementation was discussed by means of the example application BitTorrent. It demonstrates the simplicity of realization but outlines also challenges and possible future work; the latter one is addressed hereafter.

On the whole, the IG framework enables a new way of achieving reliability in distributed systems. It is also able to ll the BAR tolerance system design gap. This is illustrated in gure .. Using a structured approach for the development process, a system designer reaches a specic implementation beginning with an abstract goal. The framework design provides a exibility in terms of used system architecture and mechanisms to consider any selsh goal. .

The thesis' contributions have several relations and possible interactions. This is illustrated by gure ., outlining also design principle that was mentioned in the introduction to meet the main research challenge (see chapter ., page ). A mutual exchange should be given between the actual system behaviour and the theoretical model to reach a specic implementation from an abstract starting point. This has been identied during the thesis as important aspect for the implementation of reliability mechanisms. RCourse interacts with the IG model in terms of parameter calibrations. Quickly launched simulations evaluate system properties to determine an appropriate collaboration level or payo values. Based on these parameters, the IG approach allows a BAR tolerant system design, which can in turn be evaluated with RCourse (compare also with gure .). The utilization of Publish/Subscribe was an adequate use case system. The study could take place at specic system implementations that are close to real world systems. At the same time, the pub/sub paradigm represents the basic user needs (requesting/consuming information), thus being applicable to a broad range of systems.

The IG contribution has a fundamental research character with a proof-of-concept relevance in terms of real world implementations. Nevertheless, it has a high scientic relevance. The IG approach oers a complete new way of designing BAR tolerant systems as a whole. Reliability mechanisms -system-inherent as well as articially added -can be considered within one comprehensive model for the behaviour analysis of selsh peers. The IG approach gains a general purpose applicability and can be applied wherever entities are controlled to avoid some kind of violations. An example is the inspection of log les (commonly used router, operation system etc.) in order to detect violations.

The study demonstrated clearly the principle of the IG framework. A system designer can benet from the IG mechanics for behaviour modelling and parameter calculations. However, appropriate payo values must be used. This causes further challenges since selsh peers have inherently individual preferences. These are rarely known, probably not equal among the peers and could even by dynamic. "Good" and "dynamic" estimations, however these terms are determined, are thus needed to seriously pass the step to broad real world applications. Due to the heterogeneity and dynamics, only (semi-)automatic feedback mechanisms represent promising approaches.

Preparations and BAR Tolerance Evaluation

RCourse Benchmarking Library -assists the user in simulation workflow (time/work gains) -enables to quickly launch simulative evaluations Inspection Game Approach for Distributed Systems -model a complex and interdependent decision landscape for behaviour analysis -calculate parameters to attain targeted degree of collaboration -structured approach for the development of BAR tolerance mechanisms -architectural classification normalizes heterogeneous notions and interpretations -taxonomy of elementary failures of a peer may serve as base for BAR tolerance evaluations -evaluation of BAR tolerance capabilities -RCourse: determine an adequate targeted collaboration level for the Inspection Game -Inspection Game: create a system model that can be evaluated with RCourse

Interaction of RCourse and the Inspection Game

POSSIBLE FUTURE WORK

The IG approach provides several possibilities for further research. Three are introduced here representing signicant improvements.

. Colluding selsh inspectees collaborate in terms of their violations in order to reach an overall objective. In other words, they try to increase the payo of the group as a whole. As example, the following scenario may arrive when collaborative interactions of two peers are secured. Figure . illustrates this threat at two network structures. Let us consider an optimal case for the selsh inspectees where a network segment is fully consisting of colluding peers. Then, the colluding peers form a colluding black box. The border peers violate by removing any PoMs and they get (probably) punished. However, due to the missing proofs, the peers' behaviour inside the colluding black box cannot necessarily be clearly proven. In other words, they could violate among the collaboration and remove or falsify the violation proofs afterwards. The problem of colluding peers in distributed systems starts to be addressed by the research community (see for instance [, ]). Hence, this issue provides many possibilities for subsequent research with regard to the IG approach. One example question concerns the ratio of colluding and non-colluding peers that allows to form the black box. Possible solution approaches could identify the black box frontiers and isolate it from the network.

: border peer of colluding black box : peer in a network : violating peers inside the colluding black box . Further possible future work is related to the representation of real world circumstances to game parameters. As discussed before, a general drawback of the IG approach is the determination of the payo values. Among others, they need to represent appropriate user preferences (e.g. violation benet) and also a suitable determination of system damage. This is a challenging task for the system designer. Especially the meaning of the violation benet and punishment depends on the corresponding users. Furthermore, these values are presumably varying among the users and possibly even changing over time. These aspects emphasize the need of further research to support the mapping of real world circumstances to appropriate payo values. Ideally, some feedback mechanism(s) would allow a dynamic adaptation to the individual user preferences. A simple mechanism is already shown in gure . (page ).

Here, the inspection rate is in-/decreased until the targeted collaboration is reached, while the strategy approximation delay creates uctuations around the targeted value. However, this is only an exemplary mechanism and more elaborated ones are desired.

Another similar issue has been discussed before in this chapter and can be described by the following question: How to map the application settings and user behaviour to game parameters such as the collaboration strategy? Again, some feedback mechanisms are imaginable that adapt the meaning in form of game parameters to the dynamic system state. However, it has not yet been addressed and is still an open problem for IGs in particular.

. Rational selsh individuals in the real world can strategize over time and exchange information with other individuals (see also the discussion in section .). Hence, a possible improvement consists in the extension of the IG approach towards an evolutionary game model. This complicates the model itself (and thus also the analysis), however, it has several advantages. For example, it enables the analysis of player strategies across several games. Another example is related to section . (page ) where inspections are considered as a population. Selsh individuals may be inuenced by other in their strategy choice, e.g. by exchanging seemingly benecial application settings. Then, the PS may be dynamic, possibly not reaching a targeted strategy value such as the Nash equilibrium or a collaboration level. An . evolutionary model could then identify such strategy movement. Game parameters could be dynamically adjusted such that the population's strategy is redirected to the desired strategy value. This is illustrated in gure . with regard to the original movements of gure .

(page ).

Part VI

APPENDIX

The appendix provides additional details to several contributions of the thesis. n i = 20 q = 0.3 n i = 20 q = 1.0

  der Dissertation wurden IGs als Lösungsvorschlag für das gegebene Problem auf verteilte Systeme adaptiert. Dazu wurde das initiale IG Modell zunächst durch die Möglichkeit erweitert, dass Protokollverstöße während einer Inspektion nicht entdeckt werden (false negatives). Der IG Ansatz ermöglicht die Modellierung des Kooperationsverhaltens in verteilten Systemen und die Berechnung von Systemparametern um das anvisierte Kooperationsniveau zu erreichen. Der Ansatz ist als generisches Framework konzipiert und kann 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 IG Ansatz überwacht die Korrektheit des gesamten Kooperationsprotokolls. Dies stellt hinsichtlich der Funktionsfähigkeit eines Systems einen neuen Ansatz dar. Die Anwendbarkeit wird weiterhin durch RCourse unterstützt, einer Software-Bibliothek, welche Simulationen hinsichtlich der Robustheit verteilter Systeme vereinfacht. Daher eignet es sich insbesondere zur Bewertung des IG Ansatzes und Kalibrierung von Parametern. CONTENTS . Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thematic Backgrounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. A Clarication of Terminology . . . . . . . . . . . . . . . . . . . . . . .. The Publish/Subscribe Paradigm . . . . . . . . . . . . . . . . . . . . . . Vision & Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Research Challenges & Contributions . . . . . . . . . . . . . . . . . . . . . . . . Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenge A: Reliability & BAR Tolerance Evaluations . . . . . . . . . . . . . . Challenge B: Robustness Evaluations of Distributed Systems . . . . . . . . . . . Challenge C: Tolerating Selsh Peers . . . . . . . . . . . . . . . . . . . . . . . . Inspection Games for Reliable Distributed Systems . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Structure for Comprehensive Evaluation . . . . . . . . . . . . . . . . . . . . . .. Architectural Classication Scheme . . . . . . . . . . . . . . . . . . . .. Classifying Scribe and Gossiping . . . . . . . . . . . . . . . . . . . . . .. Taxonomy of Byzantine Failures . . . . . . . . . . . . . . . . . . . . . . BAR Tolerance Capabilities of Publish/Subscribe Systems . . . . . . . . . . . . .. The Simple Comprehensive Reliability Evaluation Model . . . . . . . .. A Qualitative Reliability Evaluation . . . . . . . . . . . . . . . . . . . . Meaning for the Research Challenges . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . / : . A Short Excursus to Pub/Sub Systems . . . . . . . . . . . . . . . . . . . . . . . .. Scribe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Gossiping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Underlying Research Principles For Practical Evaluations . . . . . . . . . . . . . Overview to RCourse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. RCourse Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . Simulative Evaluations with RCourse and Peersim . . . . . . . . . . . . . . . .. Utilization and Experimentation . . . . . . . . . . . . . . . . . . . . . x .. A Note on Multi-Process Simulations . . . . . . . . . . . . . . . . . . . .. Adaptation to Individual Measurements . . . . . . . . . . . . . . . . . . Meaning for the Research Challenges . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

OI

  ....................................................................... . Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thematic Backgrounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. A Clarication of Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. The Publish/Subscribe Paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vision & Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Research Challenges & Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure . :

 . Figure .: Limiting bandwidth is a realistic issue. The functionality is integrated in the settings of the PP software BitTorrent (left) as well as in the low-budget router D-Link DIR-(right).

Figure . :

 . Figure .: The gure illustrates a classication from Nielson et al. [],which is used in the thesis. In this context, selsh behaviour is considered as synonym to rational behaviour, assuming further a personal goal that diverges from the system goal(s).

Figure . :

 . Figure .: Graphical overview to the Publish/Subscribe communication paradigm showing the interaction-style (left) and the position in the network stack (right).

Figure

  Figure .: Vision:The objective is a design concept to enable a system deployment over selsh peers to attain a targeted collaboration level.

Figure . :

 . Figure .: General approach: An inspection target maintains a peer's collaboration proofs. It is controlled by an inspector, who gives collaboration incentives (punishment) in case of detected PoM. The desired collaboration level is reached by an appropriate inspection rate.

Figure

  Figure .: Methodology: The IG is considered as framework for the system design. The application to an illustrative use case shows the utilization in detail and how collaboration is achieved.

.

  The current part introduced among others the thematic context and the thesis' research challenges. The remainder structured as indicated in the following.

  Figure .: Outline of the relation of approaches suitable to face selsh peers in distributed systems.Note that this distribution outlines only the author's impression of the reviewed works.

.

  The IG was initially introduced Dresher in [] in its simplest form: a two-player, nonzero-sum game. Further details to this class of games can be found in[, ]. Adaptations of the IG come under names such as Pursuit-Evasion [] or Customs and Smuggler games [].The dierent variants can be seen as belonging to the wider class of Search Games (see []). In this context, Cheung et al. proposed in a recent survey of autonomous search models [] a taxonomy structured around the three main components: the model of the searcher agent (the inspector), of the target agent (the inspectee) and of the environment. Similar to general GT, the majority of works are dedicated to IG model. For example, the inspectee can observe inspections and choose a strategy according to his self-interest []. In [], the authors generalize Gale's Theorem, in which each of two players has N resources that can only be used once during N stages. Other works considering IGs are[, , , , , , ].IGs were used for instance in industrial auditing for quality control and maintenance, tax inspection or crime control[, ]. Only few works are related to IT-related problems. For example,Chung et al. published recently [] a survey of Search and Pursuit-Evasion Games in mobile robotics. They present among others fundamental results, discuss eld implementations and highlight open problems. Another work of Antoniades et al. [] targets on agent control, also formulated as Search and Pursuit-Evasion Game. In the context of digital surveillance by drones, the authors present heuristic strategies to detect and capture evaders.

Figure . :

 . Figure .: Transformation of broker overlays to PP overlays by aggregating interests of clients.

•

  Failure A: Link/Node Crash • Failure B: Message Loss • Failure C: Message Tampering • Failure D: Content Pollution • Failure E: Message Misuse • Failure F: Information Leak • Failure G: Selsh Behaviour

  Figure .: The two pub/sub algorithms are oppositional in terms of reliability and eciency.

Figure

  Figure .: The Scribe system has a tree-based dissemination style. Two operations are exemplary illustrated for a multicast group: the subscription (left) and the publishing (right).

  Examples are Cyclon [], Scamp [], Vicinity [], HyParView [] and X-Bot []. Typical partial view sizes are about -, although the size has only limited impact system attributes.

Figure . :

 . Figure .: Informed gossiping realizes a deterministic dissemination ring based on the overlay ids.Further random transfers (r-links) improve the dissemination speed.

  Figure.illustrates the simulation workow with the supported steps by RCourse (continuous lines) as well as the possibilities for individual adaptations (dashed lines). RCourse enables time/work savings (goal .) already beginning with the rst workow step -the development of the dissemination algorithms that shall be simulated. By means of a set of Java classes, RCourse provides among others functionalities for data aggregation and write-out. Thus, the user can concentrate on the development of the algorithm itself, all other steps may be taken over by RCourse components. Further support is given for example by means of pre-dened simulation scenarios and scripts in the R programming language. They analyze the simulation result data set and automatically generate result graphs as pdf les. The design goal . was reached by modularizing the RCourse components among the workow steps. This loose coupling results in a modular architecture and facilitates the adaptation of the dierent steps to user specic needs. In order to fulll goal ., the RCourse library is complete in the sense that a simulative study can be directly launched once the algorithm development is completed. Indeed, two pub/sub systems have been developed for use with RCourse, which are included in the library. These are Scribe and gossiping that were described before. RCourse provides a basic as well as informed gossiping implementation, based on the membership protocols Cyclon [] and also HyParView []. RCourse is primarily targeting the computer networks http://rcourse.sourceforge.net/

.

Figure . :

 . Figure .: RCourse Java library consists of six main classes.

  Figure .: The result analysis with R scripts is organized in phases: the analysis scripts are started in phase (I), the result les are processed in phase (II) and pdf result graphs are generated in phase (III).

Figure . :

 . Figure .: Three examples show the utilization of RCourse components in the source code. The related code is indicated in blue/italic.

  The utilization of RCourse and Peersim is shown for the Eclipse Integrated Development Environment (IDE) in gure .. In general, three information must be specied that are listed below. The conguration les contain the actual conguration and are shown in appendix A in listing A. (rcourse_Base.txt) on page and listing A. (ES.-MessageLossLRV.txt) on page .

.

Figure . :

 . Figure .: If using the Eclipse IDE for running simulations, Experimentation Scenarios may be dened as presets as shown here for ES..

Figure . :

 . Figure .: Peersim supports only single-threaded simulations. However, RCourse enables a parallel simulation to some degree and an automated result aggregation.

Figure . :

 . Figure .: The graphs show evaluation results of selshness-driven message drops of Scribe (upper graph) and basic gossiping (lower graph). Latter one used a fanout value of .

  N D S ................... . A Basic Two-Player Inspection Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Generalization of the Basic Two-Player Inspection Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . Inspection Games with False Negatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Note to the Game Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O T I G A T D S ...................... . Inspection Game Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Inspection Game Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A I G F F D S .......................... . Approach Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Inspection Target as Monitoring Interface: Design Details . . . . . . . . . . . . . . . . . . . . . . . . . . . Game & Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . BRS Graphs for Behaviour Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A E D I G F ............................... . Approach Overview & Dierences to The Initial Approach . . . . . . . . . . . . . . . . . . . . . . . . . . Specication of Game Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Payo Functions & BRS Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A D A R W S ......................... . The Inspection Game as Reliability Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Inspection Game in User Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Impact of the User Behaviour on Inspection Game Challenges . . . . . . . . . . . . . . . . . . . . .

Figure . :

 . Figure .: The extensive form for an IG with one inspector and one inspectee.

Figure . :

 . Figure .: Inspection Game G(2, 1) in extensive form.

Figure . :

 . Figure .: The Inspection Game Γ(1, 1) is shown in extensive form. It corresponds to G(1, 1) but is extended by the possibility of false negatives.

.

  Table .: Summary of the results for the Inspection Games Γ(•, •), i.e. G(•, •) enriched by false negatives. Notice that solutions of Γ(•, •) are equal to those of G(•, •) divided by a factor g.

Figure . :

 . Figure .: This gure illustrates synchronized (left) and not synchronized (right) inspectors in terms of the inspectee selection. The id space is represented in a two-dimensional way with dots as inspectees. The dashed squares indicate the assignment of id regions to an inspector.

.

Figure . :

 . Figure .: This thesis considers for the sake of simplicity a linear dependency between violation opportunities and possible violation benet. However, non-linear relations are generally possible.

.

  Figure .: The IG must be adapted to a possibly innite operation of distributed systems. To this end, each of the the operations is mapped to single game and each game is then independently played. The inspection target holds collaboration proofs and is controlled by the inspector.

Figure . :

 . Figure .: Two possible inspector implementations are illustrated: as individual peers (with possibly multiple inspector instances on the peer) and as network layer at the inspectee's peer.

  Figure .: Four exemplary inspection architectures are illustrated.

  Figure .: A network layer can be added to the inspectee for maintaining collaboration proofs. It may also monitor system values or impose punishments as collaboration incentive.

Figure . :

 . Figure .: Two possibilities for a reactive game mode are shown. The left gure shows an external inspection initiation. Here, an external individual or logic (here a game master) instructs the actual inspector to perform an inspection. The right gure shows the internal initiation, where the inspectors decide on their own to induce the inspection.

Figure

  Figure .: Several (not mutually exclusive) ways to initiate an inspection are possible.

Figure . :

 . Figure .: An architectural overview is shown left in the gure. Dark boxes show the most important parts to be specied during an application of the framework. The corresponding inspection architecture is shown on the right side.

Figure . :

 . Figure .: The inspection sequence of a two player Inspection Game is shown in the context of a distributed system (left) and schematically focusing on the players' interactions (right).

Figure . :

 . Figure .: Overview to the inspection procedure.

.

Figure . :

 . Figure .: Best response strategy (BRS) graphs present the game result by visualizing the player's behaviour in an easy comprehensible way.

Figure . :

 . Figure .: The left BRS graph illustrates the specied IG and the right possible parameter adjustments.

Figure . :

 . Figure .: Two networks are used for the application of the Inspection Game: the Scribe system disseminates by means of a tree-based network and basic gossiping creates a clique network.

Figure . :

 . Figure .: These MQ graphs verify the prediction of the EIP function, which are ., . and .for the given parameters. The predictions are precise although some outliers exist with up to about . (%) from the arithmetic mean (see VD graphs in gure B., page ).

  Figure .: The result graphs for the gossiping system show the inspectees' payo (rst row), message load (second row) and collaboration values (third row).

  Figure .: The graphs show the simulation results for the Scribe system (all corresponding VD graphs are presented gure B. in the appendix on page ). The results comprise the inspectees' payo (rst row), message load (second row) and collaboration values (third, fourth row).

Figure . :

 . Figure .: In the enhanced IG approach, an inspector is completely deployed at the inspectee's peer (left in gure). The resulting inspection architecture is shown right in the gure. Inspectors control only the local inspectee, which creates sets of two-player games.

Figure . :

 . Figure .: The inspection sequence of the enhanced IG is shown in the context of a inspection architecture (left) and schematically focusing on the players' interactions (right).

Figure . :

 . Figure .: The graph indicates the players' best response strategies (BRS) for the enhanced IG approach and the given parameters (see notation summary). Three inspection probabilities are indicated with the resulting collaboration degrees according the the IG model.

Figure . :

 . Figure .: During the simulation, the message load and inspection rate, are changed twice.

Figure . :

 . Figure .: The graph shows the inspectees' approximations to the varying inspector game strategy in the Scribe system. The curves -median with quartiles -are analogue to the gossiping system (not shown here). See gure C. (page ) for the corresponding VD graph.

Figure . :

 . Figure .: The graphs show the simulation results for Scribe (left column) and gossiping (right column). The corresponding VD graphs are given in the appendix (gure C., page ).

.

Figure . :

 . Figure .: The inspection probabilities were increased by ., resulting in targeted collaboration values ⇠ 0.87, ⇠ 0.7 and .. Thus, the collaboration value variances are reduced for the epochs with 1p ⇡ 0.7. The VD graphs are shown in gure C. (page ).

Figure . :

 . Figure .: The IG mechanics can interact the user interface, as exemplary shown here for BitTorrent.

Figure . :

 . Figure .: Two commonly used examples of user notications are shown.

.

Figure . :

 . Figure .: The IG conguration for the administrator could also be realized as additional area in the control interface. In this gure this is shown for the general game parameters.

Figure . :Figure . :

 .. Figure .: An IG control interface allows to specify manual and automatic collaboration incentives (warnings, punishment etc.). It may also give a statistical overview.

.

  Figure .: The IG principle is shown as population with the square as two-dimensional strategy space.Ideally, the population strategy (PS) moves directly to the Nash equilibrium (NE).

Figure . :

 . Figure .: The general dynamics of the inspectees strategies may lead to several PS movements.

Figure

  Figure .: A stable orbit can also be reached by means of a dynamic inspection rate mechanism. The inspectee's collaboration value uctuates around the target collaboration.

OCT

  ........................................................ . Preparations & BAR Tolerance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . RCourse Benchmarking Suite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Inspection Game Approach to Achieve Collaboration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P F W ............................................................. . Colluding Inspectees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mapping the Real World to Game Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Evolutionary Game Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure . :

 . Figure .: The IG approach represents a framework for the design of BAR tolerance capabilities. As outcome, it enables to calculate parameters to achieve the targeted collaboration degree.

Figure . :

 . Figure .: The graphical overview outlines the relations among the contributions.

Figure . :

 . Figure .: Colluding peers can create black boxes. The border peers violate and sacrice themselves such that the colluding peers inside may perform undetected violations.

Figure . :

 . Figure .: An evolutionary game model enables game modications to redirect it movements of the population strategy to a desired point (e.g. Nash equilibrium).

OAD

  RC L C ..................................... B VD G I G A ..................................... C VD G E I G A ..........................A DETAILS TO THE RCOURSE LIBRARY COMPONENTSSeveral detail information are here given about the components of the RCourse library in order to process result data and generate graphs.Listing A.: Example source code of the R script to generate the graph D. Delivery Loss Rate for Experimentation Scenario ES. Message Loss with Loss Rate Variation. ============= plot diagram ============================== pdffilename <-"ES3.2 _ D5.1 __ MessageLossLRV-DeliveryLossRate.pdf" fullpdfpath <-sprintf("%s%s", pdffolder, pdffilename) pdf(fullpdfpath, width=w, height=h) _ avg + deliveryLoss _ sdev, 100 -deliveryLoss _ avg -deliveryLoss _ sdev, xlim = c( min(msgDropProps), max(msgDropProps)) ,ylim = c(0, 100), ylab = "not delivered messages (in %)", xlab = "lost messages (in %)", pch = charSquare, col = colorBlue, bg = colorBlue, axes=FALSE ) points( xaxis,1 0 0-deliveryLoss _ avg, col=colorBlue, bg=colorBlue, pch=charSquare) lines( xaxis,1 0 0-deliveryLoss _ avg, col=colorBlue, lwd=1, lty = "dashed") # print own xaxis labels corresponding to network size variations axis(1, msgDropProps, msgDropProps ) axis(2) box() mtext(" RCourse Benchmark -ES3.2 Message Loss (Loss Rate Variation) -D5.1 Delivery Loss Rate", adj =0, line=-1, col="grey" , cex=0.8, outer=TRUE) title(main="Delivery Loss Rate") if (gossiping){ source("util/generate _ subtitleText.r") mtext(t _ subtitleText, line=0.2, col="darkgray", cex=0.7) } dev.off() print( sprintf(" Created diagram '%s'", fullpdfpath),quote=FALSE ) ⇧ Listing A.: The Experimentation Scenario congurations, here for ES., are easy comprehensible.############################################################################################# # =================== NETWORK =================== K 1 # K wiring -'known' connections on the overlay _ PER _ CYCLE OBSERVER _ STEP 5 * TIME _ PER _ CYCLE simulation.experiments 10 simulation.endtime TIME _ PER _ CYCLE * CYCLES simulation.logtime 60 * TIME _ PER _ CYCLE # =================== RCOURSE =================== #rcourse.distrProcId 1 # recommendation: define this as argument rcourse.resultLog.filenamebase ES3.2probability: all nodes are malicious ⇧ Listing A.: The analysis script diRgrams_ES..r is called by the user and invokes all further scripts. --RESULT GRAPH GENERATION FOR ES3.2 ---", quote=FALSE ) # simulation configuration -for usage with rcourse traffic generator source("config/ES3.2 _ config.r") # === global / final ========================================= source("util/readin __ global-final.r") # read in data files source("global-final/ES3.2-D2.7 _ MessageLossLRV-NotificationOverheadRatio.r") source("global-final/ES3.2-D5.1 _ MessageLossLRV-DeliveryLossRate.r") ⇧ Table A.: Detailed scenario overview and result graphs generated by RCourse.

  Figure B.: The VD result graphs for the EIP value evaluation related to those of gure . (page ).

Figure

  Figure B.: The VD result graphs for the Scribe system related to those of gure . (page ).

  Figure B.: The VD result graphs for the gossiping system related to those of gure . (page ).

  graphical overview outlines the relations among the contributions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure . Colluding peers can create black boxes. The border peers violate and sacrice themselves such that the colluding peers inside may perform undetected violations. . . . . . . . . . . . . . . . . . . . . . . Figure . An evolutionary game model enables game modications to redirect it movements of the population strategy to a desired point (e.g. Nash equilibrium). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure B. The VD result graphs for the EIP value evaluation related to those of gure . (page ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure B. The VD result graphs for the Scribe system related to those of gure . (page ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure B. The VD result graphs for the gossiping system related to those of gure . (page ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure C. The graph shows the inspectees' approximations to q and is related to gure . (page ). . . . . . . . . . . . . . . . . . . . . . . . . . . Figure C. The VD graphs correspond to those of gure . (page ). Please note that the mean curve diers slightly to the medians of gure . with its statistically robustness. . . . . . . . . . . . . . . . . . . . . . Figure C.

  •, •), i.e. G(•, •) enriched by false negatives. Notice that solutions of Γ(•, •) are equal to those of G(•, •) divided by a factor g.. . . . . . . . . . . . . . . . Table . Summary of notation with values used in the example application of the Inspection Game. . . . . . . . . . . . . . . . . . . . . . . . . . . . Table . Notation summary with values used during the enhanced Inspection Game application. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table .

Table A .

 A Detailed scenario overview and result graphs generated by RCourse. Listing A. The analysis script diRgrams_ES..r is called by the user and invokes all further scripts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . rst part serves as overview to the thesis' research domain and objectives.At rst, the thematic context is introduced and some terminology claried. Then, the thesis' vision and methodology are presented and the corresponding research challenges afterwards.

	Part I
	RESEARCH CONTEXT & CHALLENGES
	xx

LISTINGS Listing A. Example source code of the R script to generate the graph D. Delivery Loss Rate for Experimentation Scenario ES. Message Loss with Loss Rate Variation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . Listing A. The RCourse conguration le 'rcourse_Base.txt' for Peersim structures the simulated overlay networks in form of functional layers. . . Listing A. The Experimentation Scenario congurations, here for ES., are easy comprehensible. . . . . . . . . . . . . . . . . . . . . . . . . . . . This

  Thematical overview to the main contributions of the thesis the GT considerations, the initial IG model is extended by false negatives and Nash equilibria calculations are introduced for all games. The extended game types are appropriate to model and analyze the interdependent strategy choice of selsh players with resource limitation constraints. By applying the IG approach to distributed systems, it represents the theoretic counterpart to RCourse. In combination they are able to realize the thesis' vision and to achieve BAR tolerant system implementations beginning from an abstract starting point. The GT foundations are published in[, ].

	PART III: PRACTICALLY EVALUATING ROBUSTNESS
	RCourse: Robustness Benchmarking Library for Peersim
	PART II: STATE-OF-THE-ART
	Preparations for Comprehensive Evaluation
	Evaluation of BAR Tolerance Capabilities
	PART IV: ACHIEVEMENT COLLABORATION WITH!
	INSPECTION GAMES
	Inspection Game Adaptation to Distributed Systems
	An Inspection Game Framework for Networked Architectures
	Figure .:

  ................................... Architectural Classication Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Classifying Scribe and Gossiping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Taxonomy of Byzantine Failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . BAR Tolerance Capabilities of Publish/Subscribe Systems . . . . . . . . . . . . . . . . . . . . . . . . . . .. The Simple Comprehensive Reliability Evaluation Model . . . . . . . . . . . . . . . . . . . . .. A Qualitative Reliability Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Meaning for the Research Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Part II
	STATE-OF-THE-ART IN DEALING WITH
	SELFISHNESS-DRIVEN PEERS
	The previous part served as thematic introduction. This part is determines now
	the current state-of-the-art in terms of BAR tolerance capabilities of distributed
	systems. At rst, the related work is discussed. Then, a set of works are reviewed
	to evaluate their reliability capabilities.
	. Challenge A: Reliability & BAR Tolerance Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	. Challenge B: Robustness Evaluations of Distributed Systems . . . . . . . . . . . . . . . . . . . . . . .
	. Challenge C: Tolerating Selsh Peers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	. Inspection Games for Reliable Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	A S BAR T D S ................................
	. Structure for Comprehensive Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	..

O R W R C

Table . :

 . Overview of the Publish/Subscribe architectural classication scheme.

	A D	E C
	Subscription Model	-topic-based -content-based -type-based -context-based
		-serialized
	Event Data Model	-tagged
		-untagged binary
		-Predicate indexing, e.g.
		-lookup tables
	Matching Algorithm	-Hanson et al. 's algorithm [] -Testing network, e.g.
		-matching trees
		-binary decision diagrams
		-hierarchical
		-PP
	Overlay Organization	-structured PP (S-PP) -unstructured PP (U-PP)
		-PP broker overlay (BO)
		-clustered
		-subscription/event ooding
		-selective
	Dissemination Technique	-selective ltering
		-rendezvous node based
		-basic/informed gossiping
	Adaptation Technique	-active -passive
		-RPC
	Communication Technique	-socket connection
		-web services
	Underlay Awareness	-proximity-awareness -quality-awareness
	Quality of Service

-reliability (guaranteed delivery) -delivery semantics, e.g. best-eort or exactly once -latency/bandwidth guarantees

Table . :

 . The evaluation shows BAR tolerance capabilities of examined systems. This chapter evaluated BAR tolerance capabilities of a sample of current distributed systems. To this end, pub/sub systems and pure dissemination systems were reviewed. To enable a comprehensive evaluation, some preparations were introduced beforehand: an architectural classication scheme and a taxonomy of elementary failures of a peer. It turned out that almost no system tolerates more failures than link/node crash and message loss in the proposed form. One exception is the system FlightPath []. It considers the BAR concept during system design but has still important drawbacks. The scientic community started to address the problem of selshness-driven misbehaviours. Typically, reliability techniques are proposed as optional modules (e.g. encrypted communication), which is not always reasonable or possible. An interesting less-invasive yet powerful alternative is the monitoring approach introduced in this thesis.

	.
	System	Name	Subscription	Type	Dissemination	Technique	Overlay	Organisation	Failure A	Link/Node Crash	Failure B	Message Loss	Failure C	Message Tampering	Failure D	Content Pollution	Failure E	Message Misuse	Failure F	Information Leak	Failure G	Selsh Behaviour
	Pub/Sub Systems					Part III
	SIENA [] Scribe [] PRACTICALLY EVALUATING ROBUSTNESS OF PUB/SUB Selective Hierarchical Content (Filtering) & S-PP Topic Selective (Rendezvous) S-PP SYSTEMS
	Bayeux []	Topic	Selective (Rendezvous)	S-PP														6
	Hermes []	Type	Selective (Rendezvous)	BO/S-PP
	Narada Brokering []	Topic 4	Selective (Filtering)	S-PP (Clustered)														5
	Gryphon []	Content	Selective (Filtering)	BO/S-PP
	IndiQoS []	Type	Selective (Rendezvous)	BO/S-PP
	Sub--Sub []	Content	Gossiping (Informed)	U-PP (Clustered)
	REDS []	Content	Selective (Filtering)
			Content	Selective (Filtering)	S-PP
	TERA []	Topic	Selective (Filtering) 7	U-PP (Clustered)				7
	SpiderCast []	Topic	Gossiping (Informed)	U-PP
	F-A P/S []	Content	Selective (Filtering)	S-PP		10		10
	CAPS [] 2	Content	Selective (Rendezvous)	S-PP
	Jafarpour et al. []	Content	Selective (Filtering)	BO/S-PP (Clustered)
	Boonma and Suzuki []	Topic	Selective (Filtering)	S-PP
							S-PP
							(Clustered)
	LIPSIN []	Topic	Selective (Filtering)	BO/S-PP
	Kazemzadeh and Jacobsen []	Content	Selective (Filtering)	S-PP
	Pure Dissemination Systems
	Peercast []	-		Selective (Filtering)	Hierarchical
	CREW []	-		Gossiping	U-PP
	Voulgaris and van Steen []	-		Gossiping (Informed)	U-PP
	FlightPath []	-		Gossiping	U-PP				11				12						13
	Schroeter et al. et al. []	-		Flooding & Gossiping (Inf.)	BO/S-PP

BO/S-PP Anceaume et al. [] Content Sel. (Filtering) & Gossiping 14 Hierarchical & U-PP 14 14 Baldoni et al. [] 1 9 Esposito et al. [] 3 Topic Sel. (Rendezv.) & IP Multicast 8 Addressing research challenge (B), this part introduces the RCourse benchmarking library. It serves as mean for practical evaluation of a system's capabilities to tolerate the impact of selshness-driven violations. O RC: R B P S .................. . A Short Excursus To Pub/Sub Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Scribe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Gossiping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Underlying Research Principles For Practical Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . Overview to RCourse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. RCourse Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Simulative Evaluations with RCourse and Peersim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Utilization and Experimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. A Note to Multi-Process Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. Adaptation to Individual Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Meaning for the Research Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Table . :

 . This is currently not yet supported byThe pre-dened scenarios of RCourse base on the taxonomy of failures introduced before.

	Failure Type	Experimentation Scenario
		ES1.1 Standard Operation
	< failure-free >	ES1.2 Standard Operation (Network Size Variation)
		ES1.2 Standard Operation (Fanout Variation)
	Failure A	ES2.1 Catastropic Node Crash
	Link/Node Crash	ES2.2 Catastropic Node Crash (Crash Size Variation)
		ES3.1 Catastropic Message Loss
	Failure B	ES3.2 Catastropic Message Loss (Malicious Nodes Variation)
	Message Loss	ES3.3 Message Loss
		ES3.4 Message Loss (Message Loss Variation)
	Failure C Message Tampering	ES4	Message Tampering
	Failure D Content Pollution	ES5	---
		ES6.1 Node Churn
		ES6.2 Node Churn (no publish)
	Failure E Node Churn	ES6.3 Node Churn (with publish)
		ES6.4 Node Churn (Churn Rate Variation, no publish)
		ES6.5 Node Churn (Churn Rate Variation, with publish)
	Failure F Information Leak	ES7	---
	Failure G	ES8.1 Selfish Message Loss
	Selfish Behaviour	ES8.2 Selfish Message Tampering

http://fta.inria.fr/apache-default/pmwiki/index.php Cette thèse est accessible à l'adresse : http://theses.insa-lyon.fr/publication/2013ISAL0083/these.pdf © [T.R. Mayer], [2013], INSA de Lyon, tous droits réservés

:

Table Size

 Size

	RCourse Benchmark -ES1.1 Standard Operation -D3.1 Subscription Table Size Distribution
	# of Entries (self included)
				Node
		100
	Not Delivered Messages (in %)	20 40 60 80
		0
		0	20	40	60	80
				Malicious Nodes in System (in %)

  The example

	inspectee node	inspector node	inspectee node
	Application	Dissemination Algorithm	Application
	Dissemination Algorithm	Inspection Game Layer	Dissemination Algorithm
	Further Network Layer	Further Network Layer	Inspection Game Layer
	loose coupling through network connection	Further Network Layer

Table . :

 . Summary of notation with values used in the example application of the Inspection Game.

	Variable System Values	Description
	n		potentially malicious selsh peers in system (inspectees)
	m		trusted peers in system (inspectors)
	T	-	a time interval in reference to which all calculations are relatively done
	T insp	-	time interval between two inspections
	T sa f e	-	time interval needed for replacing all proof messages
	t i	-	multiplier for T so that t i ⇤ T = T insp
	t s	-	multiplier for T so that t s ⇤ T = T sa f e
	q	game strategy	probability of an inspector to perform an inspection
	p	game strategy	probability of an inspectee to violate
	n i		amount of inspectees to be inspected by an inspector
	r		amount of proof messages to be stored in the history
	h		entry size of the proof message history
	g		amount of multi-cast groups
	g s	. (%)	percentaged amount of multi-cast groups a peer is subscribed to
	g p	. (%)	percentaged amount of multi-cast groups a publisher is publishing to
	p p	. (%)	probability to publish a message (one to all g pub ⇤ g disjoint groups)
	Variable Payo Values	Description
		Scribe Gossiping
	l	.	average transferred messages per T (network load per peer)
	c		costs for the inspector performing an inspection
	a		costs for the inspectee that occur due to a punishment
	d		costs for the system for not detecting defections
	b	.	personal benet of a peer to defect (deviate from the protocol)
	w a		weighting value for a
	w d		weighting value for d
	w b		weighting value for b
	Functions		Description
	g		violation detection function
	g ⇤		violation defection function, bounded to probability values
	s		calculates the eective inspection value (EIP)
	s ⇤		calculates the maximal eective inspection value (MEIP)
	C		inspector payo function
	I		inspectee payo function
	f		calculates the inspectee's best response strategy (BRS)

Table . :

 . Notation summary with values used during the enhanced Inspection Game application.

	Variable Values	System Value Description
	n		amount of peers in system
	T	-	time interval used for calculations
	T insp	-	average time interval between two inspections
	T sa f e	-	average time interval for replacing all proof messages
	t i

Table . :

 . RCourse contributes to enrich the evaluation by quantitative information. To this end, it assists performing quickly launched simulations, also providing pre-dened scenarios.

						.
	System	Name	Subscription	Type	Dissemination	Technique	Overlay	Organisation	Failure A	Link/Node Crash	Failure B	Message Loss	Failure C	Message Tampering	Failure D	Content Pollution	Failure E	Message Misuse	Failure F	Information Leak	Failure G	Selsh Behaviour
	Pub/Sub Systems
	Scribe []	Topic	Selective (Rendezvous)	S-PP	.: % .: %	.: % .: %
	-		-		Basic Gossiping	U-PP	.: % .: %	.: % .: %

(ES1.2( ( Standard(Operation( (((((((Network(Size(Variation)(

  Continuation of table A.

	&
	Failure(Type(&	#& Experimentation(Scenario((	#( Diagram(Description(	Graph(Axes(	(Result(Writeout(
	Continuation of table A.		1&	D1.2&	Dissemination&Completion&&(&absolute&)& &&&&&(&delivered&message&percentage&per&cycle&)&	y:&&&&&&delivered&messages& x:&&&&&&simulation&cycles&	&&global&/&per&cycle&&
						2& 3&	D1.3& D1.4& 25& D1.2& Dissemination&Completion&&(&percentage&)& &&&&&(&delivered&message&percentage&per&cycle&)& Dissemination&Completion&&(&absolute&)&&&&&&&&&&&&& &&&&&(&delivered&message&percentage&per&cycle&)& PubSub&Call&Overview& &&&&&(&amount&of&publish/subscribe&api&calls&per&cycle&)& 26& D1.3& Dissemination&Completion&&(&percentage&)&&&&&&&& &&&&&(&delivered&message&percentage&per&cycle&)&	y:&&&&&&delivered&message&percentage&& x:&&&&&&simulation&cycles& Y&:&&&&&#&of&&pubsub&api&calls&& y:&&&&&&delivered&messages& x:&&&&&&simulation&cycles& &&&&&&&&&&&&(unJ/subscribe,&publish)& X&:&&&&&simulation&cycles& y:&&&&&&delivered&message&percentage&& &&global&/&per&cycle& &&global&/&per&cycle&& &&global&/&per&cycle& x:&&&&&&simulation&cycles& &&global&/&per&cycle&
			4& &	((ES2.1( ( (	4& 5& &&&&crashing&nodes&(gossiping):&30%,&50%,&80%& Catastrophic(Node(Crash(((( &&&&crashing&nodes:&10%,&20%,&30%&	D2.3& D2.4& 27& D2.4& Network&Stress&per&Cycle&&&(&notify&msg&)& &&&&&(&absolute&overlay&hop&counts&relative&to&simulation&cycle&)& Network&Stress&per&Cycle&&&(&all&msg&)&& &&&&&(&absolute&overlay&hop&counts&relative&to&simulation&cycle&)& Network&Stress&per&Cycle&&&(&all&msg&)&&&&&&&&&&&&&&&&& &&&&&(&absolute&overlay&hop&counts&relative&to&simulation&cycle&)& 28& D4.1& Clustering&Coefficient&Distribution&&&&&&&&&&&&&&&&&&&&& &&&&&(&clustering&coefficient&per&node&)&	y&:&&&&&handled&messages& x&:&&&&&simulation&cycles& y&:&&&&&handled&messages& x&:&&&&&simulation&cycles& y&:&&&&&overlay&hop&count& x&:&&&&&simulation&cycles& y&:&&&&clustering&coefficient& x&:&&&&nodes&in&network&	&&global&/&per&cycle& &&global&/&per&cycle& &&global&/&per&cycle& &&per&node&/&final&
	& &&&&& &	<&failureJfree&>& Failure&A& Link/Node&Crash& Failure&B&& Message&Loss& Failure&C&& Message&Tampering& Failure&D&& Content&Pollution Message&Misuse& ,,,( ,,,( Failure&E&& 1& ((ES1.1( Standard(Operation& 6& D2.5& 7& D2.6& 8& D3.1& 9& D3.2& 10& D10.1& 11& D4.1& 12& D4.2& 2& & (13& D1.1& 14& D2.1& 15& D2.2& 16& D2.7& 17& D4.2& 18& D10.1& 3& ES1.3( ( Standard(Operation( ((Fanout(Variation)& 19& D1.2& 20& D1.3& 21& D2.3& 22& D2.4& 29& D4.3& Node&Stress&Distribution&&&&(&notify&msg&)& &&&&&(&handled&messages&per&node&)& Node&Stress&Distribution&&&&(&all&msg&)& &&&&&(&handled&messages&per&node&)& Subscription&Table&Size&Distribution&&& &&&&&(&subscriptions&at&each&node&)& Group&Subscription&Distribution&& &&&&&(&subscription&table&entries&per&group&)& View&Membership&Distribution& &&&&&(&InJ&and&outJdegree&of&every&node&)& Clustering&Coefficient&Distribution& &&&&&(&clustering&coefficient&per&node&)& Network&Clustering&Coefficient& &&&&&(&average&clustering&coefficient&per&cycle&)& Dissemination&Delay& &&&&&(&hop&counts&per&network&size&)& Network&Stress&&&&(&notifiy&msg&)& &&&&&(&absolute&overlay&hop&counts&in&the&network&-&only&notify&and&direct&messages)& UJP2P& Network&Stress&&&&(&all&msg&)& &&&&&(&absolute&overlay&hop&counts&in&the&network&-&all&forwarded&and&direct&messages&)& related& Notification&Overhead&Ratio& &&&&&(&notify&message&hops&relative&to&network&size&)& Network&Clustering&Coefficient& &&&&&(&average&clustering&coefficient&per&cycle&)& UJP2P& related& View&Membership&Distribution& &&&&&(&InJ&and&outJdegree&of&every&node&)& Dissemination&Completion&&(&absolute&)&& &&&&&(&delivered&message&percentage&per&cycle&)& UJP2P& related& Dissemination&Completion&&(&percentage&)& &&&&&(&delivered&message&percentage&per&cycle&)& Network&Stress&per&Cycle&&&(&notify&msg&)& &&&&&(&absolute&overlay&hop&counts&relative&to&simulation&cycle&)& Network&Stress&per&Cycle&&&(&all&msg&)&& &&&&&(&absolute&overlay&hop&counts&relative&to&simulation&cycle&)& Partition&Size&Distribution&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&(&nodes&per&partition&)& 30& D4.4& Network&Partitioning&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&(&amount&of&partitions&per&amount&of&crashed&nodes&)& 10& ''ES6.1' ' Node'Churn'' '''''''(no'publish)&&&&&&&&&&&&churn&rate:&&2%' 42& D2.4& Network&Stress&per&Cycle&&&(&all&msg&)&&&&&&&&&&&&&!& &&&&&(&absolute&overlay&hop&counts&relative&to&simulation&cycle&)& 5& & ((ES2.2( ( Catastrophic(Node(Crash( (((((((Crash(Size(Variation)( 31& D2.7& Notification&Overhead&Ratio& &&&&&(&notify&message&hops&per&publish&call&)& 43& D1.2& Dissemination&Completion&&(&absolute&)&&&&&&&&&&&&& &&&&&(&delivered&message&percentage&per&cycle&)& 32& D5.1& Delivery&Loss&Rate&&&(catastrophic&node&crash)& &&&&&(&not&delivered&messages&relative&to&crashed&nodes&)& 11& ''ES6.2' ' Node'Churn'' '''''''(with'publish)&&&&&&&&&churn&rate:&&2%' 44& D1.3& Dissemination&Completion&&(&percentage&)&&&&&& &&&&&(&delivered&message&percentage&per&cycle&)& 33& D4.2& Network&Clustering&Coefficient&& &&&&&(&clustering&coefficients&for&node&crash&situations&)& 34& D4.3& Partition&Size&Distribution& (&nodes&per&partition&)& 35& D4.4& Network&Partitioning&&&(catastrophic&node&crash)& &&&&&(&amount&of&partitions&per&amount&of&crashed&nodes&)& 6& ((ES3.1( ( Message(Loss( &&&&&&Loss&rates:&10%&,&20%,&30%&& 36& D1.2& Dissemination&Completion&&(&absolute&)&&&&&&&&&& &&&&&(&delivered&message&percentage&per&cycle&)& 37& D1.3& Dissemination&Completion&&(&percentage&)&&&&&& &&&&&(&delivered&message&percentage&per&cycle&)& 38& D2.4& Network&Stress&per&Cycle&&&(&all&msg&)&&&&&&&&&&&&&&& &&&&&(&absolute&overlay&hop&counts&relative&to&simulation&cycle&)& 7& ((ES3.2( ( Message(Loss( (((((((Loss(Rate(Variation)( 39& D2.7& Notification&Overhead&Ratio& &&&&&(&notify&message&hops&per&publish&call&)& 40& D5.1& Delivery&Loss&Rate&&&(lossy&nodes)& &&&&&(&not&delivered&messages&relative&due&to&lossy&links/nodes&)& 8& ((ES4( ( Message(Tampering( (((((((Malicious(Nodes(Variation)( 41& D6& Tampering&Rate&& &&&&&(&reception&rate&of&modified&messages&)& & 9& ((ES5( ,,,( 45& D2.4& Network&Stress&per&Cycle&&&(&all&msg&)&&&&&&&&&&!& &&&&&(&absolute&overlay&hop&counts&relative&to&simulation&cycle&)& 12& ''ES6.3' ' Node'Churn'' 46& D2.2& Network&Stress&&&(&all&msg&)& &&&&&(&absolute&overlay&hop&counts&in&the&network&-&all&forwarded&and&direct&msg&)& UJP2P& y:&&&&&handled&messages& x:&&&&&nodes&in&network& y:&&&&&handled&messages& x:&&&&&nodes&in&network& y:&&&&&subscription&table&size& x:&&&&&nodes&in&network& y:&&&&&#&of&subscription&table&entries&& x:&&&&&multicast&groups&& y:&&&&&degree&of&the&node& x:&&&&&nodes&in&network& y&:&&&&clustering&coefficient& x&:&&&&nodes&in&network& y&:&&&&clustering&coefficient& x&:&&&&simulation&cycles& y&:&&&&&overlay&hop&count& x:&&&&&&network&size&(#&nodes&in&system)& y&:&&&&&handled&messages& x&:&&&&&network&size&(#&nodes&in&system)& y&:&&&&&handled&messages& x&:&&&&&network&size&(#&nodes&in&system)& y:&&&&&notify&hops&per&publish&call& x:&&&&&network&size&(#&nodes&in&system)& y&:&&&&clustering&coefficient& x&:&&&&simulation&cycles& y:&&&&&degree&of&the&node& x:&&&&&nodes&in&network& y:&&&&&&delivered&messages&& x:&&&&&&simulation&cycles& y:&&&&&&delivered&message&percentage&& x:&&&&&&simulation&cycles& y&:&&&&&overlay&hop&count& x&:&&&&&simulation&cycles& y&:&&&&&overlay&hop&count& x&:&&&&&simulation&cycles& related& y:&&&&&#&nodes&in&partition& x:&&&&&#&network&partitions& y&:&&&&&#&of&handled&messages& x&:&&&&&simulation&cycles& y:&&&&&#&of&partitions&&& x:&&&&&crashed&nodes&(in&%)& y:&&&&&&delivered&messages& x:&&&&&&simulation&cycles& y:&&&&&notify&hops&per&publish&call& x:&&&&&crashed&nodes&(in&%)& y:&&&&&not&delivered&messages&(in&%)& &&per&node&/&final& &&per&node&/&final& &&per&node&/&final& &&global&/&final& &&per&node&/&final& &&per&node&/&final& &&global&/&per&cycle& &&global&/&final& &&global&/&final& &&global&/&final& &&global&/&final& &&global&/&per&cycle& &&per&node&/&final& &&global&/&per&cycle&& &&global&/&per&cycle& &&global&/&per&cycle& &&global&/&per&cycle& &&global&/&final& &&global&/&per&cycle& &&global&/&final& &&global&/&per&cycle&& &&global&/&final& x:&&&&&crashed&nodes&(in&%)& y:&&&&&&delivered&message&percentage&& &&global&/&per&cycle& x:&&&&&&simulation&cycles& &&global&/&final& UJP2P& related& y:&&&&clustering&coefficient& x&:&&&&crashed&nodes&(in&%)& &&global&/&final& y:&&&&&#&nodes&in&partition& x:&&&&&#&network&partitions& &&global&/&final& y:&&&&&#&of&partitions&& x:&&&&&crashed&nodes&(in&%)& &&global&/&final& y:&&&&&&delivered&messages& x:&&&&&&simulation&cycles& &&global&/&per&cycle&& y:&&&&&&delivered&message&percentage&& x:&&&&&&simulation&cycles& &&global&/&per&cycle& y&:&&&&&overlay&hop&count& x&:&&&&&simulation&cycles& &&global&/&per&cycle& y:&&&&&notify&hops&per&publish&call& x:&&&&&malicious&nodes&(in&%)& &&global&/&final& y:&&&&&not&delivered&messages&(in&%)& x:&&&&&malicious&nodes&in&system&(in&%)& &&global&/&final& y:&&&&&delivered&mod.&messages&&(in&%)& x:&&&&&malicious&nodes&in&system&(in&%)& &&global&/&final& y&:&&&&&#&of&handled&messages& &&global&/&per&cycle& x&:&&&&&simulation&cycles& y&:&&&&&#&of&handled&messages& x&:&&&&&churn&rate&(in&%)& &&global&/&per&cycle& &per&cycle&only&for&calculation&&&& &of&appropriate&final&value& 13& ''ES6.4' Node'Churn' & & ' '''
						23& D2.5&	Node&Stress&Distribution&&&&(&notify&msg&)& &&&&&(&handled&messages&per&node&)&	y:&&&&&handled&messages& x:&&&&&nodes&in&network&	&&per&node&/&final&
						24& D2.6&	Node&Stress&Distribution&&&&(&all&msg&)& &&&&&(&handled&messages&per&node&)&	y:&&&&&handled&messages& x:&&&&&nodes&in&network&	&&per&node&/&final&

''''''(Churn'Rate'Variation,'no'publish)'

'''(Churn'Rate'Variation,'with'publish)'

						47& D2.2&	Network&Stress&&&(&all&msg&)& &&&&&(&absolute&overlay&hop&counts&in&the&network&-&all&forwarded&and&direct&msg&)&	y&:&&&&&#&of&handled&messages& x&:&&&&&churn&rate&(in&%)&	&&global&/&per&cycle& &per&cycle&only&for&calculation&&&& &of&appropriate&final&value&
						48& D2.7&	Notification&Overhead&Ratio& &&&&&(&notify&message&hops&per&publish&call&)&	y:&&&&&notify&hops&per&publish&call& x:&&&&&churn&rate&(in&%)&	&&global&/&final&
						49& D5.1&	Delivery&Loss&Rate&&&(lossy&nodes)& &&&&&(&not&delivered&messages&relative&due&to&lossy&links/nodes&)&	y:&&&&&not&delivered&messages&(in&%)& x:&&&&&churn&rate&(in&%)&	&&global&/&final&
	&
	Failure&F& Information&Leak&		14& ''ES7' +++'	+++' +++'	+++'	+++'	+++'
	&
	Failure&G&	&	15&	''ES8.1' '	Selfish'Message'Loss' &&&&&&&&&&drop&message&probabilities:&1,&0.66,&0.33'	50& D5.1&	Delivery&Loss&Rate&&&(selfish&drops)&&&&&&&&&&&&&&&&&&&&&&& &&&&&(&not&delivered&messages&relative&to&malicious&situation&)&	y:&&&&&not&delivered&messages&(in&%)& x:&&&&&malicious&nodes&in&system&(in&%)&	&&global&/&final&
	&Selfish&Behaviour&		16&	''ES8.2'	Selfish'Message'Tampering'
		&		'	&&&&&&modify&message&probabilities:&1,&0.66,&0.33&

Cette thèse est accessible à l'adresse : http://theses.insa-lyon.fr/publication/2013ISAL0083/these.pdf © [T.R. Mayer],[2013], INSA de Lyon, tous droits réservés

The four components are a Monitor, a Reputation System, a Trust Manager, and a Path Manager. For further details, the interested reader is referred to the paper.Cette thèse est accessible à l'adresse : http://theses.insa-lyon.fr/publication/2013ISAL0083/these.pdf © [T.R. Mayer], [2013], INSA de Lyon, tous droits réservés

Based on SIENA.

Based on Chord.

Based on Scribe.

Supports also JMS, JXTA and Xpath queries.

Monitors quality information (e.g. bandwidth) and provides a security module, both can be used as base for anti-rational-techniques.

Four protocols are introduced; the used one provides quality-based underlay awareness.

It is distinguished between outer and inner-cluster dissemination can be choosen by the administrator.

IP Multicast is used as inner-cluster technique to increase dissemination eciency.

QoS capabilities enable to retransmit messages in case of failures. between transfers is not revealed. 12 A tracker manages only one subscriber per multicast group. Signed messages avoid non authorized message generation.13 FlightPath uses proofs of misbehaviour (PoM) and punishments. 14 This work compares a leader-based against gossip-like epidemic algorithm (may provide redundant path).Cette thèse est accessible à l'adresse : http://theses.insa-lyon.fr/publication/2013ISAL0083/these.pdf © [T.R. Mayer],[2013], INSA de Lyon, tous droits réservés

Cette thèse est accessible à l'adresse : http://theses.insa-lyon.fr/publication/2013ISAL0083/these.pdf © [T.R. Mayer], [2013], INSA de Lyon, tous droits réservés Cette thèse est accessible à l'adresse : http://theses.insa-lyon.fr/publication/2013ISAL0083/these.pdf © [T.R. Mayer], [2013], INSA de Lyon, tous droits réservés

&Cette thèse est accessible à l'adresse : http://theses.insa-lyon.fr/publication/2013ISAL0083/these.pdf © [T.R. Mayer],[2013], INSA de Lyon, tous droits réservés

CONCLUSION OF THE THESIS

We conclude the thesis now by reviewing the three essential contributions in terms of the research challenges stated in the introduction.

. Due to their meaning for challenge (A), we consider the preparations for system comparison and the BAR tolerance evaluation as one contribution. This contribution outlines together with the related work discussion the state-of-the-art and justies the thesis' main research challenge. A comprehensive system evaluation in terms of BAR tolerance capabilities was enabled. An extract is shown in table ., while the full evaluation (see table . on page ) reviews the BAR tolerance capabilities of systems. The evaluation is done in a qualitative way and is based on previous preparations, an architectural classication and a taxonomy of failures. Hence, this contribution meets challenge (A) as well as (A.) and (A.).

The architectural classication normalizes the terms and interpretations of the literature. Thus, it enables a comprehensive architectural comparison, used by the evaluation to draw conclusions from the system architecture. The introduced taxonomy consists of elementary failures of a peer; all further failure scenarios are a direct result. This was an adequate metric for the qualitative evaluation, able to visualize the BAR tolerance capabilities in a comprehensible way. The evaluation revealed that practically all examined systems implement only basic reliability mechanisms. This is interpret as only a base for optional logic or specic adaptions to user dependent needs.