IE-OPIM Joint Graduate Seminar: Devin Sezer (Middle East Technical University)
“Analysis of Push-type Epidemic Data Dissemination in Fully Connected Networks”
Date: Wednesday, April 29, 2015
Time: 13:40 – 14:30
Location: FENS G035
Abstract: 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 epidemic algorithm: in each discrete round the infected nodes randomly choose c other nodes in the network and transmit, i.e., push the data to them. We write this round as a discrete time random walk with state dependent linear dynamics, the random selection of each infected node corresponding to a step of the walk. The final position of the walk represents the number of newly infected nodes in a push round. We use this to compute the expected number of rounds so that a given percentage of the network is infected and complete 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. These limits imply that the number of newly infected nodes in a push round, and the number of random connections needed within a single push round so that a given percent of the network is infected, are both asymptotically normal and provide their mean and variance. The results also allow an asymptotic comparison of the pull and the push algorithms: for large networks, a pull round on average always infects more nodes; if the network is half infected initially, for fanout c > 15, a single round of pull or push is almost enough to infect the whole network on average.
Bio: Devin Sezer is an Associate Professor at the Graduate School of Applied Mathematics, at METU. He received his B.Sc. in computer engineering and mathematics double major from METU. Later, he received his Master’s and Ph.D. degrees in Applied Mathematics from Brown University.