Introduction

Summary

The idea of mimicking the propagation of biological epidemics to achieve diffusion of useful information was first proposed in the late 1980s, the decade that also saw the appearance of computer viruses. Back then, these viruses propagated by copies on floppy disks and caused much less harm than their contemporary versions. But it was already noticed that they evolved and survived much as biological viruses do, a fact that prompted the idea of putting these features to good (rather than evil) use. The first application to be considered was synchronisation of distributed databases.

Interest in this paradigm received new impetus with the advent of peer-to-peer systems, online social systems and wireless mobile ad hoc networks in the early 2000s. All these scenarios feature a complex network with potentially evolving connections. In such large-scale dynamic environments, epidemic diffusion of information is especially appealing: it is decentralised, and it relies on randomised decisions which can prove as efficient as carefully made decisions. Detailed accounts of epidemic algorithms can be found in papers by Birman et al. and Eugster et al. Their applications are manifold. They can be used to perform distributed computation of global statistics in a spatially extended environment (e.g. mean temperature seen by a collection of sensors), to perform real-time delivery of video data streams (e.g. to users receiving live TV via peer-to-peer systems over the internet) and to propagate updates of dynamic content (e.g. to mobile phone users whose phone operating system requires patching against vulnerabilities).