Many network phenomena are well modeled as spreads of epidemics through a network. Prominent examples include the spread worms and email viruses, and, more generally, faults. types information dissemination can also be epidemics. In this paper we address question what makes an epidemic either weak or potent. More precisely, identify topological properties graph that determine persistence particular, show if ratio cure to infection rates is larger than spectral radius graph, then mean...

Structured peer-to-peer overlay networks provide a substrate for the construction of large-scale, decentralized applications, including distributed storage, group communication, and content distribution. These overlays are highly resilient; they can route messages correctly even when large fraction nodes crash or network partitions. But current not secure; small malicious prevent correct message delivery throughout overlay. This problem is particularly serious in open systems, where many...

Gossip-based protocols for group communication have attractive scalability and reliability properties. The probabilistic gossip schemes studied so far typically assume that each member has full knowledge of the global membership chooses targets uniformly at random. requirement impairs their applicability to very large-scale groups. In this paper, we present SCAMP (Scalable Membership protocol), a novel peer-to-peer protocol which operates in fully decentralized manner provides with partial...

The growth of the Internet raises new challenges for design distributed systems and applications. In context group communication protocols, gossip-based schemes have attracted interest as they are scalable, easy to deploy, resilient network process failures. However, traditional protocols two major drawbacks: 1) rely on each peer having knowledge global membership; 2) being oblivious topology, can impose a high load links when applied wide-area settings. this paper, we provide theoretical...

Structured peer-to-peer overlay networks provide a substrate for the construction of large-scale, decentralized applications, including distributed storage, group communication, and content distribution. These overlays are highly resilient; they can route messages correctly even when large fraction nodes crash or network partitions. But current not secure; small malicious prevent correct message delivery throughout overlay. This problem is particularly serious in open systems, where many...

In this article we address the problem of counting number peers in a peer-to-peer system, and more generally aggregating statistics individual over whole system. This functionality is useful many applications, but hard to achieve when each node has only limited, local knowledge We propose two generic techniques solve problem. The Random Tour method based on return time continuous random walk originating query. Sample Collide samples gathered until target redundant are obtained. It inspired...

We study how the spread of computer viruses, worms and other self-replicating malware is affected by logical topology network over which they propagate. consider a model in each host can be one 3 possible states—susceptible, infected or removed (cured no longer susceptible to infection). characterize size population that eventually becomes depends on topology. Specifically, we show if ratio cure infection rates larger than spectral radius graph, initial small, then final also small sense...

Abstract We give a rigorous analysis of variations the contact process on finite graph in which cure rate is allowed to vary from one vertex next, and even depend current state system. In particular, we study epidemic threshold models where proportional degree node or when it number its infected neighbors. © 2010 Wiley Periodicals, Inc. Random Struct. Alg.,

The emergence of drug resistance in M. tuberculosis undermines the efficacy (TB) treatment individuals and TB control programs populations. Multiple is often attributed to sequential functional monotherapy, standard initial regimens have therefore been designed include simultaneous use four different antibiotics. Despite widespread combination therapy, highly resistant tb strains emerged many settings. Here we a stochastic birth-death model estimate probability multidrug during growth...

The growth of peer-to-peer applications on the Internet motivates interest in general purpose overlay networks. construction overlays connecting a large population transient nodes poses several challenges. First, connections should reflect underlying network topology, order to avoid overloading and allow god application performance. Second, connectivity among active be maintained, even presence high failure rates or when proportion are not active. Finally, cost using spread evenly peer for...

This paper studies the performance of contention based medium access control (MAC) protocols. In particular, a simple and accurate technique for estimating throughput IEEE 802.11 DCF protocol is developed. The on rigorous analysis Markov chain that corresponds to time evolution back-off processes at contending nodes. An extension presented handle case where service differentiation provided with use heterogeneous parameters, as, example, in 802.11e EDCA protocol. Our results provide new...

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> We provide an analytical framework for evaluating the performance of automatic patching systems. use it to quantify speed patch or alert dissemination required worm containment. Motivated by scalability and trust issues, we consider a hierarchical system where network hosts are organized into subnets, each containing server (termed superhost). Patches disseminated superhosts through overlay...

Motivated by emerging need of learning algorithms for large scale networked and decentralized systems, we introduce a distributed version the classical stochastic Multi-Arm Bandit (MAB) problem. Our setting consists number agents n that collaboratively simultaneously solve same instance K armed MAB to minimize average cumulative regret over all agents. The can communicate collaborate among each other only through pairwise asynchronous gossip based protocol exchange limited bits. In our...

Epidemic-style (gossip-based) techniques have recently emerged as a scalable class of protocols for peer-to-peer reliable multicast dissemination in large process groups. These provide probabilistic guarantees on reliability and scalability. However, popular implementations epidemic-style are reputed to suffer from two major drawbacks: (a) (Network Overhead) when deployed WAN-wide or VPN-wide scale they generate number packets that transit across the boundaries multiple network domains...

The problem of sharing bandwidth in a communication network has been the focus much research aimed at guaranteeing an appropriate quality service to users. This is particularly challenging environment with great diversity users and applications, which makes it difficult, if not impossible, tightly constrain user attributes requirements. motivates shifting burden rate allocation from end-systems. We propose decentralized scheme for adaptation study its dynamics. proposed uses congestion...

Epidemic-style (gossip-based) techniques have recently emerged as a class of scalable and reliable protocols for peer-to-peer multicast dissemination in large process groups. However, popular implementations epidemic-style suffer from two major drawbacks: 1) Network overhead: when deployed on WAN-wide or VPN-wide scale, they generate number packets that transit across the boundaries multiple network domains (e.g., LANs, subnets, ASs), causing an overload core elements such bridges, routers,...

A finite load, large buffer model for the WLAN medium access protocol IEEE 802.11 is developed that gives throughput and delay predictions. This enables us to investigate impact of buffering on resource allocation. In presence heterogeneous loads, do not allocate transmission opportunities equally. It shown increased can help this inequity, but only at expense possibly significantly delays

We introduce a novel decentralized, multi agent version of the classical Multi-Arm Bandit (MAB) problem, consisting n agents, that collaboratively and simultaneously solve same instance K armed MAB to minimize individual regret. The agents can communicate collaborate among each other only through pairwise asynchronous gossip based protocol exchange limited number bits. In our model, at point decide on (i) which arm play, (ii) whether to, if so (iii) what whom with. develop algorithm in...

We study how the spread of computer viruses, worms, and other self-replicating malware is affected by logical topology network over which they propagate. consider a model in each host can be one 3 possible states - susceptible, infected or removed (cured, no longer susceptible to infection). characterise size population that eventually becomes depends on topology. Specifically, we show if ratio cure infection rates larger than spectral radius graph, initial small, then final also small sense...

This paper studies the performance of contention based medium access control (MAC) protocols. In particular, a simple and accurate technique for estimating throughput IEEE 802.11 DCF protocol is developed. The on rigorous analysis Markov chain that corresponds to time evolution back-off processes at contending nodes. An extension presented handle case where service differentiation provided with use heterogeneous parameters, as, example, in 802.11e EDCA protocol. Our results provide new...