Analysis of push-type epidemic data dissemination in fully connected networks

Download

index.pdf

Date

2014-07-01

Author

ÇAĞLAR, MİNE
Sezer, Ali Devin

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

197
views

75
downloads

Consider a fully connected network of nodes, some of which have a piece of data to be disseminated to the whole network. We analyze the following push-type epidemic algorithm: in each push round, every node that has the data, i.e., every infected node, randomly chooses c E Z. other nodes in the network and transmits, i.e., pushes, the data to them. We write this round as a random walk whose each step corresponds to a random selection of one of the infected nodes; this gives recursive formulas for the distribution and the moments of the number of newly infected nodes in a push round. We use the formula for the distribution to compute the expected number of rounds so that a given percentage of the network is infected and continue a numerical comparison of the push algorithm and the pull algorithm (where the susceptible nodes randomly choose peers) initiated in an earlier work. We then derive the fluid and diffusion limits of the random walk as the network size goes to infinity and deduce a number of properties of the push algorithm: (1) the number of newly infected nodes in a push round, and the number of random selections needed so that a given percent of the network is infected, are both asymptotically normal, (2) for large networks, starting with a nonzero proportion of infected nodes, a pull round infects slightly more nodes on average, (3) the number of rounds until a given proportion lambda of the network is infected converges to a constant for almost all lambda is an element of (0, 1). Numerical examples for theoretical results are provided. (C) 2014 Elsevier ay. All rights reserved.

Subject Keywords

Peer to peer, Pull, Push, Epidemics, Epidemic algorithm, Diffusion, Fluid, Approximation, Asymptotic, Analysis, Data dissemination, Fully connected, Network, Graph

URI

https://hdl.handle.net/11511/31122

Journal

PERFORMANCE EVALUATION

DOI

https://doi.org/10.1016/j.peva.2014.03.002

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

Evaluation of Terahertz Channel in Data Centers MOLLAHASANİ, Shahram; Onur, Ertan (2016-04-29) Designing data center network topologies with the objective of minimizing cost, increasing bisection bandwidth and decreasing latency is a difficult problem. The solutions in the literature mainly concentrate on wired networks and minimizing wiring costs thereof. Only a few proposals address the benefit of employing wireless communications in data centers due to spectrum and bandwidth limitations of current wireless communication technologies. By using terahertz communication in a data center as a complemen...
Routing Algorithms As An Application Of Graph Theory Yıldırım, Gökberk; Özbudak, Ferruh; Department of Cryptography (2023-1-27) This paper examines routing algorithms that are generally used in various network types, such as Internet Protocol in graph-based models, to find the shortest routing path or minimum cost. The fundamental approach for calculating the shortest path between one point to another is searching a given graph, starting at the source node, and traversing adjacent nodes until the destination node is reached. The aim is to identify the shortest routing path to the destination node. This paper searches well-known rout...
Improving performance of network intrusion detection systems through concurrent mechanisms Atakan, Mustafa; Şener, Cevat; Department of Computer Engineering (2003) As the bandwidth of present networks gets larger than the past, the demand of Network Intrusion Detection Systems (NIDS) that function in real time becomes the major requirement for high-speed networks. If these systems are not fast enough to process all network traffic passing, some malicious security violations may take role using this drawback. In order to make that kind of applications schedulable, some concurrency mechanism is introduced to the general flowchart of their algorithm. The principal aim is...
Relay Selection for Efficient HARQ-IR Protocols in Relay-Assisted Multisource Multicast Networks Quoc-Tuan Vien, Quoc-Tuan Vien; Nguyen, Huan X.; Shah, Purav; Ever, Enver; Duc To, Duc To (2014-05-21) This paper investigates relay selection for reliable data transmission in relay-assisted multisource multicast networks (RMMNs) where multiple source nodes distribute information to a set of destination nodes with the assistance of multiple relay nodes. Hybrid automatic repeat request with incremental redundancy (HARQ-IR) is used and supported by either a physical-layer network coding (PNC) or an analog network coding (ANC) technique employed at the relays. By deriving efficiency metrics of the HARQ-IR prot...
Cooperative Multiple-Access in Fading Relay Channels Yılmaz, Ayşen (2006-06-15) Virtual antenna arrays can be constructed via relaying even in the case that there is insufficient physical space or other resources for multiple antennae on wireless nodes. When there is a multiple access scenario, relaying offers a variety of ways to establish communication between source and destination nodes. We will compare a scheme based on space division multiple access to previously studied time division based ones. We observe that space division improves especially the ergodic capacity.

Citation Formats

M. ÇAĞLAR and A. D. Sezer, “Analysis of push-type epidemic data dissemination in fully connected networks,” PERFORMANCE EVALUATION, pp. 21–36, 2014, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31122.