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...

Easy to deploy, robust, and highly resilient failures, epidemic algorithms are a potentially effective mechanism for propagating information in large peer-to-peer systems deployed on Internet or ad hoc networks. It is possible adjust the parameters of algorithm achieve high reliability despite process crashes disconnections, packet losses, dynamic network topology. Although researchers have used applications such as failure detection, data aggregation, resource discovery monitoring, database...

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...

We address the problem of convergence to equilibrium a general class point processes, containing, in particular, nonlinear mutually exciting an extension linear Hawkes and give conditions guaranteeing existence stationary version nonstationary version, both distribution variation. also new proof result Kerstan concerning processes with bounded intensity dynamics satisfying Lipschitz condition.

We discuss the relevance of fairness as a design objective for congestion control mechanisms in Internet. Specifically, we consider backbone network shared by dynamic number short-lived flows, and study impact bandwidth sharing on performance. In particular, prove that broad class fair allocations, total flows progress remains finite if load every link is less than one. also show provided allocation "sufficiently" fair, performance optimal sense throughput mainly determined their access...

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...

Decelle et al. [1] conjectured the existence of a sharp threshold on model parameters for community detection in sparse random graphs drawn from stochastic block model. Mossel, Neeman and Sly [2] established negative part conjecture, proving impossibility non-trivial reconstruction below threshold. In this work we solve positive conjecture. To that end introduce modified adjacency matrix B which counts self-avoiding paths given length ℓ between pairs nodes. We then prove logarithmic ℓ,...

Motivated by increased concern over energy consumption in modern data centers, we propose a new, distributed computing platform called Nano Data Centers (NaDa). NaDa uses ISP-controlled home gateways to provide and storage services adopts managed peer-to-peer model form center infrastructure. To evaluate the potential for savings pick Video-on-Demand (VoD) services. We develop an VoD traditional centers this using large set of empirical access data. find that even under most pessimistic...

We study the dissemination of dynamic content, such as news or traffic information, over a mobile social network. In this application, users subscribe to dynamic-content distribution service, offered by their service provider. To improve coverage and increase capacity, we assume that share any content updates they receive with other meet. make two contributions. First, determine how provider can allocate its bandwidth optimally at "fresh" possible. More precisely, define global fairness...

In this paper, we determine the optimal convergence rates for strongly convex and smooth distributed optimization in two settings: centralized decentralized communications over a network. For (i.e. master/slave) algorithms, show that distributing Nesterov's accelerated gradient descent is achieves precision $\varepsilon > 0$ time $O(\sqrt{κ_g}(1+Δτ)\ln(1/\varepsilon))$, where $κ_g$ condition number of (global) function to optimize, $Δ$ diameter network, $τ$ (resp. $1$) needed communicate...

This paper concerns the design of distributed algorithms for sharing network bandwidth resources among contending flows. The classical fairness notion is so-called max-min fairness; Kelly (see Europ. Trans. Telecom. vol.8 p.33-37, 1997) has previously introduced alternative proportional criterion; we introduce a third criterion, which naturally interpreted in terms delays experienced by ongoing transfers. We prove that fixed size window control can achieve fair according to any these...

This paper concerns the design of distributed algorithms for sharing network bandwidth resources among contending flows. The classical fairness notion is so-called max-min fairness. alternative proportional criterion has recently been introduced by F. Kelly (see Eur. Trans. Telecommun., vol.8, p.33-7, 1997); we introduce a third criterion, which naturally interpreted in terms delays experienced ongoing transfers. We prove that fixed-size window control can achieve fair according to any these...

We investigate how congestion control can achieve efficient usage of network resources in the presence heterogeneous communication delays between users and resources. To this end, we consider a fluid flow model behavior. study stability system's behavior under small perturbations around target equilibrium point (local stability). establish several criteria for certain linear delay-differential equations, via technique which essentially reduces question to studying ordinary differential...

Several peer-to-peer systems for live streaming have been recently deployed (e.g. CoolStreaming, PPLive, SopCast). These all rely on distributed, epidemic-style dissemination mechanisms. Despite their popularity, the fundamental performance trade-offs of such mechanisms are still poorly understood. In this paper we propose several results that contribute to understanding trade-offs.

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...

Portable devices have more data storage and increasing communication capabilities everyday. In addition to classic infrastructure based communication, these can exploit human mobility opportunistic contacts communicate. We analyze the characteristics of such forwarding paths. establish that mobile networks in general are characterized by a small diameter, destination device is reachable using only number relays under tight delay constraint. This property first demonstrated analytically on...

We consider the problem of broadcasting a live stream data in an unstructured network. The has been studied extensively for edge-capacitated networks. give first proof that whenever demand lambda + epsiv is feasible > 0, simple local-control algorithm stable under lambda, and as corollary famous theorem Edmonds. then study node-capacitated case show similar optimality result complete graph. through simulation delay users must wait order to playback video with small number skipped packets,...

An increasing number of retail energy markets show price fluctuations, providing users with the opportunity to buy at lower than average prices. We propose temporarily store this inexpensive in a battery, and use it satisfy demand when prices are high, thus allowing exploit variations without having shift their low-price periods. study battery control policy that yields best performance, i.e., minimizes total discounted costs. The optimal is shown have threshold structure, we derive these...

We propose Push-to-Peer, a peer-to-peer system to cooperatively stream video. The main departure from previous work is that content proactively pushed peers, and persistently stored before the actual transfers. initial placement increases availability improves use of peer uplink bandwidth. Our specific contributions are: (i) associated pull policies allow optimal bandwidth; (ii) performance analysis such in controlled environments as DSL networks under ISP control; (iii) distributed load...

In this article we provide a novel characterization of the proportionally fair bandwidth allocation network capacities, in terms Fenchel–Legendre transform capacity region. We use to prove stability (i.e., ergodicity) dynamics under sharing, by exhibiting suitable Lyapunov function. Our result extends previously known results more general model including Markovian users routing. particular, it implies that condition exponential service time distributions remains valid so-called phase-type...

A non-backtracking walk on a graph is directed path such that no edge the inverse of its preceding edge. The matrix indexed by edges and can be used to count on-backtracking walks given length. It has been recently in context community detection appeared previously connection with Ihara zeta function some generalizations Ramanujan graphs. In this work, we study largest eigen valus Erdos-Renyi random Stochastic Block Model regime where number proportional vertices. Our results confirm...