PushToPull: Effective, Low Traffic Epidemic Replication

28.06.2006

Abstract:
The Internet of today consists of more heterogeneous components than ever. Typically, an average user's laptop or desktop computer can act as a server for others. This is for example seen in peer-to-peer networks, and will lead to more unreliable servers than with normal Web or e-mail servers.

When we are to design a system adapting to an unreliable setting like described above, we cannot think in the classical terms of a centralized server model. More dynamic algorithms have to be used, and we propose epidemic algorithms as a candidate for disseminating data efficiently and reliably.

This thesis presents the design and implementation of a replication service, based on an epidemic and probabilistic approach. Applications running on the same machine as the service are able to disseminate and receive data, using our service.

Epidemic approaches are often associated with high overhead in the form of unnecessary network traffic. This thesis presents the PushToPull algorithm, which disseminates data with high performance, but keeps wasted network communication at a low level. The algorithm is based on known epidemic algorithms, versions of so-called rumor mongering.

An important focus in our work is to detect the point when an update disseminated to n peers is held by half of all peers, the n/2 point. Each peer does this detection locally, without the need for extra communication. Our experiments show that it is possible to detect this point individually. If most peers find the n/2 point the probabilistic PushToPull algorithm can experience low traffic, high-performance dissemination. The experiments also show that dissemination times with our algorithm follow a logarithmic curve.