Supplement to "Sampling Strategies for Epidemic-Style Information Dissemination" - Gupta, Varun; Vojnovic, Milan (Microsoft, 2009)
In this note we establish several new results for sampling-based information dissemination strategies considered in [1] (version with proofs – [2]). First, we establish the computational complexity and an algorithm for computing the target set of subnets for the optimum static sampling strategy, OPT-STATIC [1], given the densities of susceptible hosts over subnets. Second, we identify the worst-case and best-case placements of initially infected hosts, so as to maximize or minimize, respectively, the number of samplings required to reach a given fraction of susceptible hosts. Finally, we study the effect of target fraction of infected hosts on the optimum number of samplings, and consider simple approximations for the optimum number of samplings to reach a given target fraction of hosts. The surprising accuracy of our simple approximation provides insights on the qualitative and quantitative impact of system parameters on the optimum number of samplings. We illustrate some of our results using the empirical distributions of hosts over subnets that were used in [1].