hide
Free keywords:
-
Abstract:
We investigate the class of so-called epidemic algorithms that are commonly
used for the lazy transmission of
updates to distributed copies of a database. These algorithms use a simple
randomized communication
mechanism to ensure robustness. Suppose $n$ players communicate in parallel
rounds in each of which every
player calls a randomly selected communication partner. In every round, players
can generate rumors
(updates) that are to be distributed among all players. Whenever communication
is established between two
players, each one must decide which of the rumors to transmit. The major
problem (arising due to the
randomization) is that players might not know which rumors their partners have
already received. For
example, a standard algorithm forwarding each rumor from the calling to the
called players for $\Theta(\ln
n)$ rounds needs to transmit the rumor $\Theta(n \ln n)$ times in order to
ensure that every player finally
receives the rumor with high probability.
We investigate whether such a large communication overhead is inherent to
epidemic algorithms. On the
positive side, we show that the communication overhead can be reduced
significantly. We give an algorithm
using only $O(n \ln\ln n)$ transmissions and $O(\ln n)$ rounds. In addition, we
prove the robustness of this
algorithm, e.g., against adversarial failures. On the negative side, we show
that any address-oblivious algorithm
(i.e., an algorithm that does not use the addresses of communication partners)
needs to send $\Omega(n \ln\ln
n)$ messages for each rumor regardless of the number of rounds. Furthermore, we
give a general lower bound
showing that time- and communication-optimality cannot be achieved
simultaneously using random phone
calls, that is, every algorithm that distributes a rumor in $O(\ln n)$ rounds
needs $\omega(n)$ transmissions.
