Delay analysis of epidemic schemes in sparse and dense heterogeneous contact environments

Epidemic algorithms have found their way into many areas of computer science, such as databases and distributed systems, and recently for communication in Opportunistic and Delay Tolerant Networks (DTNs). To ensure analytical tractability, existing analyses of epidemic spreading predominantly consider homogeneous contact rates between nodes. However, this assumption is generally not true, especially in opportunistic networks between mobile nodes. In this paper we consider two classes of contact/mobility models with heterogeneous contact rates. We derive simple closed form approximations and bounds for the basic epidemic spreading step, and prove conditions for their accuracy. To demonstrate the utility of this result in practice, we use it to derive the delay of epidemic routing and variants (gossiping and 2-hop routing) as well as to construct a network size estimator based on local measurements. We use simulation results based on synthetic heterogeneous models to validate our analysis, as well as real traces to demonstrate that our expressions can still be useful even in scenarios with significantly more

complex structure.