  We study gossip algorithms for the rumor spreading problem which asks each
node to deliver a rumor to all nodes in an unknown network. Gossip algorithms
allow nodes only to call one neighbor per round and have recently attracted
attention as message efficient, simple and robust solutions to the rumor
spreading problem.
  Recently, non-uniform random gossip schemes were devised to allow efficient
rumor spreading in networks with bottlenecks. In particular, [Censor-Hillel et
al., STOC'12] gave an O(log^3 n) algorithm to solve the 1-local broadcast
problem in which each node wants to exchange rumors locally with its
1-neighborhood. By repeatedly applying this protocol one can solve the global
rumor spreading quickly for all networks with small diameter, independently of
the conductance.
  This and all prior gossip algorithms for the rumor spreading problem have
been inherently randomized in their design and analysis. This resulted in a
parallel research direction trying to reduce and determine the amount of
randomness needed for efficient rumor spreading. This has been done via lower
bounds for restricted models and by designing gossip algorithms with a reduced
need for randomness. The general intuition and consensus of these results has
been that randomization plays a important role in effectively spreading rumors.
  In this paper we improves over this state of the art in several ways by
presenting a deterministic gossip algorithm that solves the the k-local
broadcast problem in 2(k+log n)log n rounds. Besides being the first efficient
deterministic solution to the rumor spreading problem this algorithm is
interesting in many aspects: It is simpler, more natural, more robust and
faster than its randomized pendant and guarantees success with certainty
instead of with high probability. Its analysis is furthermore simple,
self-contained and fundamentally different from prior works.
